backtracking

[알고리즘] 백트래킹 해결 방법과 예시 문제

백트래킹 이란? 백트래킹은 완전탐색을 하는 과정에서 가지치기를 통해 유망하지 않은 곳은 더 이상 탐색하지 않는 알고리즘 기법을 말한다. 백트래킹 용어 유망(Promising) 하다. 어떤 노드를 방문했을 때 그 노드를 포함한 경로가 해답이 될 수 있다면 유망하다고 한다. 가지치기 (Pruning) 유망하지 않은 노드가 포함되는 경로는 더 이상 고려하지 않는다. 백트래킹 문제의 일반적인 해결 방법 상태 공간 트리를 구한다. 깊이 우선 탐색(DFS)을 이용하여 상태 공간 트리를 탐색한다. 각 노드가 유망한지를 점검한다. 만일 그 노드가 유망하지 않으면, 그 노드의 부모 노드로 돌아가서 다음 자식 노드로 간다. 어떤 노드가 해당 문제의 해가 되면 탐색을 중지하고, 해를 구한다. 백트래킹 문제의 예시 1. N-..