1. 재귀 함수 설계 원칙
재귀란 무엇인가
함수가 자기 자신을 호출하는 방식으로 문제를 더 작은 같은 구조의 문제로 쪼개는 기법이다.
거울 두 개를 마주 보게 세우면 그 안에서 거울이 무한히 반복된다. 다만 프로그래밍에서 무한 반복은 곧 RecursionError다. 반드시 멈추는 조건이 있어야 한다.
팩토리얼이 가장 직관적인 예시다:
5! = 5 × 4!
4! = 4 × 3!
3! = 3 × 2!
2! = 2 × 1!
1! = 1 ← 여기서 멈춘다
def factorial(n):
if n <= 1:
return 1
return n * factorial(n - 1)
재귀 설계 3단계
재귀 함수를 작성할 때 세 가지를 순서대로 결정한다.
1단계: 부분 문제 정의
─────────────────────────────────────────────
"큰 문제를 같은 구조의 작은 문제로 어떻게 쪼갤 수 있는가?"
factorial(n) = n × factorial(n-1)
fibonacci(n) = fibonacci(n-1) + fibonacci(n-2)
sum(n) = n + sum(n-1)
2단계: 기저 조건 설정
─────────────────────────────────────────────
"더 이상 쪼갤 수 없는 가장 작은 경우는 무엇인가?"
factorial: n <= 1 이면 1
fibonacci: n <= 1 이면 n
sum: n == 0 이면 0
3단계: 수렴 확인
─────────────────────────────────────────────
"재귀 호출마다 입력이 반드시 기저 조건 방향으로 줄어드는가?"
factorial(n) → factorial(n-1) → ... → factorial(1) [수렴]
fibonacci(n) → fibonacci(n-1) + fibonacci(n-2) [수렴]
f(n) → f(n+1) → ... [발산, 무한 재귀]
기저 조건을 잘못 설정한 경우:
def bad_factorial(n):
if n == 0: # n이 음수로 들어오면 0을 지나쳐 무한 재귀
return 1
return n * bad_factorial(n - 1)
bad_factorial(-1) # RecursionError
def good_factorial(n):
if n <= 1: # 음수와 0을 모두 처리
return 1
return n * good_factorial(n - 1)
재귀 호출 스택 시각화
재귀 함수가 호출될 때 내부적으로 어떤 일이 벌어지는지 스택 프레임 레벨에서 추적한다.
factorial(4) 실행 과정:
호출 단계 (스택 프레임이 쌓임):
─────────────────────────────────
factorial(4) → 4 × factorial(3) [대기]
factorial(3) → 3 × factorial(2) [대기]
factorial(2) → 2 × factorial(1) [대기]
factorial(1) → 1 [반환]
factorial(2) → 2 × 1 = 2 [반환]
factorial(3) → 3 × 2 = 6 [반환]
factorial(4) → 4 × 6 = 24 [반환]
메모리 내 콜 스택:
────────────────────────────────────────
[호출 시] [반환 시]
┌─────────────┐ ┌─────────────┐
│ factorial(1)│ │ │
├─────────────┤ ├─────────────┤
│ factorial(2)│ → │ │
├─────────────┤ ├─────────────┤
│ factorial(3)│ │ │
├─────────────┤ ├─────────────┤
│ factorial(4)│ │ factorial(4)│ → 24
└─────────────┘ └─────────────┘
(스택 최대 깊이) (하나씩 팝)
n번 호출 → 스택 깊이 n → Python 기본 한도 1000 초과 시 RecursionError
fibonacci(4) 호출 트리 (중복 호출 확인):
fibonacci(4)
├── fibonacci(3)
│ ├── fibonacci(2)
│ │ ├── fibonacci(1) → 1
│ │ └── fibonacci(0) → 0
│ └── fibonacci(1) → 1
└── fibonacci(2) ← 이미 위에서 계산했다
├── fibonacci(1) → 1
└── fibonacci(0) → 0
중복 호출이 n이 커질수록 기하급수적으로 증가한다:
n=10 → 177번 호출
n=20 → 21,891번 호출
n=30 → 2,692,537번 호출
n=40 → 331,160,281번 호출
n=50 → 40,730,022,147번 호출
메모이제이션으로 중복 제거
한 번 계산한 결과를 저장해두고 재사용한다.
import functools
@functools.cache
def fibonacci(n):
if n <= 1:
return n
return fibonacci(n - 1) + fibonacci(n - 2)
메모이제이션 적용 후 호출 횟수:
n=10 → 11번 호출
n=50 → 51번 호출
n=100 → 101번 호출
각 n에 대해 정확히 한 번만 계산한다. 시간 복잡도가 O(2^n)에서 O(n)으로 떨어진다.
@functools.cache는 Python 3.9+에서 사용 가능하다. 이전 버전은 @functools.lru_cache(maxsize=None)을 사용한다.
재귀 vs 반복문 선택 기준
| 구분 | 재귀 | 반복문 |
|---|---|---|
| 코드 가독성 | 문제 구조가 드러남 | 상태 변수 직접 관리 |
| 메모리 | 호출마다 스택 프레임 생성 | 스택 사용 없음 |
| 성능 | 중복 호출 있으면 느림 | 일반적으로 빠름 |
| 적합한 경우 | 트리, 그래프, 분할 정복 | 단순 반복 |
트리나 그래프처럼 구조 자체가 재귀적으로 정의된 경우에는 재귀가 자연스럽다. 단순히 1부터 n까지 더하는 것을 재귀로 작성하면 오히려 복잡해진다.
같은 문제를 재귀와 반복문으로:
def sum_recursive(n):
if n == 0:
return 0
return n + sum_recursive(n - 1)
def sum_iterative(n):
total = 0
for i in range(1, n + 1):
total += i
return total
단순 합산은 반복문이 간결하고 빠르다. 재귀는 스택 공간을 n만큼 사용한다.
분할 정복형 재귀: 하노이 탑
하노이 탑은 재귀의 힘이 극적으로 드러나는 문제다. n개의 원판을 A에서 C로 옮기되, 작은 원판이 항상 위에 있어야 한다.
규칙:
- 한 번에 원판 하나만 이동
- 큰 원판이 작은 원판 위에 올라갈 수 없음
- 세 개의 기둥 A, B, C 사용
n=3일 때 이동 순서:
A→C, A→B, C→B, A→C, B→A, B→C, A→C (총 7번)
n개이면 2^n - 1번
핵심 아이디어: n개를 옮기는 문제를 (n-1)개를 옮기는 문제 두 번으로 쪼갠다.
n개를 A→C로 옮기는 방법:
1단계: 위의 (n-1)개를 A→B로 옮긴다 (B를 임시 기둥으로 사용)
2단계: 가장 큰 원판 하나를 A→C로 옮긴다
3단계: (n-1)개를 B→C로 옮긴다 (A를 임시 기둥으로 사용)
def hanoi(n, source, target, auxiliary):
if n == 1:
print(f"{source} → {target}")
return
hanoi(n - 1, source, auxiliary, target)
print(f"{source} → {target}")
hanoi(n - 1, auxiliary, target, source)
hanoi(3, 'A', 'C', 'B')
A → C
A → B
C → B
A → C
B → A
B → C
A → C
코드가 단 7줄이지만, 이 구조를 반복문으로 작성하면 매우 복잡해진다. 재귀가 자연스러운 대표적 사례다.
Python 재귀 한도와 실전 대응
Python 기본 재귀 깊이 한도는 1000이다.
import sys
print(sys.getrecursionlimit()) # 1000
코딩 테스트에서 그래프 DFS를 재귀로 구현할 때 노드 수가 많으면 한도를 초과한다.
import sys
sys.setrecursionlimit(100000) # 파일 최상단에 배치
100,000 ~ 200,000이 일반적이다. 너무 큰 값을 설정하면 메모리 초과가 발생할 수 있다.
재귀를 반복문으로 변환해 한도 자체를 피하는 방법도 있다:
def dfs_recursive(graph, start):
visited = set()
order = []
def dfs(node):
visited.add(node)
order.append(node)
for neighbor in graph[node]:
if neighbor not in visited:
dfs(neighbor)
dfs(start)
return order
def dfs_iterative(graph, start):
visited = set()
order = []
stack = [start]
while stack:
node = stack.pop()
if node in visited:
continue
visited.add(node)
order.append(node)
for neighbor in reversed(graph[node]):
if neighbor not in visited:
stack.append(neighbor)
return order
graph = {1: [2, 3], 2: [4], 3: [4], 4: []}
print(dfs_recursive(graph, 1)) # [1, 2, 4, 3]
print(dfs_iterative(graph, 1)) # [1, 2, 4, 3]
재귀 순서를 그대로 유지하려면 이웃 노드를 reversed() 순서로 스택에 넣는다. 스택은 LIFO이므로 나중에 넣은 것이 먼저 꺼내진다.
2. 브루트포스 완전 탐색
완전 탐색이란
가능한 모든 경우를 직접 확인하는 전략이다. 최적 알고리즘을 찾기 어렵거나, 범위가 작아서 시간 안에 통과할 수 있을 때 선택한다.
완전 탐색은 항상 정답을 보장한다. 효율을 희생하되 정확성을 얻는 전략이다. 코딩 테스트에서는 먼저 완전 탐색으로 정답을 확인한 다음 최적화를 검토하는 접근이 효과적이다.
적용 가능 범위 판단:
Python 기준 1초에 약 10^7 ~ 10^8 연산이 가능하다.
경우의 수 <= 약 10^7 → 완전 탐색 시도
경우의 수 > 10^7 → 다른 접근법 필요 (DP, 그리디 등)
경우의 수 크기 감각
| n | n! (순열) | 2^n (부분집합) | C(n, n/2) (최대 조합) |
|---|---|---|---|
| 5 | 120 | 32 | 10 |
| 8 | 40,320 | 256 | 70 |
| 10 | 3,628,800 | 1,024 | 252 |
| 11 | 39,916,800 | 2,048 | 462 |
| 12 | 479,001,600 | 4,096 | 924 |
| 15 | 1.3조 | 32,768 | 3,003 |
| 20 | 2.4 × 10^18 | 1,048,576 | 184,756 |
| 25 | 연산 불가 | 33,554,432 | 5,200,300 |
| 30 | 연산 불가 | 1,073,741,824 | 155,117,520 |
실전 기준:
- 순열(n!): n <= 10~11이 한계
- 부분 집합(2^n): n <= 20~25가 한계
- 조합 C(n,r): 직접 계산해서 10^7 이하인지 확인
순열 (Permutation)
n개에서 r개를 순서 있게 나열하는 모든 경우다. P(n,r) = n! / (n-r)!
[1, 2, 3]의 전체 순열 (P(3,3) = 3! = 6가지):
[1,2,3] [1,3,2] [2,1,3] [2,3,1] [3,1,2] [3,2,1]
Decision Tree 시각화 -- [1, 2, 3]에서 2개 순열 (P(3,2) = 6가지):
[ ]
/ | \
[1] [2] [3]
/ \ / \ / \
[1,2] [1,3] [2,1] [2,3] [3,1] [3,2]
(답) (답) (답) (답) (답) (답)
각 레벨에서 이미 선택한 원소를 제외한 나머지만 자식 노드로 확장한다.
itertools 사용:
from itertools import permutations
nums = [1, 2, 3]
for perm in permutations(nums):
print(perm)
(1, 2, 3)
(1, 3, 2)
(2, 1, 3)
(2, 3, 1)
(3, 1, 2)
(3, 2, 1)
r개만 선택하는 경우:
from itertools import permutations
nums = [1, 2, 3, 4]
perms_2 = list(permutations(nums, 2))
print(f"P(4,2) = {len(perms_2)}가지") # P(4,2) = 12가지
print(perms_2[:4]) # [(1, 2), (1, 3), (1, 4), (2, 1)]
방문 배열로 직접 구현:
def generate_permutations(nums):
result = []
visited = [False] * len(nums)
def backtrack(current):
if len(current) == len(nums):
result.append(current[:])
return
for i in range(len(nums)):
if not visited[i]:
visited[i] = True
current.append(nums[i])
backtrack(current)
current.pop()
visited[i] = False
backtrack([])
return result
print(generate_permutations([1, 2, 3]))
[[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]
visited[i] = True / False와 current.append / pop이 항상 짝을 이룬다. 이것이 백트래킹의 핵심 동작이다.
slicing으로 구현 (방문 배열 없이):
def generate_permutations_slice(nums):
result = []
def backtrack(current, remaining):
if not remaining:
result.append(current[:])
return
for i in range(len(remaining)):
current.append(remaining[i])
backtrack(current, remaining[:i] + remaining[i+1:])
current.pop()
backtrack([], nums)
return result
remaining[:i] + remaining[i+1:]로 선택한 원소를 제외한 나머지를 다음 재귀에 넘긴다. 직관적이지만 슬라이싱마다 새 리스트를 생성하므로 방문 배열 방식보다 메모리 효율이 낮다.
조합 (Combination)
n개에서 r개를 순서 없이 선택하는 모든 경우다. C(n,r) = n! / (r! × (n-r)!)
[1, 2, 3, 4]에서 2개 선택 (C(4,2) = 6가지):
(1,2) (1,3) (1,4) (2,3) (2,4) (3,4)
[1,2]와 [2,1]은 같은 것이다. 순열과 달리 순서가 중요하지 않다.
순열 vs 조합 비교:
[1, 2, 3]에서 2개:
순열: (1,2) (1,3) (2,1) (2,3) (3,1) (3,2) → 6가지
조합: (1,2) (1,3) (2,3) → 3가지
차이: 조합 = 순열 / r!
C(3,2) = P(3,2) / 2! = 6 / 2 = 3
Decision Tree 시각화 -- [1, 2, 3, 4]에서 2개 조합:
[ ]
/ / \ \
[1] [2] [3] [4]
/ | \ | \ |
[1,2][1,3][1,4] [2,3][2,4] [3,4]
(답) (답) (답) (답) (답) (답)
각 노드에서 현재 인덱스보다 큰 인덱스의 원소만 자식으로 확장한다.
[1]의 자식: [2], [3], [4]
[2]의 자식: [3], [4] ← 1은 이미 탐색했으므로 제외
[3]의 자식: [4]
[4]의 자식: 없음
itertools 사용:
from itertools import combinations
nums = [1, 2, 3, 4]
for comb in combinations(nums, 2):
print(comb)
(1, 2)
(1, 3)
(1, 4)
(2, 3)
(2, 4)
(3, 4)
재귀로 직접 구현:
def generate_combinations(nums, r):
result = []
def backtrack(start, current):
if len(current) == r:
result.append(current[:])
return
for i in range(start, len(nums)):
current.append(nums[i])
backtrack(i + 1, current)
current.pop()
backtrack(0, [])
return result
print(generate_combinations([1, 2, 3, 4], 2))
[[1, 2], [1, 3], [1, 4], [2, 3], [2, 4], [3, 4]]
순열 구현과의 차이는 딱 하나다. 순열은 모든 인덱스를 탐색하지만, 조합은 start 이후 인덱스만 탐색한다. backtrack(i + 1, ...)이 이것을 담당한다.
순열: for i in range(len(nums)) → 모든 인덱스
조합: for i in range(start, len(nums)) → start 이후 인덱스만
부분 집합 (Subset)
n개의 원소로 만들 수 있는 모든 부분 집합이다. 총 2^n가지다. 각 원소가 포함되거나 포함되지 않는 두 가지 선택이 있기 때문이다.
[1, 2, 3]의 부분 집합 (2^3 = 8가지):
[] [1] [2] [3] [1,2] [1,3] [2,3] [1,2,3]
비트마스크로 구현:
n=3일 때 mask 0~7까지 각각 어떤 부분 집합인지:
mask 이진수 선택된 인덱스 부분 집합
0 000 없음 []
1 001 0 [1]
2 010 1 [2]
3 011 0,1 [1, 2]
4 100 2 [3]
5 101 0,2 [1, 3]
6 110 1,2 [2, 3]
7 111 0,1,2 [1, 2, 3]
def subsets_bitmask(nums):
n = len(nums)
result = []
for mask in range(1 << n):
subset = [nums[i] for i in range(n) if mask & (1 << i)]
result.append(subset)
return result
print(subsets_bitmask([1, 2, 3]))
[[], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3]]
mask & (1 << i)는 mask의 i번째 비트가 1인지 확인하는 연산이다. 1이면 nums[i]를 부분 집합에 포함한다.
비트 연산 시각화:
mask = 5, i = 0 검사:
5 = 101
1 = 001 (1 << 0)
AND = 001 → 1 (0번 인덱스 포함)
mask = 5, i = 1 검사:
5 = 101
2 = 010 (1 << 1)
AND = 000 → 0 (1번 인덱스 제외)
mask = 5, i = 2 검사:
5 = 101
4 = 100 (1 << 2)
AND = 100 → 4 (2번 인덱스 포함)
결과: 인덱스 0, 2 선택 → nums[0]=1, nums[2]=3 → [1, 3]
재귀로 구현:
def subsets_recursive(nums):
result = []
def backtrack(start, current):
result.append(current[:])
for i in range(start, len(nums)):
current.append(nums[i])
backtrack(i + 1, current)
current.pop()
backtrack(0, [])
return result
조합과 달리 기저 조건에서 반환하지 않는다. 모든 단계에서 현재 상태를 결과에 추가한다. 빈 집합부터 전체 집합까지 모든 크기의 부분 집합이 자연스럽게 생성된다.
포함/미포함 이진 트리 시각화 -- [1, 2, 3]:
[]
/ \
1 포함 1 미포함
[1] []
/ \ / \
2 포함 2 미포함 2 포함 2 미포함
[1,2] [1] [2] []
/ \ / \ / \ / \
3포함 3미포함 3포함 3미포함 3포함 3미포함 3포함 3미포함
[1,2,3] [1,2] [1,3] [1] [2,3] [2] [3] []
각 원소에 대해 포함/미포함 두 가지 선택 → 깊이 n이면 2^n개의 리프 노드
중복 허용 경우
중복 순열: 같은 원소를 여러 번 선택할 수 있고, 순서도 중요하다.
from itertools import product
for p in product([1, 2, 3], repeat=2):
print(p, end=" ")
(1,1) (1,2) (1,3) (2,1) (2,2) (2,3) (3,1) (3,2) (3,3)
n자리 자물쇠 비밀번호처럼 각 자리에서 독립적으로 선택하는 문제에 적합하다. 총 3^2 = 9가지다.
중복 조합: 같은 원소를 여러 번 선택할 수 있지만, 순서는 중요하지 않다.
from itertools import combinations_with_replacement
for c in combinations_with_replacement([1, 2, 3], 2):
print(c, end=" ")
(1,1) (1,2) (1,3) (2,2) (2,3) (3,3)
일반 조합(3가지)보다 많고, 중복 순열(9가지)보다 적다.
비교 정리:
| 유형 | 함수 | [1,2,3]에서 2개 | 경우의 수 |
|---|---|---|---|
| 순열 | permutations(nums, r) |
(1,2)(1,3)(2,1)(2,3)(3,1)(3,2) | P(3,2) = 6 |
| 조합 | combinations(nums, r) |
(1,2)(1,3)(2,3) | C(3,2) = 3 |
| 중복 순열 | product(nums, repeat=r) |
(1,1)(1,2)...(3,3) | 3^2 = 9 |
| 중복 조합 | combinations_with_replacement(nums, r) |
(1,1)(1,2)(1,3)(2,2)(2,3)(3,3) | H(3,2) = 6 |
3. 시간 복잡도 정리
| 알고리즘 | 시간 복잡도 | 설명 |
|---|---|---|
| 순열 생성 | O(P(n,r)) | r=n이면 O(n!) |
| 조합 생성 | O(C(n,r)) | |
| 부분 집합 생성 | O(2^n) | |
| 피보나치 (재귀) | O(2^n) | 중복 호출 |
| 피보나치 (메모이제이션) | O(n) | 각 n에 대해 한 번만 계산 |
4. Python 메서드 정리
| 메서드 | 용도 | 예시 |
|---|---|---|
permutations(it, r) |
순열 생성 | permutations([1,2,3], 2) |
combinations(it, r) |
조합 생성 | combinations([1,2,3], 2) |
product(it, repeat=r) |
중복 순열 | product([1,2,3], repeat=2) |
combinations_with_replacement(it, r) |
중복 조합 | combinations_with_replacement([1,2,3], 2) |
sys.setrecursionlimit(n) |
재귀 한도 설정 | sys.setrecursionlimit(100000) |
@functools.cache |
메모이제이션 | @functools.cache 데코레이터 |
list[:] |
리스트 복사 | result.append(current[:]) |
5. 연습 문제
입문 (브론즈 ~ 실버 하위)
| 번호 | 문제 | 난이도 | 링크 | 핵심 접근 |
|---|---|---|---|---|
| 10872 | 팩토리얼 | 브론즈 2 | https://www.acmicpc.net/problem/10872 | 기저 조건 설계, n <= 1이면 1 반환 |
| 10870 | 피보나치 수 5 | 브론즈 2 | https://www.acmicpc.net/problem/10870 | 재귀 호출 트리 구조 파악, n<=30이므로 메모이제이션 불필요 |
| 2798 | 블랙잭 | 브론즈 2 | https://www.acmicpc.net/problem/2798 | n<=100, 3개 조합 완전 탐색, C(100,3)=161,700 |
| 1476 | 날짜 계산 | 브론즈 1 | https://www.acmicpc.net/problem/1476 | 세 주기(15×28×19) 완전 탐색, 최대 7,980번 확인 |
| 11729 | 하노이 탑 이동 순서 | 실버 1 | https://www.acmicpc.net/problem/11729 | 분할 정복형 재귀, n개 = (n-1)개 이동 두 번 + 원판 하나 이동 |
핵심 (실버)
| 번호 | 문제 | 난이도 | 링크 | 핵심 접근 |
|---|---|---|---|---|
| 15649 | N과 M (1) | 실버 3 | https://www.acmicpc.net/problem/15649 | 순열 백트래킹 기본, 방문 배열 패턴 |
| 15650 | N과 M (2) | 실버 3 | https://www.acmicpc.net/problem/15650 | 조합 백트래킹 기본, start 인덱스로 중복 제거 |
| 1182 | 부분수열의 합 | 실버 2 | https://www.acmicpc.net/problem/1182 | N<=20이므로 2^20 부분 집합 탐색, 합 조건 확인 |
| 14501 | 퇴사 | 실버 3 | https://www.acmicpc.net/problem/14501 | 날별 선택/미선택 재귀, N<=15이므로 2^15 완전 탐색 |
프로그래머스
| 문제 | 난이도 | 링크 | 핵심 접근 |
|---|---|---|---|
| 최소직사각형 | Lv 1 | https://school.programmers.co.kr/learn/courses/30/lessons/86491 | 각 명함을 가로/세로 두 방향으로 완전 탐색 |
| 소수 찾기 | Lv 2 | https://school.programmers.co.kr/learn/courses/30/lessons/42839 | 숫자 조각으로 만들 수 있는 순열 생성 + 소수 판별 |
| 카펫 | Lv 2 | https://school.programmers.co.kr/learn/courses/30/lessons/42842 | 가능한 가로/세로 크기를 완전 탐색, 조건 만족 확인 |
백트래킹 & 실전 전략
1. 백트래킹: 가지치기 전략
완전 탐색에서 백트래킹으로
완전 탐색은 모든 경우를 확인한다. 백트래킹은 완전 탐색을 하되 불필요한 탐색을 조기에 중단하는 기법이다.
탐색 중간에 현재 경로가 답이 될 수 없다는 것을 발견하면, 더 깊이 탐색하지 않고 이전 단계로 돌아가 다른 방향을 시도한다. 이것을 가지치기(pruning)라고 한다.
가지치기의 효과:
4-Queens 문제 (4×4 체스판에 퀸 4개 배치):
완전 탐색: 4^4 = 256가지 모두 확인
백트래킹: 실제 탐색 노드 수 약 50개
N-Queens 문제 (N=8):
완전 탐색: 8^8 = 16,777,216가지
백트래킹: 실제 탐색 노드 수 약 2,000개 (99.99% 감소)
가지치기 조건이 강할수록 탐색 노드 수가 극적으로 줄어든다.
재귀 + 가지치기 기본 패턴
백트래킹 코드의 전형적인 구조다.
def backtrack(상태):
if 기저_조건: # 답을 찾은 경우
result.append(현재_답[:])
return
for 다음_선택 in 가능한_선택들:
if 가지치기_조건: # 이 방향은 답이 될 수 없다
continue
선택_적용() # 상태 변경
backtrack(다음_상태) # 재귀 탐색
선택_취소() # 상태 복원 (undo)
선택과 취소는 반드시 짝을 이룬다. 취소가 없으면 이전 선택이 남아있어 다른 경로를 올바르게 탐색할 수 없다.
선택/취소 패턴 3가지:
# 패턴 1: 리스트 append/pop
current.append(nums[i])
backtrack(...)
current.pop()
# 패턴 2: 방문 배열 True/False
visited[i] = True
backtrack(...)
visited[i] = False
# 패턴 3: set add/remove
cols.add(col)
backtrack(...)
cols.remove(col)
세 패턴 모두 동일한 원칙이다. 상태를 변경하고 탐색한 뒤, 정확히 이전 상태로 되돌린다.
가지치기 전략 3가지
전략 1: 현재 상태 검증
지금까지의 선택이 제약 조건을 위반하지 않는지 확인한다. 위반하면 이 경로의 모든 자식 노드를 탐색할 필요가 없다.
예시: N-Queens에서 퀸 배치
현재 행에 퀸을 놓으려는 열이 이미 다른 퀸과 같은 열 또는 대각선에 있으면
→ 이 선택부터 그 아래 모든 배치는 이미 무효
→ continue로 이 열을 건너뜀
if col in cols or (row - col) in diag1 or (row + col) in diag2:
continue
전략 2: 미래 가능성 검증
현재까지는 제약을 만족하지만, 이 방향으로 계속 가면 답이 나올 수 없는 경우를 미리 탐지한다.
예시: 합이 target인 부분 집합 찾기 (배열이 정렬된 경우)
현재 누적 합 + 다음 원소 > target이면
→ 이미 초과했으므로 이후 원소는 더 클 것 (정렬 조건)
→ break로 반복문 전체를 종료
nums.sort()
for i in range(start, len(nums)):
if current_sum + nums[i] > target:
break # 이후 원소는 더 크므로 중단
current.append(nums[i])
backtrack(i + 1, current_sum + nums[i])
current.pop()
전략 3: 범위 검증
남은 선택지 수가 목표를 달성하기에 부족한 경우를 미리 탐지한다.
예시: n개 중 r개를 뽑는 조합
현재까지 k개를 선택했고 start 인덱스부터 탐색한다면
남은 원소 수: n - start
더 필요한 원소 수: r - k
남은 원소 수 < 더 필요한 원소 수 → 절대 r개를 채울 수 없음
def backtrack(start, current):
if len(current) == r:
result.append(current[:])
return
remaining_needed = r - len(current)
remaining_available = len(nums) - start
if remaining_available < remaining_needed:
return # 원소가 부족하므로 중단
for i in range(start, len(nums)):
current.append(nums[i])
backtrack(i + 1, current)
current.pop()
N-Queens 전체 탐색 시각화
4×4 체스판에 퀸 4개를 서로 공격하지 않게 배치한다. 퀸은 가로, 세로, 대각선을 모두 공격한다.
퀸 충돌 조건:
같은 열: col_A == col_B
왼쪽 대각선: row_A - col_A == row_B - col_B (row - col이 같으면 같은 대각선)
오른쪽 대각선: row_A + col_A == row_B + col_B (row + col이 같으면 같은 대각선)
4-Queens 탐색 과정 (첫 번째 해 찾기):
행 0에서 (0,0) 선택:
Q . . .
. . . .
. . . .
. . . .
행 1 탐색:
(1,0): 열 충돌 (col=0 이미 사용) [가지치기]
(1,1): 대각선 충돌 (0-0 = 0 = 1-1) [가지치기]
(1,2): 통과 → 행 2 탐색으로 진입
(1,3): 통과 (나중에 탐색)
(0,0)→(1,2) 선택된 상태:
Q . . .
. . Q .
. . . .
. . . .
행 2 탐색:
(2,0): 통과 → 행 3 탐색으로 진입
(2,1): 대각선 충돌 (1-2 = -1 = 2-1? 아님. 0-0=0, 1-2=-1, 2+1=3, 0+0=0, 1+2=3) → 오른쪽 대각선 충돌 [가지치기]
(2,2): 열 충돌 (col=2 이미 사용) [가지치기]
(2,3): 대각선 충돌 (0-0=0, 2-3=-1 다름. 0+0=0, 2+3=5 다름. 1-2=-1, 2-3=-1 같음) → 왼쪽 대각선 충돌 [가지치기]
(0,0)→(1,2)→(2,0) 선택된 상태:
Q . . .
. . Q .
Q . . .
. . . .
행 3 탐색:
(3,0): 열 충돌 (col=0 이미 사용) [가지치기]
(3,1): 통과 → 답 발견!
(3,2): 대각선 충돌 [가지치기]
(3,3): 대각선 충돌 [가지치기]
첫 번째 해:
Q . . .
. . Q .
Q . . .
. Q . . ← 이 배치는 유효한가? (0,0), (1,2), (2,0), (3,1)
→ (0,0)과 (2,0)이 같은 열(0)! 유효하지 않다
(실제로는 (2,0)에서 이미 (0,0)과 열 충돌로 가지치기해야 한다)
올바른 첫 번째 해:
. Q . .
. . . Q
Q . . .
. . Q . ← (0,1), (1,3), (2,0), (3,2)
N-Queens 구현:
def n_queens(n):
result = 0
cols = set()
diag1 = set()
diag2 = set()
def backtrack(row):
nonlocal result
if row == n:
result += 1
return
for col in range(n):
if col in cols or (row - col) in diag1 or (row + col) in diag2:
continue
cols.add(col)
diag1.add(row - col)
diag2.add(row + col)
backtrack(row + 1)
cols.remove(col)
diag1.remove(row - col)
diag2.remove(row + col)
backtrack(0)
return result
print(n_queens(4)) # 2
print(n_queens(8)) # 92
diag1은 row - col이 같은 위치들이 같은 \ 방향 대각선에 있다는 성질을 이용한다. diag2는 row + col이 같은 위치들이 같은 / 방향 대각선에 있다는 성질을 이용한다. set 사용으로 충돌 확인이 O(1)이다.
합이 target인 조합: 백트래킹 + 가지치기 완성 예시
def combination_sum(nums, target):
result = []
nums.sort() # 가지치기를 위해 정렬
def backtrack(start, current, remaining):
if remaining == 0:
result.append(current[:])
return
for i in range(start, len(nums)):
if nums[i] > remaining: # 현재 원소가 이미 남은 합 초과
break # 정렬되어 있으므로 이후도 초과
current.append(nums[i])
backtrack(i, current, remaining - nums[i])
current.pop()
backtrack(0, [], target)
return result
print(combination_sum([2, 3, 6, 7], 7))
[[2, 2, 3], [7]]
if nums[i] > remaining: break가 미래 가능성 검증 가지치기다. 정렬 없이 continue를 사용하면 이후에 더 작은 값이 있을 수 있어 break를 사용할 수 없다.
스도쿠: 제약 전파 + 백트래킹
스도쿠도 백트래킹의 대표적인 문제다. 빈 칸에 1~9를 넣되, 같은 행/열/3×3 박스에 중복이 없어야 한다.
탐색 방식:
빈 칸을 순서대로 탐색
1~9를 하나씩 시도
유효하면 다음 빈 칸으로 진행
어떤 숫자도 들어갈 수 없으면 → 백트래킹
def solve_sudoku(board):
def is_valid(row, col, num):
for i in range(9):
if board[row][i] == num:
return False
if board[i][col] == num:
return False
box_row, box_col = 3 * (row // 3), 3 * (col // 3)
for i in range(box_row, box_row + 3):
for j in range(box_col, box_col + 3):
if board[i][j] == num:
return False
return True
def backtrack():
for i in range(9):
for j in range(9):
if board[i][j] == 0:
for num in range(1, 10):
if is_valid(i, j, num):
board[i][j] = num
if backtrack():
return True
board[i][j] = 0 # 백트래킹
return False # 어떤 숫자도 불가 → 실패
return True # 빈 칸 없음 → 성공
backtrack()
return board
N-Queens와 구조가 동일하다. 빈 칸마다 선택 → 유효하면 다음 칸으로 진입 → 막히면 되돌아가기.
2. 코딩테스트 실전 전략
문제 유형 판별 플로우
문제를 받으면 다음 순서로 접근 방법을 결정한다.
┌─ Step 1: N 크기 확인 ──────────────────────────────────────────────┐
│ │
│ N <= 8~10 → 순열 완전 탐색 (N! 허용) │
│ N <= 20~25 → 부분 집합 / 비트마스크 (2^N 허용) │
│ N이 크지만 │
│ 제약 조건이 강함 → 백트래킹 (실제 탐색 노드 수 < 이론값) │
│ N <= 1,000 → O(N^2) 이하 탐색 or 다른 접근 │
│ N > 10,000 → DP / 그리디 / 이분 탐색 │
└─────────────────────────────────────────────────────────────────────┘
┌─ Step 2: 문제 키워드 확인 ─────────────────────────────────────────┐
│ │
│ "모든 순서", "경우의 수", "최소/최대 경로" → 순열 완전 탐색 │
│ "n개 중 r개 선택", "팀 구성", "조합" → 조합 완전 탐색 │
│ "부분 합", "가능한 조합", "합이 X" → 부분 집합 탐색 │
│ "배치", "제약 조건 만족", "색칠" → 백트래킹 │
│ "최적 배치", "퍼즐" → 백트래킹 + 가지치기 │
└─────────────────────────────────────────────────────────────────────┘
┌─ Step 3: 경우의 수 계산 ───────────────────────────────────────────┐
│ │
│ 선택한 접근법의 최악 경우의 수를 직접 계산 │
│ 10^7 이하면 완전 탐색 시도 │
│ 초과하면 가지치기 추가 또는 접근법 변경 │
└─────────────────────────────────────────────────────────────────────┘
시간 복잡도 기반 판단표
| 접근법 | 시간 복잡도 | Python 1초 내 최대 N |
|---|---|---|
| 전체 순열 | O(N!) | N <= 10~11 |
| 부분 집합 | O(2^N) | N <= 23~25 |
| 조합 C(N, N/2) | O(C(N, N/2)) | N별로 계산 필요 |
| 백트래킹 (강한 가지치기) | O(실제 탐색 노드) | 문제에 따라 N이 커도 가능 |
| O(N^2) | O(N^2) | N <= 10,000 |
| O(N log N) | O(N log N) | N <= 1,000,000 |
N 크기별 허용 경우의 수:
1초 제한 / Python 기준 약 10^7~10^8 연산:
N = 8 → 8! = 40,320 (순열 가능)
N = 10 → 10! = 3,628,800 (순열 가능, 주의)
N = 11 → 11! = 39,916,800 (순열 한계)
N = 20 → 2^20 = 1,048,576 (부분 집합 가능)
N = 25 → 2^25 = 33,554,432 (부분 집합 한계)
자주 하는 실수 5가지
실수 1: 결과 저장 시 참조 저장
results = []
current = [1, 2, 3]
results.append(current) # 참조 저장
current.append(4)
print(results) # [[1, 2, 3, 4]] - 같이 바뀜!
results.append(current[:]) # 복사본 저장
current.append(4)
print(results) # [[1, 2, 3]] - 독립적
중첩 리스트면 copy.deepcopy(current)가 필요하다. 1차원 리스트는 current[:]로 충분하다.
실수 2: 선택 취소 누락
def backtrack(current):
if len(current) == 3:
print(current)
return
for i in range(n):
if not visited[i]:
visited[i] = True
current.append(nums[i])
backtrack(current)
current.pop() # 이 줄이 없으면 current가 계속 커짐
visited[i] = False # 이 줄이 없으면 원소를 재사용 못 함
append와 pop, visited[i] = True와 visited[i] = False는 반드시 쌍을 이룬다.
실수 3: 기저 조건 범위 오류
def factorial(n):
if n == 0: # n이 음수면 0을 지나쳐 무한 재귀
return 1
def factorial(n):
if n <= 0: # 올바름: 음수와 0 모두 처리
return 1
재귀 함수를 작성할 때 입력 범위 전체를 고려해 기저 조건을 설정한다.
실수 4: 재귀 한도 미설정
import sys
sys.setrecursionlimit(100000) # 파일 최상단에 배치
def dfs(node):
...
그래프 노드 수나 트리 깊이가 1000을 초과할 가능성이 있으면 미리 설정한다.
실수 5: 정렬 없이 break 가지치기 사용
nums = [3, 1, 4, 1, 5]
for x in nums:
if x > target:
break # 3 이후 1이 나올 수 있으므로 잘못된 가지치기
nums.sort() # 정렬 먼저
for x in nums:
if x > target:
break # 정렬 후에는 이후 원소도 모두 크므로 올바름
break로 가지치기하려면 정렬이 선행 조건이다.
빈출 패턴 정리
패턴 1: 순열로 최솟값/최댓값 찾기
from itertools import permutations
min_cost = float('inf')
for perm in permutations(nodes):
cost = calculate_cost(perm)
min_cost = min(min_cost, cost)
모든 순서를 시도하는 전형적인 패턴이다. n이 10 이하인 경우에 사용한다.
패턴 2: 방문 배열 + 백트래킹
visited = [False] * n
def backtrack(depth):
if depth == target_depth:
result.append(path[:])
return
for i in range(n):
if not visited[i]:
visited[i] = True
path.append(nums[i])
backtrack(depth + 1)
path.pop()
visited[i] = False
순열 생성, 경로 탐색 등 "이미 선택한 원소를 다시 선택하지 않아야" 하는 경우에 사용한다.
패턴 3: start 인덱스 + 백트래킹
def backtrack(start, current):
if len(current) == r:
result.append(current[:])
return
for i in range(start, n):
current.append(nums[i])
backtrack(i + 1, current) # i+1: 현재 이후만 탐색 (조합)
current.pop()
조합 생성처럼 "순서는 무관하고 선택만 중요한" 경우에 사용한다.
패턴 4: 누적 값으로 조기 가지치기
nums.sort()
def backtrack(start, current, total):
if total == target:
result.append(current[:])
return
for i in range(start, len(nums)):
if total + nums[i] > target:
break # 이후 원소는 더 크므로 중단
current.append(nums[i])
backtrack(i + 1, current, total + nums[i])
current.pop()
합, 비용, 거리 등 누적 값이 제약을 초과하면 더 탐색할 필요가 없는 경우에 사용한다.
패턴 5: 제약 집합으로 O(1) 검증
used_cols = set()
used_diag1 = set()
used_diag2 = set()
def backtrack(row):
for col in range(n):
if col in used_cols or ...:
continue
used_cols.add(col)
backtrack(row + 1)
used_cols.remove(col)
충돌/중복 확인이 빈번하게 발생하는 경우, 리스트 순회 O(n) 대신 set O(1)로 처리한다.
3. 완전 탐색 접근법 비교
같은 문제를 서로 다른 방식으로 풀어보며 접근법 차이를 비교한다.
문제: 1~N에서 M개를 중복 없이 순서 있게 나열 (백준 15649)
import sys
input = sys.stdin.readline
n, m = map(int, input().split())
result = []
visited = [False] * (n + 1)
def backtrack(current):
if len(current) == m:
print(*current)
return
for i in range(1, n + 1):
if not visited[i]:
visited[i] = True
current.append(i)
backtrack(current)
current.pop()
visited[i] = False
backtrack([])
접근법 2: itertools 사용
from itertools import permutations
n, m = map(int, input().split())
for perm in permutations(range(1, n + 1), m):
print(*perm)
두 접근법 모두 같은 결과를 낸다. itertools는 간결하지만, 직접 구현하면 중간 단계에서 가지치기를 추가할 수 있다.
문제: 합이 S인 부분 수열 존재 여부 (백준 1182 변형)
방법 1: 비트마스크
def count_subsets_with_sum(nums, s):
n = len(nums)
count = 0
for mask in range(1 << n):
total = sum(nums[i] for i in range(n) if mask & (1 << i))
if total == s:
count += 1
return count
방법 2: 재귀 백트래킹 (가지치기 없음)
def count_subsets_with_sum(nums, s):
count = 0
def backtrack(idx, total):
nonlocal count
if idx == len(nums):
if total == s:
count += 1
return
backtrack(idx + 1, total + nums[idx]) # 포함
backtrack(idx + 1, total) # 미포함
backtrack(0, 0)
return count
방법 3: 재귀 백트래킹 (가지치기 추가)
def count_subsets_with_sum(nums, s):
nums.sort()
count = 0
total_sum = sum(nums)
def backtrack(idx, current_sum):
nonlocal count
if current_sum == s:
count += 1
if idx == len(nums):
return
remaining_sum = sum(nums[idx:])
if current_sum + remaining_sum < s: # 최대로 더해도 s 미달
return
if current_sum > s: # 이미 초과
return
backtrack(idx + 1, current_sum + nums[idx])
backtrack(idx + 1, current_sum)
backtrack(0, 0)
return count
비교:
| 방법 | 시간 복잡도 | 가지치기 | 적합한 경우 |
|---|---|---|---|
| 비트마스크 | O(2^n × n) | 없음 | n <= 20, 간단 구현 |
| 재귀 (가지치기 없음) | O(2^n) | 없음 | 구조 이해용 |
| 재귀 (가지치기 있음) | O(2^n) 최악, 실제는 훨씬 빠름 | 있음 | n이 크거나 성능 필요 시 |
4. 시간 복잡도 정리
| 알고리즘 | 시간 복잡도 | 설명 |
|---|---|---|
| 완전 탐색 (순열) | O(N!) | N <= 10~11 |
| 완전 탐색 (부분 집합) | O(2^N) | N <= 20~25 |
| N-Queens | O(N!) 최악, 실제는 훨씬 작음 | 가지치기로 대폭 감소 |
| 스도쿠 | O(9^(빈 칸 수)) 최악 | 가지치기로 대폭 감소 |
| 합이 target인 조합 | O(2^N) 최악 | 정렬 + 가지치기로 감소 |
백트래킹의 이론적 최악 시간 복잡도는 완전 탐색과 같다. 실제 성능은 가지치기 조건의 품질에 달려 있다.
5. 연습 문제
핵심 (실버)
| 번호 | 문제 | 난이도 | 링크 | 핵심 접근 |
|---|---|---|---|---|
| 15649 | N과 M (1) | 실버 3 | https://www.acmicpc.net/problem/15649 | 순열 백트래킹 기본, 방문 배열 패턴 |
| 15650 | N과 M (2) | 실버 3 | https://www.acmicpc.net/problem/15650 | 조합 백트래킹 기본, start 인덱스 패턴 |
| 15651 | N과 M (3) | 실버 3 | https://www.acmicpc.net/problem/15651 | 중복 순열, visited 없이 구현 |
| 15652 | N과 M (4) | 실버 3 | https://www.acmicpc.net/problem/15652 | 중복 조합, backtrack(i, ...) 로 같은 인덱스 재사용 |
| 1182 | 부분수열의 합 | 실버 2 | https://www.acmicpc.net/problem/1182 | 2^N 부분 집합 탐색, 합 조건 확인 |
심화 (골드)
| 번호 | 문제 | 난이도 | 링크 | 핵심 접근 |
|---|---|---|---|---|
| 9663 | N-Queen | 골드 4 | https://www.acmicpc.net/problem/9663 | 열/대각선 set으로 O(1) 충돌 확인, 백트래킹 |
| 1759 | 암호 만들기 | 골드 5 | https://www.acmicpc.net/problem/1759 | 조합 생성 + 모음 최소 1개 / 자음 최소 2개 필터링 |
| 2580 | 스도쿠 | 골드 4 | https://www.acmicpc.net/problem/2580 | 빈 칸 순서대로 1~9 시도, 행/열/박스 충돌 확인, 백트래킹 |
| 6603 | 로또 | 실버 2 | https://www.acmicpc.net/problem/6603 | 7개 이상 후보 중 6개 조합 생성 |
프로그래머스
| 문제 | 난이도 | 링크 | 핵심 접근 |
|---|---|---|---|
| 피로도 | Lv 2 | https://school.programmers.co.kr/learn/courses/30/lessons/87946 | 던전 방문 순서 순열 완전 탐색, 최소 피로도 조건으로 가지치기 |
| 양궁대회 | Lv 2 | https://school.programmers.co.kr/learn/courses/30/lessons/92342 | 10개 과녁에 화살 분배, 부분 집합 + 조건 검증 |
| 외벽 점검 | Lv 3 | https://school.programmers.co.kr/learn/courses/30/lessons/60062 | 친구 순열 × 취약 지점 순열, 완전 탐색 + 조건 검증 |
'CodingTest > 자료구조-알고리즘' 카테고리의 다른 글
| [DFS & BFS] (0) | 2026.03.31 |
|---|---|
| 해시 (Hash) (1) | 2026.03.17 |
| 큐 (Queue) (1) | 2026.03.17 |
| 스택 (Stack) (0) | 2026.03.17 |
| 연결 리스트 (Linked List) (0) | 2026.03.16 |