sm 기술 블로그
백트래킹 본문
백트래킹
- 더 이상 나아갈 수 없는 상황에서 그 이전 단계로 복귀하는 과정
모든 경우의 수를 전부 고려하는 알고리즘이다.
트리 탐색 알고리즘이라고 봐도 무방하며 방식에 따라 깊이우선탐색 (Depth First Search - DFS) 와 최선 우선 탐색 (Best First Search - BFS) 가 있다.
모든 경우의 수를 고려해야 한다면 DFS가 좋으며 BFS로도 구현이 가능하나 큐의 크기, 속도가 똑같아 DFS가 좋다.
장점
무한히 깊은 곳을 찾아야할때 효과적이다.
단점
모든곳을 방문하기 때문에 목표지점이 있지 않는 경로로 빠져서 비효율적인 결과를 초래할 수 있다.
https://smhope.tistory.com/308
너비 우선 탐색(BFS)
너비 우선 탐색(BFS) 루트 노드에서 시작해서 인접한 노드를 먼저 탐색하는 방법. 가장 가까운 정점을 먼저 방문하고 이후 멀리 떨어져 있는 정점을 방문하는 방식이다. 특징 직관적이지 않다. 큐
smhope.tistory.com
https://smhope.tistory.com/307
깊이 우선 탐색(DFS)
깊이 우선 탐색(DFS) 루트노드에서 시작해서 다음 분기로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법 특징 깊이 우선 탐색(DFS) 에 비해서 너비 우선 탐색(BFS)이 보다 좀 더 간단하다. 어떤
smhope.tistory.com
'자료구조 || 알고리즘' 카테고리의 다른 글
| [알고리즘 | 자료구조] 그리디 알고리즘(Greedy Algorithm) (0) | 2022.07.17 |
|---|---|
| 동적프로그래밍(Dynamic Programming) (0) | 2022.07.01 |
| 너비 우선 탐색(BFS) (0) | 2022.06.28 |
| 깊이 우선 탐색(DFS) (0) | 2022.06.28 |
| 유클리드 호제법(최대공약수 구하기) (0) | 2022.06.25 |
'자료구조 || 알고리즘' Related Articles
more
Comments