1. 백트래킹(Backtracking)과 DFS의 차이
- 어떤 노드에서 부터 더이상 가능성이 없는 노드를 따라가지 않음으로 시도의 횟수를 줄인다.
⇒ 이 과정을 (Prunning, 가치치기) 라고 부른다.
- 백트래킹의 과정
- 상태 공간 트리의 DFS 를 실시한다.
- 각 노드가 유망한지를 점검한다.
- 만일 노드가 유망하지 않으면, 부모 노드로 돌아가서 검색을 계속한다.
- 백준의 N과 M문제가 대표적임
Uploaded by N2T
반응형
반응형
'Algorithm > APS' 카테고리의 다른 글
| [APS] 16. 상호배타집합 파이썬(Python)으로 구현하기 (1) | 2022.10.03 |
|---|---|
| [APS] 15. Prim 알고리즘 파이썬(Python)으로 구현하기 (1) | 2022.10.03 |
| [APS] 13. 퀵 정렬(Quick Sort) (0) | 2022.10.03 |
| [APS] 12. 병합정렬(합병정렬) Merge Sort (0) | 2022.10.03 |
| [APS] 11. Python으로 조합(Combination)만들기 (0) | 2022.09.22 |