백트래킹(Backtraking)이란? 모든 가능한 경우의 수를 탐색하는 완전 탐색(Brute Force)의 한 형태이지만, 가지치기(pruning)을 통해 불필요한 경로는 탐색하지 않는 효율적인 완전탐색입니다.
백트래킹의 기본 원리
1. 어떤 문제를 여러 단계의 결정 과정(decision step)으로 나눕니다
2. 각 단계마다 가능한 선택지를 탐색합니다.
3. 만약 조건을 위반하는 선택지가 생기면 그 분기를 즉시 중단하고 이전 단계로 돌아갑니다.
4. 조건을 만족하면 계속 다음 단계로 진행합니다.
백트래킹 의사코드
def backtrack(경로, 선택지):
if (정답을 찾은 경우):
결과 저장
return
for 선택 in 가능한 선택지q (pruning)
continue
경로에 선택 추가
backtrack(갱신된 경로, 갱신된 선택지)
경로에서 선택 제거 # 되돌아가기 (backtrack)
백트래킹 vs 완전탐색
완전탐색
- 모든 경우를 전부 탐색
- O(n!)
- 대표 예시: 브루트포스
백트래킹
- 조건 불만족 시 조기 중단
- 가지치기로 탐색 줄임
- 대표 예시: N-Queen, Sudoku, 조합 생성 등
<백트래킹 문제 모음>
[백준] 14888번_연산자 끼워넣기
