[알고리즘] 백트래킹 (BackTracking)
알고리즘 문제를 풀다 보면 "모든 경우를 다 확인해야 하는데, 경우의 수가 너무 많아서 시간 초과가 나는 상황"을 자주 마주하게 된다. 이럴 때 단순한 완전 탐색으로는 해결하기 어렵고, 불필요한 탐색을 줄이는 전략이 필요하다. 백트래킹(BackTracking)은 이러한 문제를 해결하기 위한 대표적인 기법으로, 탐색 과정에서 가능성이 없는 경로를 미리 차단하여 효율을 높이는 방법이다. 백트래킹을 이해하기 위해 먼저, 그 기반이 되는 깊이 우선 탐색(DFS)에 대해 간단히 알아보자. 깊이 우선 탐색(DFS, Depth-First Search)깊이 우선 탐색은 가능한 모든 경로를 끝까지 탐색하는 방식이다.하나의 경로를 선택하면, 그 경로의 끝까지 내려간 뒤 더 이상 진행할 수 없을 때 다른 경로로 이동한다. ..
