Ch.9 재귀와 백트래킹
순열과 조합 — Permutations, Combinations
순서가 중요하면 **순열**, 중요하지 않으면 **조합**
3명 중 2명을 줄 세우는 것과 팀을 뽑는 것은 다릅니다. AB와 BA는 순열에서는 다르지만 조합에서는 같습니다.
코드로는 어떻게 구분할까? 백트래킹 템플릿에서 어디가 달라질까?
순열은 visited 배열, 조합은 start 인덱스 — 이 한 가지 차이만 기억하면 됩니다.
핵심 개념
순열 (Permutation)
순서가 중요한 나열. n개 중 r개를 뽑아 줄 세우기
조합 (Combination)
순서 무관한 선택. n개 중 r개를 뽑기
핵심 내용
A, B, C 세 명 중 두 명을 선택하는 방법
코드 차이 한 줄: 순열 → visited[] 사용, 조합 → start 인덱스 사용
Permutations: [1,2,3]의 모든 순열을 구하라
def permute(nums):
result = []
def backtrack(path, used):
if len(path) == len(nums):
result.append(path[:])
return
for i in range(len(nums)):
if used[i]: # 이미 사용한 원소 건너뛰기
continue
used[i] = True # 사용 표시
path.append(nums[i]) # 선택
backtrack(path, used) # 탐색
path.pop() # 되돌리기
used[i] = False # 사용 해제
backtrack([], [False] * len(nums))
return result
# [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]used[i] 배열로 이미 선택한 원소를 추적합니다. 매번 0부터 순회하므로 순서가 달라집니다
시간: O(n! × n) — n!개 순열 × 각 복사 공간: O(n) — 재귀 깊이 + used 배열
Combinations: n=4, k=2일 때 모든 조합을 구하라
def combine(n, k):
result = []
def backtrack(start, path):
if len(path) == k:
result.append(path[:])
return
for i in range(start, n + 1):
path.append(i) # 선택
backtrack(i + 1, path) # 다음부터 탐색
path.pop() # 되돌리기
backtrack(1, [])
return result
# [[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]]start = i + 1이므로 이전 원소를 다시 선택하지 않습니다. [1,2]와 [2,1]은 같은 조합이므로 하나만 생성됩니다
두 코드의 결정적 차이를 나란히 비교합니다
# ── 순열: 매번 0부터, visited로 체크 ──
for i in range(len(nums)):
if used[i]: continue
# → [1,2,3], [1,3,2], [2,1,3] ...
# ── 조합: start부터, 앞쪽 원소 건너뜀 ──
for i in range(start, len(nums)):
# → [1,2], [1,3], [2,3] ...면접 분류 공식: "순서 중요?" → 순열 (visited 배열) "순서 무관?" → 조합 (start 인덱스) "원소 중복 허용?" → start를 i+1이 아닌 i로 설정
입력에 중복 원소가 있으면? nums = [1, 1, 2]
def permuteUnique(nums):
result = []
nums.sort() # 정렬 필수!
def backtrack(path, used):
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, used)
path.pop()
used[i] = False
backtrack([], [False] * len(nums))
return result
# [[1,1,2],[1,2,1],[2,1,1]]not used[i-1] 조건이 핵심. 같은 값의 이전 원소를 아직 사용하지 않았다면, 현재 원소도 건너뛴다
[1,2,3]의 순열(Permutation)은 총 몇 개인가?
순열과 조합의 코드 차이에서 조합이 사용하는 것은?
Permutations 문제의 시간 복잡도는?
핵심 용어
순열 (P)
AB, BA, AC, CA, BC, CB → 6가지 (순서 구분)
조합 (C)
AB, AC, BC → 3가지 (순서 무관)
시각 자료
퀴즈와 인터랙션으로 더 깊이 학습하세요
play_circle인터랙티브 레슨 시작