백트래킹(Backtracking) 알고리즘
백트래킹은 일종의 DFS 기반 알고리즘으로, 문제 해결 과정에서 해를 찾기 위해 후보군을 검사하다가 조건을 만족하지 않으면 이전 단계로 돌아가 다른 후보군을 찾는 기법이다. 주로 조합, 순열, 부분집합 등을 구하는 문제에서 사용된다. 백트래킹은 유용한 문제 해결 기법 중 하나로, 많은 NP-hard 문제에 적용될 수 있다. 백트래킹의 기본 아이디어 상태 공간 트리(State Space Tree): 문제의 해를 트리 구조로 표현한다. 각 노드는 문제의 한 상태를 나타내며, 간선은 상태 간의 전이를 나타낸다. 프로모션(promising): 해당 노드에서 유망한지 검사한다. 즉, 현재 상태에서 해를 찾을 가능성이 있는지를 확인한다. 가지치기(cutting off): 유망하지 않은 노드의 서브트리는 검사하지 않..
Programming/알고리즘
2024. 1. 21. 01:56