Let IT Begin

* Python을 기준으로 합니다 백트래킹 (Backtracking) - 개념 백트래킹 : 가능성이 없는 해는 포기하여 되돌아가고, 가능성이 높은 해결책만을 탐색하는 방법 여러 제약 조건을 만족하는 상태를 탐색해야 하는 제약 충족 문제에 적합한 방식 대표적으로 DFS는 더 이상 탐색할 경로가 없으면 (해가 없으면) 되돌아가서 다른 깊이를 탐색하는 방식으로 동작하므로 백트래킹의 예시로 볼 수 있음 - 즉, 백트래킹은 DFS를 기본 골격으로 함 백트래킹의 동작 가능한 해들의 후보 집합을 정의하고 정의된 집합을 그래프로 표현함 - 이를 상태 공간 트리 (state space tree)라고 함 유망 함수를 정의하고, 상태 공간 트리를 루트에서부터 DFS로 탐색하면서, 유망 함수에 따라 방문한 노드가 정답이 아니..