프로그래민👨‍💻

백트래킹의 전형적인 문제인 N-Queen 문제이다. 체스판에 서로 공격할 수 없도록 N개의 Queen을 배치하는 문제인데, Queen의 움직임 특성상 한 행에 한 개의 Queen 만을 가질수 있게 됨으로 한행을 depth로 보고 dfs를 실행하였다. 보통의 백트래킹은 visit함수로만 방문 여부를 결정하였는데 이 문제에선 대각선이랑 같은 열에 Queen이 존재해야하는지 봐야함으로 check함수를 이용하여 방문 가능여부를 한번더 확인해주는 과정을 거쳐 문제를 해결하였다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 4..

조합을 사용하는 문제이다. 백트래킹을 사용하는 comb함수를 구현하여 N개중에서 N/2개를 뽑는 조합의 경우를 구하고, 그 경우 마다 check함수를 적용시켜 서로 다른 두 집합의 시너지 합이 최소가 되는 경우를 찾았다. check함수에서는 visit배열을 기준으로 방문의 유무를 이용하여 두개의 그룹으로 나누었다. 그리고 이 check함수에서도 2개씩 뽑아내야 하는 조합이 있는데 이것은 단순 이중for문으로 구현하였다. 문제를 이해하는데 꽤 많은 시간이 걸려서 다른 블로그를 참고하였다. 문제의 의도를 파악하는 연습이 필요한 것 같다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 ..