DFS
DFS는 깊이 우선 탐색으로 재귀 호출을 이용하여 모든 경우의 수를 다 찾는 탐색 방법이다.
단, 모든 경우의 수를 다 찾기 때문에 비효율적일 수 있다
백트래킹
백트래킹(되추적) 알고리즘은
어떤 노드를 점검할때 해당 노드가 조건에 부합되지않으면 부모노드의 다른 노드를 검사한다
로 이해를 하였다.
백트래킹 알고리즘을 사용하는 이유는 비효율적인 경로를 아예 들리지않아 DFS보다 효율적이기 때문에 사용하는데 비효율적인 경로를 들리지않는 것은 가지치기(purning)이라고 한다.
'알고리즘' 카테고리의 다른 글
| 알고리즘 백준 15650 N과M(2)(파이썬) (0) | 2022.01.12 |
|---|---|
| 알고리즘 백준 15649 N과M(1)(파이썬) (0) | 2022.01.12 |
| 알고리즘 백준 10814 나이순정렬(파이썬) (0) | 2022.01.08 |
| 알고리즘 백준 10814 단어 정렬(파이썬) (0) | 2022.01.08 |
| 알고리즘 백준 11651 좌표 정렬하기2(파이썬) (0) | 2022.01.07 |