반응형
백트래킹이란?
- DFS와 유사한 알고리즘으로 차이점이 있다면 효율성이 있습니다. 가지치기라고 하여 조건에 만족하지 않을 경우 진행하지 않고 이전 단계로 넘어가는 형태를 말합니다. 이것으로 인해 모든 경로를 탐색하지 않아도 되어 효율성이 좋습니다.
구현방식 및 동작원리
- 재귀함수로 구현하며 조건에 만족하지 않을 경우 이전 단계로 돌아감
시간 복잡도
- 문제마다 다릅니다. 왜냐하면 조건에 만족하느냐 안하느냐에 따라 더 진행할지 말지가 정해지기 때문 입니다.
문제 유형
- 순열, 조합, N-Queen 가 있습니다. 해당 문제들은 주어진 조건이 명확하고 조기에 진행 불가능한 상태를 확인할 수 있기 때문입니다.
참고영상
- 바로가기
- 바로가기
반응형
'알고리즘(코테 대비) > 알고리즘 공부' 카테고리의 다른 글
| [필수 알고리즘] DP (0) | 2025.09.09 |
|---|---|
| [필수 알고리즘] 그리디 알고리즘 (0) | 2025.09.09 |
| [필수 알고리즘] DFS (0) | 2025.05.03 |
| [필수 알고리즘] BFS (0) | 2025.05.03 |
| [필수 알고리즘] 그래프 탐색 (0) | 2025.05.03 |