[알고리즘] 백트래킹(Backtracking)
백트래킹(Backtracking)은 조건을 만족하는 해를 찾기 위해 모든 경우를 탐색 하되, 불필요한 경우는 조기에 가지치기(pruning) 하며 탐색을 중단하는 탐색 알고리즘 이다. 즉, 선택을 번복할 수 있다는 점에서 그리디 알고리즘과 차이가 있다. 그리디 알고리즘은 항상 최적 선택 을 기준으로 해를 구성하지만, 백트래킹은 조건을 만족하는 해가 있는 방향으로만 탐색한다. 백트래킹은 상태 공간(State Space)을...