순열과 조합
중복 원소가 있는 경우와 없는 경우에 대해 리스트의 모든 순열을 열거하고, 모든 k-조합과 조합 합 변형을 생성합니다.
순열과 조합은(는) CoddyKit의 무료 DSA Interview Prep 강의입니다. 이것은 4개 중 3번째 강의입니다. 아래에서 전체 강의를 무료로 읽을 수 있으며, 내장 코드 에디터와 24/7 AI 튜터와 함께 브라우저에서 직접 실습할 수 있습니다. 이 강의는 DSA Interview Prep 학습 경로의 일부이며, 진행 상황이 웹과 CoddyKit 앱에 동기화됩니다. DSA Interview Prep 강의에는 총 4개의 강의가 포함되어 있습니다.
순열과 조합 비교
순열은 순서가 중요한 배열입니다. [1,2,3]과 [3,2,1]은 서로 다릅니다. n개 항목의 순열 개수는 n!입니다. 조합은 순서가 중요하지 않은 선택입니다. {1,2}를 선택하는 것과 {2,1}을 선택하는 것은 같습니다. n개 항목에서 k개를 선택하는 조합의 개수는 C(n,k) = n! / (k! × (n-k)!)입니다. 순열과 조합은 모두 개수 세기, 열거, 선택과 관련된 면접 문제에서 필수적인 패턴입니다.
import math
# Permutations
n = 4
print(f'Permutations of {n} items: {math.factorial(n)}')
# 4! = 24
# Combinations
for k in range(n+1):
print(f'C({n},{k}) = {math.comb(n,k)}')
# C(4,0)=1, C(4,1)=4, C(4,2)=6, C(4,3)=4, C(4,4)=1
# Sum = 2^4 = 16 (total subsets)모든 순열 생성
현재 경로에 어떤 원소가 포함되어 있는지 추적하려면 used 불리언 배열을 사용합니다. 각 단계에서 아직 사용하지 않은 모든 원소를 시도합니다. 탐색이 끝나면 해당 원소를 다시 사용하지 않은 상태로 표시합니다. 부분집합과 달리 순열은 원소를 어떤 순서로든 사용할 수 있으므로 start 인덱스가 없습니다. len(path) == n이 되면 재귀를 종료합니다.
def permutations(nums):
result = []
used = [False] * len(nums)
def backtrack(path):
if len(path) == len(nums):
result.append(list(path))
return
for i, num in enumerate(nums):
if not used[i]:
used[i] = True # CHOOSE
path.append(num)
backtrack(path) # EXPLORE
path.pop() # UNCHOOSE
used[i] = False
backtrack([])
return result
print(permutations([1, 2, 3]))
# [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]교환 기반 순열
또 다른 방법은 위치 start의 원소를 start부터 n-1까지의 각 원소와 교환하고, 재귀 호출을 한 다음 다시 교환하는 것입니다. 이 방식은 used 배열 없이 배열을 제자리에서 수정합니다. 핵심은 각 수준에서 start의 왼쪽에 있는 모든 원소가 고정되어 있고, 위치 start에 어떤 원소를 배치할지 선택한다는 점입니다. 이 방식은 메모리 효율이 조금 더 높으며 힙 알고리즘의 기반이 됩니다.
def permutations_swap(nums):
result = []
def backtrack(start):
if start == len(nums):
result.append(list(nums))
return
for i in range(start, len(nums)):
nums[start], nums[i] = nums[i], nums[start] # CHOOSE (swap)
backtrack(start + 1) # EXPLORE
nums[start], nums[i] = nums[i], nums[start] # UNCHOOSE (swap back)
backtrack(0)
return result
print(permutations_swap([1, 2, 3]))
# Same 6 permutations, different order순열 II: 중복 값 처리
입력에 중복 값이 있으면(예: [1, 1, 2]) used 배열 방식은 중복 순열을 생성합니다. 해결 방법은 배열을 정렬한 다음, 이전의 동일한 원소가 이번 재귀 호출에서 사용되지 않았다면 중복 값을 건너뛰는 것입니다. 조건은 if i > 0 and nums[i] == nums[i-1] and not used[i-1]: continue입니다. 이렇게 하면 중복 값이 항상 왼쪽에서 오른쪽 순서로 선택됩니다.
def permutations_unique(nums):
nums.sort()
result = []
used = [False] * len(nums)
def backtrack(path):
if len(path) == len(nums):
result.append(list(path))
return
for i in range(len(nums)):
if used[i]: continue
# Skip if this num is a duplicate and the previous dup was not used
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_unique([1, 1, 2]))
# [[1,1,2],[1,2,1],[2,1,1]] — 3, not 6다음 순열(사전순)
다음 순열(LeetCode 31)은 배열을 사전순으로 더 큰 다음 순열로 제자리에서 변환합니다. 알고리즘은 다음과 같습니다. (1) nums[i] < nums[i+1]인 가장 오른쪽 인덱스 i를 찾습니다. (2) nums[j] > nums[i]인 가장 오른쪽 인덱스 j를 찾습니다. (3) nums[i]와 nums[j]를 교환합니다. (4) 인덱스 i 뒤의 접미 부분을 뒤집습니다. 이러한 i가 없으면 배열 전체를 뒤집습니다(가장 작은 순열로 순환합니다).
def next_permutation(nums):
n = len(nums)
# Step 1: find rightmost i where nums[i] < nums[i+1]
i = n - 2
while i >= 0 and nums[i] >= nums[i+1]:
i -= 1
if i >= 0:
# Step 2: find rightmost j where nums[j] > nums[i]
j = n - 1
while nums[j] <= nums[i]:
j -= 1
# Step 3: swap
nums[i], nums[j] = nums[j], nums[i]
# Step 4: reverse suffix after i
nums[i+1:] = nums[i+1:][::-1]
return nums
print(next_permutation([1, 2, 3])) # [1,3,2]
print(next_permutation([3, 2, 1])) # [1,2,3] (wraps)
print(next_permutation([1, 1, 5])) # [1,5,1]k-조합 백트래킹
n개 원소에서 k개를 선택하는 모든 조합을 생성합니다(LeetCode 77). 부분집합과 같이 시작 인덱스를 사용하여 원소를 다시 방문하지 않도록 하고 정렬된 순서를 유지합니다. k - len(path)개보다 적은 원소가 남으면 가지치기합니다. 조건은 if len(nums) - i + 1 < k - len(path): break입니다. 이는 앞에서 살펴본 combine(n, k)과 동일하지만 실제 배열에서 동작합니다.
def combinations(nums, k):
result = []
def backtrack(start, path):
if len(path) == k:
result.append(list(path))
return
for i in range(start, len(nums)):
# Pruning: not enough elements left
if len(nums) - i < k - len(path):
break
path.append(nums[i])
backtrack(i + 1, path)
path.pop()
backtrack(0, [])
return result
print(combinations([1,2,3,4,5], 3))
# 10 combinations: C(5,3)
import math
print(math.comb(5,3)) # 10조합 합: 무제한 재사용
조합 합(LeetCode 39)에서는 각 숫자를 횟수 제한 없이 사용할 수 있습니다. 일반적인 조합과 다른 점은 시작 인덱스를 i+1로 이동하는 대신 i를 전달하여 현재 원소를 다시 사용할 수 있도록 한다는 것입니다. 가지치기 방법은 다음과 같습니다. 남은 목표값이 0이 되면 경로를 기록하고, 음수가 되면 중단합니다. 정렬하면 남은 모든 후보가 남은 목표값보다 커지는 순간 일찍 종료할 수 있습니다.
def combination_sum(candidates, target):
candidates.sort()
result = []
def backtrack(start, path, remaining):
if remaining == 0:
result.append(list(path))
return
for i in range(start, len(candidates)):
c = candidates[i]
if c > remaining: break # all remaining are too big
path.append(c)
backtrack(i, path, remaining - c) # reuse allowed: pass i, not i+1
path.pop()
backtrack(0, [], target)
return result
print(combination_sum([2, 3, 6, 7], 7))
# [[2,2,3],[7]]조합 합 II: 재사용 없음, 중복 값 포함
조합 합 II(LeetCode 40)에서는 각 숫자를 최대 한 번만 사용하지만 입력에 중복 값이 포함될 수 있습니다. 두 가지 기법을 결합합니다. start를 i+1로 이동하여 재사용을 막고, 정렬한 후 같은 수준에서 중복 값을 건너뜁니다(if i > start and nums[i] == nums[i-1]: continue). 이는 부분집합 II의 중복 처리 방식과 조합의 재사용 없음 제약을 결합한 것입니다.
def combination_sum_ii(candidates, target):
candidates.sort()
result = []
def backtrack(start, path, remaining):
if remaining == 0:
result.append(list(path))
return
for i in range(start, len(candidates)):
if candidates[i] > remaining: break
# Skip duplicates at same level
if i > start and candidates[i] == candidates[i-1]:
continue
path.append(candidates[i])
backtrack(i + 1, path, remaining - candidates[i]) # no reuse: i+1
path.pop()
backtrack(0, [], target)
return result
print(combination_sum_ii([10,1,2,7,6,1,5], 8))
# [[1,1,6],[1,2,5],[1,7],[2,6]]전화번호의 문자 조합
문자 조합(LeetCode 17)은 전화 키패드의 각 숫자를 문자에 대응시키고, 주어진 숫자 문자열에서 가능한 모든 문자 조합을 생성합니다. 각 위치에서 숫자에 대응하는 문자 중 하나를 선택하고 재귀 호출하는 백트래킹 문제입니다. 길이가 n이고 숫자당 평균 k개의 문자가 있는 문자열의 시간 복잡도는 O(kⁿ)입니다.
def letter_combinations(digits):
if not digits: return []
phone = {
'2': 'abc', '3': 'def', '4': 'ghi', '5': 'jkl',
'6': 'mno', '7': 'pqrs', '8': 'tuv', '9': 'wxyz'
}
result = []
def backtrack(index, path):
if index == len(digits):
result.append(''.join(path))
return
for letter in phone[digits[index]]:
path.append(letter)
backtrack(index + 1, path)
path.pop()
backtrack(0, [])
return result
print(letter_combinations('23'))
# ['ad','ae','af','bd','be','bf','cd','ce','cf']순열과 조합 비교
핵심적인 구조 차이는 다음과 같습니다. 순열 — 시작 인덱스가 없고, 재사용을 막기 위해 used 배열이나 교환을 사용하며, 트리의 각 수준에서 n개의 선택지가 있고 총 n!개의 리프가 있습니다. 조합 — 순서를 강제하기 위해 시작 인덱스를 사용하며 C(n,k)개의 리프가 있습니다. 조합 합 — 재사용을 위해 시작 인덱스를 이동하지 않고 목표값을 기준으로 가지치기합니다. 새로운 문제를 이 세 가지 형태 중 하나에 대응시키면 적절한 틀을 즉시 선택할 수 있습니다.
# Pattern summary:
# Permutations: for i in range(n); if not used[i]; no start advancement
# Combinations: for i in range(start, n); advance start → i+1
# Combo Sum (reuse): for i in range(start, n); advance start → i (same)
# Quick reference:
import math
n = 5
print(f'Perm({n}) = n! = {math.factorial(n)}')
print(f'Comb({n},2) = C(n,k) = {math.comb(n,2)}')
print(f'Comb({n},3) = {math.comb(n,3)}')
# Also: subsets = sum(C(n,k) for k=0..n) = 2^n
print(f'Subsets({n}) = 2^n = {2**n}')복잡도와 면접 팁
열거의 시간 복잡도는 순열이 O(n × n!), 조합이 O(k × C(n,k)), 조합 합이 O(n^(T/min_val))입니다. 공간 복잡도는 재귀 깊이에 대해 O(n)이고 결과에 대해 O(출력)입니다. 핵심 팁은 다음과 같습니다. (1) 순서가 중요한지 항상 확인하십시오(순열인지 조합인지). (2) 질문을 받기 전에 중복 처리 방법을 언급하십시오. (3) 가지치기 조건을 항상 명시적으로 설명하십시오. (4) n이 큰 경우 출력 자체가 지수적이라는 점을 언급하십시오. 문제의 결과를 모두 출력해야 한다면 이 알고리즘은 최적입니다.
import math
# Complexity for n=10
n = 10
print(f'Permutations(10): {math.factorial(n):,} results')
print(f'Combinations(10,5): {math.comb(n,5):,} results')
print(f'Subsets(10): {2**n:,} results')
# For interview: state which pattern
# 'This is a combinations problem because order doesnt matter'
# 'I will use a start index to avoid revisiting elements'
# 'Pruning: when sum exceeds target, break (after sorting)'빠른 확인
이번 학습에서 다룬 자료 구조 및 알고리즘 — 코딩 면접 준비 개념에 대한 이해도를 확인해 보십시오.
학습 내용 복습
이번 학습에서 다음을 배웠습니다. 순열은 used 배열과 시작 인덱스 없이 n!개의 배열을 생성합니다. 조합은 재사용을 막기 위해 이동하는 시작 인덱스를 사용하여 C(n,k)개의 선택을 생성합니다. 또한 두 문제의 중복 값은 정렬한 다음 같은 재귀 수준에서 반복되는 값을 건너뛰어 처리합니다. 다음에는 백트래킹을 N-퀸 문제에 적용하고 제약 전파를 살펴봅니다.
자주 묻는 질문
“순열과 조합” 강의는 무료인가요?
네 — “순열과 조합” 전체 내용을 이 웹사이트에서 무료로 읽을 수 있습니다. 인터랙티브하게 실습하려면(내장 코드 에디터와 24/7 AI 튜터), CoddyKit PRO로 업그레이드하면 DSA Interview Prep 강의 전체를 잠금 해제할 수 있습니다. DSA Interview Prep 강의에는 총 4개의 강의가 포함되어 있습니다.
“순열과 조합”에서 뭘 배우나요?
중복 원소가 있는 경우와 없는 경우에 대해 리스트의 모든 순열을 열거하고, 모든 k-조합과 조합 합 변형을 생성합니다. 브라우저에서 직접 실행하는 실습 코드로 DSA Interview Prep을(를) 배우며, 24/7 AI 튜터가 강의를 진행하면서 질문에 답변해줍니다.
DSA Interview Prep을(를) 시작하는 데 경험이 필요한가요?
사전 경험은 필요하지 않습니다. CoddyKit의 DSA Interview Prep은(는) 초급자부터 고급 학습자까지를 위해 구성되어 있으므로, 여기서 시작하거나 처음부터 시작할 수 있으며 자신의 속도대로 진행할 수 있습니다. 이것은 4개 중 3번째 강의입니다.
“순열과 조합” 강의는 얼마나 걸리나요?
대부분의 CoddyKit 강의는 약 5~10분이 소요됩니다. 각 강의는 간결하고 인터랙티브하여 꾸준한 진행이 가능하며, 웹과 앱에서 중단한 부분부터 바로 시작할 수 있습니다.
이 DSA Interview Prep 강의에서 코드를 작성하고 실행할 수 있나요?
네. 모든 DSA Interview Prep 강의에는 내장 코드 에디터가 포함되어 있으므로, 브라우저에서 바로 실제 코드를 작성하고 실행한 후 즉시 AI 피드백을 받을 수 있습니다 — 로컬 설정이 필요 없습니다.