
[ALGORITHM] 백트래킹
·
ALGORITHM & DATA STRUCTURE
백트래킹 (Backtracking) 제약 조건 만족 문제에서 해를 찾기 위한 전략 해를 찾기 위하여, 후보군 제약조건을 점진적으로 체크하다가, 해당 후보군이 제약 조건을 만족할 수 없다고 판단되는 즉시 Backtrack(다시는 해당 후보군을 체크하지 않을 것을 표기)하고, 바로 다른 후보군으로 넘어가, 최적의 해를 찾는 방법 실제 구현시, 고려할 수 있는 모둔 경우의 수를 상태공간트리(State Space Tree)를 통하여 표현 각 후보군은 DFS로 확인하며, 상태공간 트리를 탐색하면서, 제약이 맞지 않으면 후보가 될만한 곳으로 넘어가서 바로 탐색 상태공간트리 (State Space Tree) 문제 해결 과정의 중간 상태를 각각의 노드로 나타낸 트리 상태공간트리 탐색 기법 Promising : 해당 루..