백트래킹 (Backtracking) 어릴 적 신문 신문 한 구석에 있던 "미로 찾기"를 떠올려 보세요. 갈림길을 만나면 일단 한 곳으로 가봅니다. 가다 보니 막다른 길이 나오면 어떻게 하나요? 다시 직전 갈림길로 되돌아가서 다른 길을 선택하죠?알고리즘에서 이 되돌리기 전략을 백트래킹이라고 부릅니다. 백트래킹은 모든 경로를 다 가보되 지금 선택한 길이 정답이 될 가능성이 있는 지 체크합니다. 이를 알고리즘 용어로 유망성 검사(Promising)이라고 합니다. 그리고 그 길이 "아, 이 길은 가봐야 어차피 답이 안 나오겠네?"라는 생각이 드는 순간 그 경로를 과감히 포기하고 직전 단계로 돌아갑니다. 이 스마트한 포기 과정을 알고리즘 용어로 가지치기(Pruning)라고 부릅니다. 즉, 백트래킹은 재귀적으로 탐..
