![[알고리즘 #5] 백트래킹](https://image.inblog.dev?url=https%3A%2F%2Fsource.inblog.dev%2Ffeatured_image%2F2025-09-03T15%3A52%3A45.225Z-893d25d9-0e5d-44e1-9054-2097af9c5f84&w=2048&q=75)
백트래킹
탐색 기법으로, 문제를 해결할 수 있는 모든 경로를 탐색하면서 선택한 경로가 유효하지 않거나 조건에 만족하는 해를 찾지 못할 경우, 이전 단계로 되돌아가 다른 경로를 시도하는 알고리즘이다.
- 기능 : 문제를 해결할 수 있는 모든 경로 탐색
- 특징
- 재귀 함수로 구현
- 가지치기로 성능 향상
- 시간 복잡도(N: 분기 수, d: 탐색 깊이)
- O(N^d)
백트래킹은 일반적으로 재귀 함수 형태로 구현하며, 앞서 배운 DFS의 개념과 구현 방식이 매우 유사하다. 가장 큰 특징은 가지치로 유효하지 않는 경로를 조기에 배제하여 탐색 범위를 줄이고 성능을 높힌다.
백트래킹 핵심 이론
1. 가능한 선택지 탐색하기
2. 유효성 검사 및 가지치기
각 선택지가 문제의 조건을 만족하는지 검사한다. 만약 조건을 만족하지 않으면, 해당 경로는 더 이상 탐색하지 않고 즉시 이전 단계로 되돌아간다.
3. 해답 도출하기
조건을 만족하는 해답을 찾으면 이를 기록하고, 필요에 따라 다른 경로도 계속 탐색한다.
Share article