알고리즘
Advanced Combinatorics고급 조합론
고급 조합론은 유한 구조의 존재, 개수, 최적화를 연구하는 수학이다. 순열, 조합, 생성 함수, 포함-배제 원리, 라몬-비트 이론이 알고리즘 분석과 암호학의 기반이 된다.
핵심 공식 정리
순열 P(n,k) = n! / (n-k)! : n개에서 k개를 순서 있게 선택
조합 C(n,k) = n! / (k!(n-k)!) : n개에서 k개를 순서 없이 선택
이항 정리:
(x+y)^n = Σ C(n,k) x^k y^(n-k) for k=0 to n
다항 정리:
(x1+x2+...+xm)^n = Σ n!/(k1!k2!...km!) x1^k1...xm^km
조건: k1+k2+...+km = n
카탈란 수 C_n = C(2n,n)/(n+1):
C_0=1, C_1=1, C_2=2, C_3=5, C_4=14, ...
→ 괄호 쌍 개수, 이진 트리 개수, 삼각형 분할 수포함-배제 원리
python
from itertools import combinations
from functools import reduce
def inclusion_exclusion(sets: list) -> int:
"""포함-배제 원리로 합집합 크기 계산"""
n = len(sets)
total = 0
for k in range(1, n + 1):
for combo in combinations(range(n), k):
intersection = reduce(set.intersection,
[sets[i] for i in combo])
total += (-1)**(k+1) * len(intersection)
return total
# 예시: 1~100 중 2 또는 3 또는 5의 배수 개수
A = set(range(2, 101, 2)) # 2의 배수
B = set(range(3, 101, 3)) # 3의 배수
C = set(range(5, 101, 5)) # 5의 배수
result = inclusion_exclusion([A, B, C])
print(f"|A∪B∪C| = {result}")
# 검증
print(f"실제: {len(A | B | C)}")생성 함수 응용
python
from fractions import Fraction
def count_ways_change(n: int, coins: list) -> int:
"""동전 거스름돈 경우의 수 (생성 함수 / DP)"""
dp = [0] * (n + 1)
dp[0] = 1
for coin in coins:
for amount in range(coin, n + 1):
dp[amount] += dp[amount - coin]
return dp[n]
# 1, 5, 10, 25원으로 41원 만드는 방법의 수
result = count_ways_change(41, [1, 5, 10, 25])
print(f"거스름돈 경우의 수: {result}")
