[Algorithm] Backtracking(백트래킹)

백트래킹이란?

 

완전탐색처럼 모든 경우를 탐색하나, 중간 과정에서 조건에 맞지 않는 케이스를 가지치기하여 탐색 시간을 줄이는 기법이다. 즉, 백트래킹은 모든 가능한 경우의 수 중에서 특정한 조건을 만족하는 경우만 살펴보는 것이다.

 

백트래킹의 특징

• 모든 경우의 수를 탐색하지 않기 때문에 완전탐색보다 시간적으로 효율적이다.
• 탐색 중 조건에 맞지 않는 경우 이전 과정으로 돌아가야 하기 때문에 재귀를 사용하는 경우가 많다.
• 가지치기를 얼마나 잘하느냐에 따라 효율성이 결정된다.

가지치기란?

• 지금의 경로가 해가 될 것 같지 않으면 그 전으로 돌아가는 것이다.
• 불필요한 부분을 쳐내는 것으로 되돌아간 후 다시 다른 경로를 검사한다.

백트래킹의 적용

• N의 크기가 작을 때 보통 20 이하 (주로 재귀함수로 구현하기 때문)
• 그 전 과정으로 돌아가면서 하는 탐색이 필요한 경우