1.2 백트래킹 (Backtracking)

<aside> 💡 "백트래킹"은 해를 찾는 도중 해가 아니어서 막히면, 되돌아가서 다시 해를 찾아가는 기법을 말합니다.

</aside>

백트래킹은 일반적으로 완전탐색과의 유사성을 가지고 있습니다. 둘 다 모든 해를 찾아 나가려고 하는것은 같지만 백트래킹의 경우 해를 구해나가는 과정 중 더 진행해도 해가 될 것 같지 않다면 중단시키고 되돌아가는것이 특징입니다.

문제의 모든 가능성은 하나의 트리 형태로 표현할 수 있으며 부모 노드에서 자식 노드로 이동하는 것을 모든 가능성중 특정 가능성으로 결정하는 것으로 보아 이 트리를 의사 결정 트리라고 부릅니다. 즉 백트래킹은 의사 결정 트리를 순회하며 답을 찾는 방법으로 이해할 수 있습니다.

 

 

이 중단시키고 되돌아가는 것을 백트래킹에서는 가지치기 라고 부릅니다.

이 가지치기를 얼마나 잘 하느냐에 따라 효율성이 달라집니다.

코딩테스트에서 자주 나오는 문제는 완전탐색과 유사합니다.

그 이유는 백트래킹은 결국 완전탐색의 최적화 버전이기 때문입니다.

그렇기에 완전탐색과 같은 유형에서 사용이 가능합니다.

• “조건이 존재하는” 부분집합 생성 문제
• “조건이 존재하는” 순열과 조합 생성 문제
• “조건이 존재하는” 격자 탐색 문제