backtracking은 깊이우선탐색(DFS) 방식으로 상태공간트리를 탐색하는 알고리즘으로, 최적화 문제를 해결하는데에 사용될 수 있다. backtracking의 진행절차는 다음과 같다. ① 상태공간트리의 깊이우선검색(DFS)을 실시 ② 각 노드가 유망(promising)한지 점검 ③ 유망하지 않은 노드들은 더 이상 검색하지 않고 그 노드의 부모노드로 돌아가서 검색을 계속(pruning), 유망한 노드들은 그 노드의 자식노드를 검색 여기서 promising, 즉 유망하다는 것은 더 내려다볼 가치가 있다는 것이고 반대로 유망하지 않다(non-promising)는 것은 전혀 해답이 나올 가능성이 없다는 것을 의미한다. 유망하지 않으면 그 자식노드에 대한 탐색을 중단하고 부모노드로 돌아가는데, 이를 '가지친다..