백트래킹(Backtracking)

💡 백트래킹(Backtracking)이란 해를 찾는 도중 해가 아니어서 막히면, 되돌아가서 다시 해를 찾아가는 기법을 말합니다. 최적화 문제와 결정 문제를 푸는 방법이 됩니다. 용어 설명 유망함(promising) : 진행 중인 경로가 해답을 찾을 가능성이 있음을 의미 유망하지 않음(non-promising) : 진행 중인 경로가 해답을 찾을 가능성이 없음을 의미 가지치기(pruning) : 유망하지 않은 하위 트리를 자르는 것 백트래킹 vs DFS ? 공통점 두 방법 모두 깊이 우선 탐색 (DFS, Depth-First Search)을 이용하여 탐색합니다. 재귀 함수를 사용하는데, 이 때 스택(stack) 메모리를 사용하여 작동합니다. 차이점 목적 DFS: 모든 노드를 방문하는 것이 목적입니다. 경로 ..