백트래킹(Backtracking)

 경우의 수를 탐색해 나가는 도중 찾는 해가 아니면 이전 상태로 되돌아가서 다시 해를 찾는 방법이다. 주요 개념은 해를 얻을 때까지 모든 가능성을 시도한다는 점이다. 모든 가능성은 하나의 트리처럼 구성할 수 있으며, 가지 중에 해결책이 있다. 트리를 검사하기 위해 깊이 우선 탐색을 사용한다. 탐색 중에 오답을 만나면 이전 분기점으로 돌아간다. 시도해보지 않은 다른 해결 방법이 있으면 시도한다.

 

DFS

해가 되지 않을 것 같다면 그 아래의 탐색은 중지하고 이전 분기점으로 되돌아가는데 탐색 횟수가 줄어들게 된다. 이를 가지치기라고 한다. 즉 가지치기를 얼마나 잘하느냐에 따라서 효율성이 결정된다.

모든 트리를 탐색하게 된다면 해가 없을 것이다.

 

백트래킹은 기본적으로 완전탐색 카테고리에 있다. 다른 알고리즘 방법으로 해결하기 힘들어 전수 조사가 필요한 경우에 사용된다. 백트래킹은 다항시간에 문제해결이 가능한 알고리즘을 찾지 못했을 때 이다.

 

다항시간이란, O(N^2), O(N log N), O(N^3) 등 시간복잡도의 최고 차수가 상수에 해결가능한 문제를 의미