“모든 경우를 다 뒤지면 너무 느린데, 어떻게 하면 빠르게 답을 찾을 수 있을까?” 코딩 테스트에서 순열·조합·N-Queen·스도쿠 같은 문제를 만났을 때 떠오르는 질문입니다. 백트래킹 알고리즘 가지치기는 바로 이 질문의 답입니다. 완전 탐색(Brute Force)처럼 모든 경우를 시도하되, 현재 경로가 답이 될 수 없다고 판단되는 순간 더 깊이 들어가지 않고 즉시 되돌아오는(Backtrack) 전략입니다. 미로를 탐색할 때 막힌 길을 만나면 왔던 길로 돌아와 다른 길을 시도하는 것과 정확히 같은 원리입니다. 오늘은 백트래킹의 내부 작동 구조부터 가지치기 조건 설계법, N-Queen·순열·부분집합 합·스도쿠까지 실전 코드와 함께 완전히 정리해 드립니다.
목차
- 백트래킹이란 무엇인가 — 완전 탐색과 무엇이 다른가
- 백트래킹의 핵심 메커니즘 — 상태 공간 트리와 재귀 구조
- 가지치기(Pruning) 설계법 — 핵심은 유망 함수다
- 백트래킹 핵심 문제 완전 분석 — 순열·조합·부분집합·N-Queen
- 심화 문제 — 스도쿠·단어 탐색·외판원 문제
- 백트래킹 최적화 전략과 면접 답변 가이드
1. 백트래킹이란 무엇인가 — 완전 탐색과 무엇이 다른가
백트래킹(Backtracking)은 해를 찾는 도중 막히면 되돌아가서 다른 경로를 시도하는 탐색 전략입니다. 1950년대 수학자 D.H. 레머(D.H. Lehmer)가 체계적으로 정리했으며, 현재는 조합 최적화·AI·게임 트리 탐색의 핵심 알고리즘으로 자리 잡았습니다.
완전 탐색 vs 백트래킹 vs 동적 프로그래밍
세 가지를 혼동하는 경우가 많습니다. 각각이 어떻게 다른지를 먼저 명확히 이해해야 합니다.
완전 탐색 (Brute Force):
모든 경우를 빠짐없이 탐색한다.
가지치기 없음 → 지수 시간 그대로 소비
백트래킹 (Backtracking):
모든 경우를 시도하되, 유망하지 않은 경로는 즉시 중단한다.
가지치기(Pruning)로 탐색 공간을 극적으로 줄임
→ 최악은 완전 탐색과 같지만 평균적으로 훨씬 빠름
동적 프로그래밍 (Dynamic Programming):
부분 문제의 결과를 메모이제이션으로 재사용한다.
중복 계산 제거 → 다항 시간 보장
→ 최적 부분 구조와 중복 부분 문제가 있을 때만 적용 가능
백트래킹이 적합한 문제 유형
백트래킹은 다음 세 가지 유형의 문제에 가장 잘 맞습니다.
결정 문제(Decision Problem): 해가 존재하는지 예/아니오로 답한다. 예: 스도쿠에 해가 있는가?
최적화 문제(Optimization Problem): 가능한 해 중 최적(최솟값·최댓값)을 찾는다. 예: 외판원 문제에서 최단 경로는?
열거 문제(Enumeration Problem): 가능한 모든 해를 나열한다. 예: n개 원소의 모든 순열을 구하라.
핵심 직관 — 미로와 가지치기
백트래킹을 직관적으로 이해하는 가장 좋은 비유는 미로 탈출입니다. 미로에서 한 방향으로 계속 전진하다가 막힌 벽을 만나면, 왔던 길을 되돌아가서(Backtrack) 아직 시도하지 않은 다른 갈림길을 선택합니다. 이 과정에서 “이 길은 절대 출구로 이어지지 않는다”고 판단할 수 있다면, 그 길의 모든 하위 경로를 탐색하지 않고 즉시 잘라냅니다(Pruning). 이 잘라내기가 백트래킹의 핵심 무기입니다.
2. 백트래킹의 핵심 메커니즘 — 상태 공간 트리와 재귀 구조
백트래킹을 코드로 구현하기 전에, 내부에서 무슨 일이 일어나는지를 상태 공간 트리로 시각화해야 합니다.
상태 공간 트리(State Space Tree)
백트래킹이 탐색하는 공간을 트리로 표현한 것이 상태 공간 트리입니다. 각 노드는 현재 선택 상태를 나타내고, 간선은 선택지를 나타냅니다. 루트에서 리프까지의 경로 하나가 하나의 완전한 후보 해(Candidate Solution)입니다.
예시: [1, 2, 3]에서 2개 선택하는 조합
루트
/ | \
1 2 3
/ \ \
2 3 3
↓ ↓ ↓
[1,2][1,3] [2,3] ← 유효한 해(리프)
백트래킹은 이 트리를 DFS(깊이 우선 탐색) 방식으로 순회합니다. 그러나 DFS와의 결정적 차이는 유망하지 않은 노드에 도달하면 그 노드의 모든 자손을 탐색하지 않고 즉시 부모로 돌아간다는 점입니다.
백트래킹의 기본 재귀 골격
모든 백트래킹 문제는 아래 골격 코드로 수렴합니다. 이 구조를 완전히 체화하면 어떤 백트래킹 문제도 이 틀에 맞춰 해결할 수 있습니다.
python
def backtrack(상태, 선택_목록):
# 1. 종료 조건 — 완전한 해에 도달했는가
if 종료_조건:
결과에_추가(상태)
return
for 선택 in 선택_목록:
# 2. 유망성 검사 — 이 선택이 유효한가 (가지치기)
if not is_promising(선택, 상태):
continue # 유망하지 않으면 즉시 건너뜀
# 3. 선택 적용 — 상태 변경
상태에_선택_추가(선택)
# 4. 재귀 탐색 — 더 깊이 들어감
backtrack(상태, 남은_선택_목록)
# 5. 선택 취소 — 상태 복원 (핵심!)
상태에서_선택_제거(선택)
5번 “선택 취소(Undo)”가 백트래킹의 심장입니다. 재귀 호출이 끝나면 반드시 상태를 이전으로 복원해야 다른 경로를 올바르게 탐색할 수 있습니다. 이 취소 과정 없이 상태가 계속 쌓이면 잘못된 결과가 나옵니다.
재귀 호출 스택으로 이해하는 되돌아가기
python
# 실행 흐름 추적을 위한 디버그 버전
def backtrack_debug(path, choices, depth=0):
indent = " " * depth
print(f"{indent}→ 진입: path={path}, choices={choices}")
if len(path) == 2: # 종료 조건: 2개 선택
print(f"{indent}✓ 해 발견: {path}")
return
for i, choice in enumerate(choices):
print(f"{indent} 선택: {choice}")
path.append(choice) # 선택 적용
remaining = choices[i+1:] # 중복 방지
backtrack_debug(path, remaining, depth + 1)
removed = path.pop() # 선택 취소 ← 핵심!
print(f"{indent} 취소: {removed} → path 복원: {path}")
backtrack_debug([], [1, 2, 3])
# 출력:
# → 진입: path=[], choices=[1, 2, 3]
# 선택: 1
# → 진입: path=[1], choices=[2, 3]
# 선택: 2
# → 진입: path=[1, 2], choices=[3]
# ✓ 해 발견: [1, 2]
# 취소: 2 → path 복원: [1]
# 선택: 3
# ✓ 해 발견: [1, 3]
# 취소: 3 → path 복원: [1]
# 취소: 1 → path 복원: []
# ...
3. 가지치기(Pruning) 설계법 — 핵심은 유망 함수다
백트래킹의 성능은 가지치기의 품질에 달려 있습니다. 가지치기를 얼마나 정교하게 설계하느냐가 같은 백트래킹이라도 O(n!)과 O(n·2ⁿ)의 차이를 만들어냅니다.
유망 함수(Promising Function) 설계 3원칙
원칙 1. 제약 조건 위반 여부 확인
→ 현재 선택이 문제의 명시적 조건을 위반하는가?
예: N-Queen에서 같은 열·대각선에 퀸이 있는가?
원칙 2. 목표 초과 여부 확인
→ 현재까지의 합·비용이 이미 목표를 넘었는가?
예: 부분집합 합 문제에서 현재 합이 이미 목표를 초과했는가?
원칙 3. 완성 가능성 확인
→ 남은 선택지를 모두 더해도 목표에 도달할 수 없는가?
예: 현재 합 + 남은 원소의 합 < 목표 → 불가능
가지치기 적용 전후 탐색 노드 수 비교
python
import time
# 부분집합 합 문제: [3, 1, 4, 2, 5] 중 합이 7인 부분집합
nums = [3, 1, 4, 2, 5]
target = 7
total_nodes_without_pruning = 0
total_nodes_with_pruning = 0
# 가지치기 없는 완전 탐색
def solve_brute(idx, current_sum, path):
global total_nodes_without_pruning
total_nodes_without_pruning += 1
if current_sum == target:
return True
if idx == len(nums):
return False
return (solve_brute(idx + 1, current_sum + nums[idx], path + [nums[idx]]) or
solve_brute(idx + 1, current_sum, path))
# 가지치기 적용 백트래킹
def solve_backtrack(idx, current_sum, remaining_sum):
global total_nodes_with_pruning
total_nodes_with_pruning += 1
if current_sum == target:
return True
# 가지치기 1: 합 초과
if current_sum > target:
return False
# 가지치기 2: 남은 원소 모두 더해도 목표 미달
if current_sum + remaining_sum < target:
return False
if idx == len(nums):
return False
remaining = remaining_sum - nums[idx]
return (solve_backtrack(idx + 1, current_sum + nums[idx], remaining) or
solve_backtrack(idx + 1, current_sum, remaining))
remaining_total = sum(nums)
solve_brute(0, 0, [])
solve_backtrack(0, 0, remaining_total)
print(f"가지치기 없음: {total_nodes_without_pruning}개 노드 방문")
print(f"가지치기 적용: {total_nodes_with_pruning}개 노드 방문")
print(f"탐색 감소율: {(1 - total_nodes_with_pruning/total_nodes_without_pruning)*100:.1f}%")
가지치기의 시간복잡도 영향
| 문제 | 가지치기 없는 복잡도 | 가지치기 후 평균 복잡도 |
|---|---|---|
| 순열 | O(n!) | O(n!) 최악, 실제 훨씬 빠름 |
| 조합 | O(2ⁿ) | O(2ⁿ) 최악, 실제 훨씬 빠름 |
| N-Queen | O(n!) | O(n! / 상수) |
| 부분집합 합 | O(2ⁿ) | O(2^(n/2)) 이하 |
| 스도쿠 | O(9^81) | 실제 밀리초 수준 |
스도쿠를 예로 들면, 이론적 완전 탐색은 9^81이라는 천문학적 경우의 수이지만, 실제 백트래킹은 유망 함수가 대부분의 경로를 초기에 잘라내어 평균적으로 밀리초 이내에 해를 찾습니다.
4. 백트래킹 핵심 문제 완전 분석 — 순열·조합·부분집합·N-Queen
코딩 테스트에서 반드시 마주치는 네 가지 핵심 백트래킹 문제 유형을 실전 코드와 함께 완전히 분석합니다.
문제 1. 순열(Permutation) — nPr
n개의 원소에서 r개를 순서 있게 선택하는 모든 경우를 구합니다. 같은 원소도 순서가 다르면 다른 경우입니다.
python
def permutations(nums, r):
result = []
used = [False] * len(nums) # 중복 방지 체크 배열
def backtrack(path):
# 종료 조건: r개를 선택했을 때
if len(path) == r:
result.append(path[:]) # 복사본 저장 (참조 아님)
return
for i in range(len(nums)):
if used[i]: # 가지치기: 이미 사용한 원소
continue
used[i] = True # 선택 적용
path.append(nums[i])
backtrack(path) # 재귀
path.pop() # 선택 취소
used[i] = False # 상태 복원
backtrack([])
return result
print(permutations([1, 2, 3], 2))
# [[1,2],[1,3],[2,1],[2,3],[3,1],[3,2]] ← 6가지 (3P2)
# 중복 원소가 있는 경우 — 정렬 후 인접 중복 건너뛰기
def permutations_with_duplicates(nums):
result = []
nums.sort() # 중복 처리를 위해 정렬
used = [False] * len(nums)
def backtrack(path):
if len(path) == len(nums):
result.append(path[:])
return
for i in range(len(nums)):
if used[i]:
continue
# 핵심 가지치기: 같은 값이 이전에 이미 사용됐고
# 이전 값이 취소된 상태라면 → 중복 순열 방지
if i > 0 and nums[i] == nums[i-1] and not used[i-1]:
continue
used[i] = True
path.append(nums[i])
backtrack(path)
path.pop()
used[i] = False
backtrack([])
return result
print(permutations_with_duplicates([1, 1, 2]))
# [[1,1,2],[1,2,1],[2,1,1]] ← 중복 없이 3가지
문제 2. 조합(Combination) — nCr
n개의 원소에서 r개를 순서 없이 선택합니다. 순열과 달리 [1,2]와 [2,1]은 같은 경우입니다.
python
def combinations(nums, r):
result = []
def backtrack(start, path):
# 종료 조건: r개 선택 완료
if len(path) == r:
result.append(path[:])
return
# 핵심 가지치기: start부터 탐색하여 순서 보장 (중복 선택 방지)
# 추가 가지치기: 남은 원소 수 확인
remaining_needed = r - len(path)
remaining_available = len(nums) - start
if remaining_available < remaining_needed: # 더 뽑을 수 없음
return
for i in range(start, len(nums)):
path.append(nums[i])
backtrack(i + 1, path) # i+1로 앞 원소 재선택 방지
path.pop()
backtrack(0, [])
return result
print(combinations([1, 2, 3, 4], 2))
# [[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]] ← 6가지 (4C2)
# 합이 목표인 조합 (Combination Sum)
def combination_sum(candidates, target):
"""같은 원소를 여러 번 사용 가능"""
result = []
candidates.sort() # 정렬로 가지치기 효율 향상
def backtrack(start, path, remaining):
if remaining == 0: # 정확히 목표 합 달성
result.append(path[:])
return
for i in range(start, len(candidates)):
# 가지치기: 현재 값이 이미 남은 목표 초과
if candidates[i] > remaining:
break # 정렬됐으므로 이후도 모두 초과
path.append(candidates[i])
backtrack(i, path, remaining - candidates[i]) # i로 재사용 허용
path.pop()
backtrack(0, [], target)
return result
print(combination_sum([2, 3, 6, 7], 7))
# [[2,2,3],[7]]
문제 3. 부분집합(Subset) — 멱집합
n개의 원소로 만들 수 있는 모든 부분집합(2ⁿ개)을 구합니다.
python
def subsets(nums):
result = []
def backtrack(start, path):
result.append(path[:]) # 모든 노드가 유효한 해 (비어있는 집합 포함)
for i in range(start, len(nums)):
path.append(nums[i])
backtrack(i + 1, path)
path.pop()
backtrack(0, [])
return result
print(subsets([1, 2, 3]))
# [[], [1], [1,2], [1,2,3], [1,3], [2], [2,3], [3]] ← 8가지 (2³)
# 부분집합 합 문제 — 합이 target인 부분집합 존재 여부
def subset_sum_exists(nums, target):
nums.sort() # 정렬로 가지치기 효율 향상
def backtrack(idx, current_sum):
if current_sum == target:
return True
if current_sum > target: # 가지치기 1: 합 초과
return False
if idx == len(nums):
return False
remaining = sum(nums[idx:])
if current_sum + remaining < target: # 가지치기 2: 달성 불가
return False
# 선택: nums[idx] 포함
if backtrack(idx + 1, current_sum + nums[idx]):
return True
# 비선택: nums[idx] 제외
return backtrack(idx + 1, current_sum)
return backtrack(0, 0)
print(subset_sum_exists([3, 1, 4, 2, 5], 7)) # True: [3,4] or [2,5]
문제 4. N-Queen — 백트래킹의 대표 문제
N×N 체스판에 N개의 퀸을 서로 공격하지 않도록 배치하는 경우의 수를 구합니다. 퀸은 같은 행·열·대각선에 있으면 서로 공격합니다.
python
def n_queens(n):
result = []
# 열·대각선 사용 여부를 집합으로 관리 — O(1) 조회
cols = set()
diag1 = set() # 우하향 대각선: (row - col) 일정
diag2 = set() # 우상향 대각선: (row + col) 일정
board = [-1] * n # board[row] = col (퀸의 열 위치)
def backtrack(row):
# 종료 조건: 모든 행에 퀸 배치 완료
if row == n:
result.append(board[:])
return
for col in range(n):
# 유망 함수: 같은 열 또는 대각선에 퀸이 있으면 가지치기
if col in cols:
continue
if (row - col) in diag1:
continue
if (row + col) in diag2:
continue
# 선택 적용
cols.add(col)
diag1.add(row - col)
diag2.add(row + col)
board[row] = col
backtrack(row + 1)
# 선택 취소
cols.remove(col)
diag1.remove(row - col)
diag2.remove(row + col)
board[row] = -1
backtrack(0)
return len(result), result
count, solutions = n_queens(8)
print(f"8-Queen 해의 수: {count}") # 92
# 해 시각화
def visualize_queen(solution, n):
for row in range(n):
line = ""
for col in range(n):
line += "Q " if solution[row] == col else ". "
print(line)
print()
visualize_queen(solutions[0], 8)
# . . . . Q . . .
# . . . . . . Q .
# . . Q . . . . .
# ...
5. 심화 문제 — 스도쿠·단어 탐색·외판원 문제
핵심 패턴을 익혔다면 더 복잡한 제약 조건을 가진 심화 문제에 적용해 보겠습니다.
심화 1. 스도쿠 풀이
9×9 스도쿠를 백트래킹으로 풀기. 각 행·열·3×3 박스에 1~9가 중복 없이 들어가야 합니다.
python
def solve_sudoku(board):
rows = [set() for _ in range(9)]
cols = [set() for _ in range(9)]
boxes = [set() for _ in range(9)]
empty_cells = []
# 초기 상태 파악
for r in range(9):
for c in range(9):
if board[r][c] != 0:
num = board[r][c]
box_idx = (r // 3) * 3 + (c // 3)
rows[r].add(num)
cols[c].add(num)
boxes[box_idx].add(num)
else:
empty_cells.append((r, c))
def backtrack(idx):
# 종료 조건: 모든 빈 칸 채움
if idx == len(empty_cells):
return True
r, c = empty_cells[idx]
box_idx = (r // 3) * 3 + (c // 3)
for num in range(1, 10):
# 유망 함수: 행·열·박스 충돌 검사
if num in rows[r] or num in cols[c] or num in boxes[box_idx]:
continue
# 선택 적용
board[r][c] = num
rows[r].add(num)
cols[c].add(num)
boxes[box_idx].add(num)
if backtrack(idx + 1):
return True # 해 발견 → 즉시 반환
# 선택 취소
board[r][c] = 0
rows[r].remove(num)
cols[c].remove(num)
boxes[box_idx].remove(num)
return False # 이 경로에서 해 없음
backtrack(0)
return board
# 스도쿠 풀이 핵심 최적화:
# 가장 제약이 많은 빈 칸부터 시도 (MRV 휴리스틱)
def find_most_constrained(board, rows, cols, boxes):
min_choices = 10
best_cell = None
for r in range(9):
for c in range(9):
if board[r][c] == 0:
box_idx = (r // 3) * 3 + (c // 3)
choices = 9 - len(rows[r] | cols[c] | boxes[box_idx])
if choices < min_choices:
min_choices = choices
best_cell = (r, c)
if min_choices == 1: # 선택지가 1개면 즉시 선택
return best_cell
return best_cell
심화 2. 단어 탐색 (Word Search)
2D 그리드에서 상하좌우로 연결된 문자들로 특정 단어를 찾습니다.
python
def word_search(board, word):
rows, cols = len(board), len(board[0])
directions = [(0,1),(0,-1),(1,0),(-1,0)]
def backtrack(r, c, idx):
# 종료 조건: 단어 전체 매칭
if idx == len(word):
return True
# 가지치기: 범위 초과 또는 문자 불일치
if r < 0 or r >= rows or c < 0 or c >= cols:
return False
if board[r][c] != word[idx]:
return False
# 선택 적용: 방문 표시 (재방문 방지)
temp = board[r][c]
board[r][c] = "#" # 임시 마킹
for dr, dc in directions:
if backtrack(r + dr, c + dc, idx + 1):
board[r][c] = temp # 복원 후 반환
return True
# 선택 취소: 방문 표시 해제
board[r][c] = temp
return False
for r in range(rows):
for c in range(cols):
if backtrack(r, c, 0):
return True
return False
grid = [
['A','B','C','E'],
['S','F','C','S'],
['A','D','E','E']
]
print(word_search(grid, "ABCCED")) # True
print(word_search(grid, "SEE")) # True
print(word_search(grid, "ABCB")) # False (B 재방문 불가)
심화 3. 외판원 문제(TSP) — 백트래킹 + 한계값 가지치기
모든 도시를 한 번씩 방문하고 돌아오는 최단 경로를 찾습니다.
python
import math
def tsp_backtrack(dist, n):
min_cost = [math.inf]
visited = [False] * n
def backtrack(current, path, cost, depth):
if depth == n: # 모든 도시 방문
# 출발지로 돌아오는 비용 추가
total = cost + dist[current][0]
min_cost[0] = min(min_cost[0], total)
return
for next_city in range(n):
if visited[next_city]:
continue
# 가지치기: 현재 비용이 이미 최솟값 초과
new_cost = cost + dist[current][next_city]
if new_cost >= min_cost[0]: # 한계값(Bound) 가지치기
continue
visited[next_city] = True
backtrack(next_city, path + [next_city], new_cost, depth + 1)
visited[next_city] = False
visited[0] = True
backtrack(0, [0], 0, 1)
return min_cost[0]
# 4개 도시 예시
distance_matrix = [
[0, 10, 15, 20],
[10, 0, 35, 25],
[15, 35, 0, 30],
[20, 25, 30, 0]
]
print(f"최단 경로 비용: {tsp_backtrack(distance_matrix, 4)}") # 80
6. 백트래킹 최적화 전략과 면접 답변 가이드
백트래킹 성능 향상을 위한 5가지 최적화 전략
전략 1. 정렬로 가지치기 효율 향상
→ 원소를 오름차순 정렬하면 "현재 값이 목표 초과" 조건에서
break로 이후 탐색을 한 번에 건너뛸 수 있다
전략 2. MRV 휴리스틱 (Minimum Remaining Values)
→ 가장 선택지가 적은 변수부터 먼저 배치한다
→ 스도쿠에서 선택 가능한 숫자가 1개인 칸 먼저 채우기
전략 3. Forward Checking
→ 선택을 적용하면서 남은 선택지에 영향을 즉시 전파
→ 미래 제약 위반을 미리 감지해 탐색 전에 차단
전략 4. 대칭성 제거
→ 대칭 관계에 있는 해를 하나만 탐색하고 나머지는 복제
→ N-Queen에서 절반만 탐색 후 대칭 해 추가
전략 5. 비트마스크로 집합 연산 최적화
→ visited 배열 대신 정수 하나로 방문 여부 관리
→ 비트 연산으로 O(1) 집합 연산
python
# 비트마스크 순열 — visited 배열 대신 정수 사용
def permutations_bitmask(n):
result = []
path = []
def backtrack(used): # used: 비트마스크로 사용 여부 표현
if len(path) == n:
result.append(path[:])
return
for i in range(n):
if used & (1 << i): # i번째 비트가 1이면 이미 사용
continue
path.append(i + 1)
backtrack(used | (1 << i)) # i번째 비트 ON
path.pop()
backtrack(0)
return result
print(permutations_bitmask(3))
# [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
면접에서 백트래킹 질문 모범 답변
Q: “백트래킹이 무엇인지 설명해 주세요”
“백트래킹은 상태 공간 트리를 DFS로 탐색하면서, 현재 경로가 해가 될 수 없다고 판단되면 즉시 되돌아가 다른 경로를 탐색하는 알고리즘입니다. 완전 탐색과 달리 유망 함수(Promising Function)로 불필요한 경로를 조기에 제거하는 가지치기(Pruning)가 핵심입니다. 재귀로 구현하며, 선택 적용 → 재귀 호출 → 선택 취소의 세 단계가 핵심 패턴입니다.”
Q: “백트래킹과 DFS의 차이가 무엇인가요?”
“DFS는 그래프의 모든 노드를 깊이 우선으로 방문하는 탐색 방법이고, 백트래킹은 DFS를 기반으로 하되 유망하지 않은 노드는 탐색을 중단하는 최적화 전략입니다. DFS는 방문 여부만 관리하지만, 백트래킹은 현재 선택 상태(path)를 유지하고 재귀 후 반드시 상태를 복원합니다.”
Q: “백트래킹의 시간복잡도는 얼마인가요?”
“가지치기 없는 최악의 경우 순열은 O(n!), 조합·부분집합은 O(2ⁿ)입니다. 그러나 유망 함수의 품질에 따라 실제 탐색 노드 수가 이론적 최악 대비 수십~수천 배 적어집니다. 가지치기의 효과는 문제별로 다르므로 ‘최악 O(n!)이지만 평균적으로 훨씬 빠르다’고 답하는 것이 정확합니다.”
백트래킹 문제 접근 체크리스트
문제를 받았을 때 순서대로 확인:
□ 1. 완전 탐색으로 풀 수 있는 문제인가?
(모든 경우의 수 탐색이 필요한가?)
□ 2. 상태 공간을 트리로 그릴 수 있는가?
(각 노드: 현재 선택 상태, 간선: 선택지)
□ 3. 가지치기 조건은 무엇인가?
- 제약 조건 위반?
- 합/비용 초과?
- 완성 불가능?
□ 4. 종료 조건은 무엇인가?
(r개 선택 완료? 목표 합 달성? 모든 칸 채움?)
□ 5. 선택 취소(Undo) 로직이 맞는가?
(상태가 재귀 전으로 완전히 복원되는가?)
□ 6. 중복 처리가 필요한가?
(중복 원소? 순서 무관? → 정렬+인접 중복 건너뛰기)
결론
백트래킹 알고리즘 가지치기의 핵심은 세 가지로 압축됩니다. 첫째, 상태 공간 트리를 DFS로 탐색한다. 둘째, 유망하지 않은 경로는 유망 함수로 즉시 잘라낸다. 셋째, 재귀 후 반드시 선택을 취소하여 상태를 복원한다. 이 세 가지 원칙을 체화하면 순열·조합·N-Queen·스도쿠·단어 탐색 어떤 문제도 같은 골격 코드 위에서 해결할 수 있습니다. 가지치기의 품질이 성능을 결정하므로, 제약 조건 위반·합 초과·완성 불가라는 세 가지 유망 함수 설계 원칙을 문제마다 적용해 보세요. 오늘 바로 N-Queen 문제를 직접 구현하고, 가지치기 전후 탐색 노드 수를 직접 측정해보는 것부터 시작해 보세요.
답글 남기기