수강한 강의 Chapter 21 백 트래킹 - 백 트래킹 알고리즘 이해 학습 후기 백트래킹(Backtracking) 백트래킹 또는 퇴각 검색으로 불리며 제약 조건 만족 문제에서 해를 찾기 위한 전략이다. 모든 조합을 시도해서 문제의 해를 찾으며 퇴각 검색을 통해 많은 부분의 조합들을 배제하기에 풀이 시간이 단축된다. 모든 조합을 DFS방식으로 확인하며 조건이 맞지 않으면 포기하고 바로 해가 될만한 곳으로 넘어가서 탐색 용어 Promising: 조건에 맞는지 검사하는 것 Pruning: 가지치기로 조건에 맞지 않으면 포기하고 바로 다음 탐색할 곳으로 옮겨 시간을 절약하는 기법 대표적인 문제: N Queen 대표적인 백트래킹 문제로 NxN 크기의 체스판에 N개의 퀸을 서로 공격할 수 없도록 배치하는 문제로 ..
