카테고리 없음
[알고리즘] 백트래킹
[알고리즘] 백트래킹
백트래킹은 해를 찾는 도중에 '막히면' 되돌아가서 다시 해를 찾아가는 전략이다. 모든 가능한 경우의 수를 전부 살펴보는 브루트 포스(Brute Force) 방식과 달리, 백트래킹은 현재 상태에서 해가 될 가능성이 없다고 판단되면 더 이상 그 방향으로 탐색하지 않고 이전으로 돌아간다. N-Queens 문제N-Queens 문제는 N×N 체스판에 N개의 퀸을 서로 공격할 수 없도록 배치하는 문제이다. 알고리즘 구현: cvoid queens(index i) { index j; if(promising(i)) if(i==n) cout 유망성 검사: cbool promising(index i) { index k; bool switch; k=1; ..
