코딩고치

백 트래킹 기법 백 트래킹 또는 퇴각 검색이라 칭함 제약 조건 만족 문제를 풀기 위한 전략 후보군의 제약 조건을 체크하다가 만족할 수 없다고 판단되면 backtrack (다시는 이 후보군을 체크하지 않음), 그 후 다른 후보군으로 넘어감 계산의 양을 줄일 수 있음 모든 경우의 수를 상태 공간 트리로 표현 각 후보군을 DFS로 탐색 제약기 맞지 않으면 해의 후보가 될만한 곳으로 넘어가서 탐색 Promising: 조건이 맞는지 검사 Pruning: 조건이 맞지 않으면 다른 루트로 가서 탐색, 시간 절약 DFS로 탐색을 진행하면서 조건에 부합하는지 체크하고 부합하지 않으면 다른 루트로 가서 DFS 탐색을 진행 N Queen 문제 NxN 크기의 체스판에 N개의 퀸을 서로 공격할 수 없도록 배치하는 문제 Prun..