설명 해를 찾는 도중에 '막히면' (즉, 해가 아니면) 되돌아가서 다시 해를 찾아가는 기법 백트래킹 기법은 최적화 문제와 결정 문제를 해결 가능 결정 문제 : 문제의 조건을 만족하는 해가 존재하는지의 여부를 'yes' 또는 'no'가 답하는 문제 미로 찾기 n-Queen 문제 Map coloring 부분 집합의 합(Subset Sum) 문제 등 백트래킹과 깊이우선탐색과의 차이 어떤 노드에서 출발하는 경로가 해결책으로 이어질 것 같지 않으면 더 이상 그 경로를 따라가지 않음으로써 시도의 횟수를 줄임. (Prunning 가지치기) 깊이우선탐색이 모든 경로를 추적하는데 비해 백트래킹은 불필요한 경로를 조기에 차단 깊이우선탐색을 가하기에는 경우의 수가 너무 많음 즉 N! 가지의 경우의 수를 가진 문제에 대해 깊..
