내 맴

- Backtracking Algorithm ✔ 해를 찾는도중에 해가 아니면 되돌아가서 다시 해를 찾는 기법 ✔ 모든 경우의 수를 전부 고려한다 ( 브루트 포스 Algorithm과 유사) ✔ 최적화(optimization) 문제와 결정(decision) 문제 ( yes or no question) 를 해결할수있다. ✔ DFS (깊이 우선 탐색 ) 으로 모든 Node를 검색한뒤 Node의 유망성을 점검하여 유망하지않으면 부모노드로 돌아간 후 다른 자손 노드를 탐색한다 - 순서 1. State Space Tree에서 DFS를 실시한다 2. 각 Node가 promising한 지 점검 3. If Node가 promising한 경우 → 자손 Node 탐색 Else non promising한 경우 → 부모 Node..

문제 ) https://www.acmicpc.net/problem/9663 9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net [ 설명 ] N개의 Queen을 서로 상대를 공격하지 않도록 NxN 체스판에 위치 시키는 문제 → 상대를 공격하지 않으려면 같은 행,열,대각선 상에 위치하면 안된다 예를들어 4 Queen의 경우 , 첫번째 queen을 (1,1)에 둔다면 2번째 queen은 노란색으로 표시한 자리에는 올 수 없다. [ 풀이 ] Backtracking Algorithm으로 풀 수 있는 대표적인 문제다. - Backtrack..