백트래킹1 [알고리즘 이론] 7. 백트래킹 백트래킹 제약조건 만족 문제에서 해를 찾기 위한 전략 해를 찾기 위해 후보군에 제약 조건을 점진적으로 체크하다가, 해당 후보군이 제약 조건을 만족할 수 없다고 판단되는 즉시 백트랙(이 후보군은 다시 체크하지 않을 것을 표시) 하고, 바로 다른 후보군으로 넘어가며, 결국 최적의 해를 찾는 방법 즉, 백트래킹은 트리 구조를 기반으로 DFS로 깊이 탐색을 진행하면서, 각 루트에 대해 조건이 부합하는지 체크하고, 만약 해당 트리에서 조건에 맞지 않는 노드는 더 이상 DFS로 깊이 탐색을 진행하지 않고 가지를 쳐버리는 탐색. 알고리즘 문제 추천 N과 M(1 ~ 4) (실버 3) https://www.acmicpc.net/problem/15649 https://www.acmicpc.net/problem/15650 .. 2023. 5. 9. 이전 1 다음