728x90
백트래킹이란?
- 노드의 유망성을 판단한 뒤 해당 노드가 유망하지 않다면 부모노드로 돌아가 다른 자식 노드를 찾는 방법.
❗️즉, 모든 경우의 수를 찾아 보지만 그 중에서도 가능성 있는 경우의 수만 찾아보는 것을 의미❗️
백트래킹 vs dfs vs 브루트포스
1. 브루트 포스
- 모든 경우의 수를 찾아본다.
- 장점 : 만족하는 값을 100% 찾아냄
- 단점 : 조합 가능 경우의 수에 따라 필요 자원 크기가 커 질 수 있음.
2. 백트래킹
- 해당 범위 내에서 조건을 추가하여 값의 유망성을 판단.
- 장점 : 탐색에 불필요한 자원을 줄일 수 있다. (브루트 포스의 단점 보완)
3. dfs
- 백트래킹에 사용되는 대표적인 탐색 알고리즘
❗️ 백트래킹의 방법 중 하나가 dfs임 ❗️
728x90
'🐣 알고리즘 삐약 > ✌️알고리즘 개념 잡기' 카테고리의 다른 글
| [DP | Dynamic Programming] 카데인 알고리즘 Kadane's Algorithm (0) | 2023.10.16 |
|---|---|
| [Factors] gcd, lcm Theorem | C++ / Cpp (0) | 2022.05.24 |
| [Prime] 에라토스 테네스의 체 | C++ / Cpp (0) | 2022.05.24 |
| [소수 & 약수] Prime | C++ / Cpp (0) | 2022.05.24 |
| [Range Queries] Segment Tree | C++ (0) | 2022.05.17 |