Ch.9 재귀와 백트래킹
백트래킹 — 가지치기, Subsets
모든 경우를 다 해보되, **막히면 되돌아온다**
미로에서 갈림길을 만나면 한 방향을 선택합니다. 막다른 길이면 되돌아와서 다른 방향을 시도합니다. 이것이 백트래킹입니다.
모든 경우의 수를 다 탐색하면 너무 느리지 않을까?
가지치기(Pruning)로 불필요한 경로를 미리 잘라내면 효율적입니다.
핵심 개념
백트래킹 (Backtracking)
해를 찾는 과정에서 막히면 이전 단계로 되돌아가는 탐색 기법
가지치기 (Pruning)
조건에 맞지 않는 경로를 미리 잘라내어 탐색 범위를 줄이는 기법
핵심 내용
미로를 탈출하는 방법을 생각해봅시다
갈림길에서 왼쪽을 선택 → 막다른 길 → 되돌아와서 오른쪽 선택 → 출구 발견!
백트래킹 = 선택 → 탐색 → 실패 시 되돌리기(undo)를 반복하는 패턴
백트래킹 문제의 90%는 이 템플릿 하나로 풀 수 있습니다
def backtrack(path, choices):
# 1. 종료 조건 (정답 찾았으면 저장)
if is_solution(path):
result.append(path[:])
return
# 2. 선택지 순회
for choice in choices:
# 3. 가지치기 (조건 불만족 시 건너뛰기)
if not is_valid(choice):
continue
path.append(choice) # 4. 선택
backtrack(path, choices) # 5. 재귀 탐색
path.pop() # 6. 되돌리기 (undo)핵심 3단계: 선택(choose) → 탐색(explore) → 되돌리기(unchoose) path.append() → backtrack() → path.pop()
Subsets: 배열의 모든 부분집합을 구하라 nums = [1, 2, 3]
각 원소에 대해 "포함 vs 미포함" 두 가지 선택. 3개 원소 → 2³ = 8개 부분집합
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) # 탐색 (i+1: 중복 방지)
path.pop() # 되돌리기
backtrack(0, [])
return result
# [[], [1], [1,2], [1,2,3], [1,3], [2], [2,3], [3]]start 매개변수가 핵심입니다. i+1부터 시작하므로 [1,2]와 [2,1]처럼 중복을 방지합니다
시간 복잡도: O(n × 2ⁿ) — 2ⁿ개 부분집합 × 각 복사 O(n) 공간 복잡도: O(n) — 재귀 깊이
원소에 중복이 있으면? nums = [1, 2, 2]
def subsetsWithDup(nums):
result = []
nums.sort() # 정렬이 핵심!
def backtrack(start, path):
result.append(path[:])
for i in range(start, len(nums)):
# 가지치기: 같은 레벨에서 같은 값 건너뛰기
if i > start and nums[i] == nums[i-1]:
continue
path.append(nums[i])
backtrack(i + 1, path)
path.pop()
backtrack(0, [])
return result가지치기 조건: `i > start and nums[i] == nums[i-1]` 같은 재귀 레벨에서 같은 값을 두 번 선택하지 않는다 반드시 정렬 후 적용해야 동작합니다
가지치기가 없으면 탐색 공간이 기하급수적으로 커집니다
Subsets II [1,2,2,2] 예시: 가지치기 없이: 16개 경로 탐색 → 중복 제거 필요 가지치기 적용: 8개 경로만 탐색 → 바로 정답 원소가 많을수록 차이가 기하급수적으로 커집니다
면접 팁: 백트래킹 풀이를 제시할 때 항상 가지치기 조건을 함께 설명하라. "불필요한 경로를 잘라냅니다"
백트래킹에서 '되돌리기'에 해당하는 코드는?
nums = [1,2,3]의 부분집합은 총 몇 개인가?
핵심 용어
백트래킹
막히면 이전 단계로 되돌아가는 탐색 기법
가지치기
불필요한 경로를 미리 잘라내어 탐색 범위 축소
결정 트리
각 선택지를 노드로 표현한 탐색 공간의 트리
시각 자료
퀴즈와 인터랙션으로 더 깊이 학습하세요
play_circle인터랙티브 레슨 시작