순열과 조합

완전 탐색을 할지 말지는 "경우가 몇 개인가"에 달려 있다. 그 수를 세는 기본 도구가 순열과 조합이다. 둘의 차이는 하나뿐이다. 뽑은 것의 순서를 구분하면 순열, 구분하지 않으면 조합이다.

순열: 순서가 있는 나열

서로 다른 n개를 한 줄로 세우는 방법의 수를 P(n, n)이라 하자. 첫 자리에 올 것을 고르는 방법이 n가지이고, 남은 n−1개를 세우는 방법은 P(n−1, n−1)이다.

P(n, n) = n × P(n−1, n−1),   P(1, 1) = 1
→ P(n, n) = n × (n−1) × … × 1 = n!

n개 중 r개만 골라 세우는 P(n, r)은 앞의 r자리만 채우고 멈춘 것이다. n개를 모두 세우는 일을 "앞 r자리 세우기"와 "나머지 n−r자리 세우기"로 나누면

n! = P(n, r) × (n−r)!
→ P(n, r) = n! / (n−r)!  = n × (n−1) × … × (n−r+1)

예: 10명 중 회장·부회장·총무를 뽑는 방법은 10 × 9 × 8 = 720.

조합: 순서가 없는 선택

r개를 골라 줄 세우는 일은 "r개를 고르기(조합)"와 "고른 r개를 세우기(r!)"로 나뉜다.

C(n, r) × r! = P(n, r)
→ C(n, r) = n! / (r! (n−r)!)

예: 10명 중 대표 3명을 뽑는 방법은 720 / 3! = 120. 같은 세 사람을 어떤 순서로 뽑았든 한 가지로 센다.

성질 두 가지가 자주 쓰인다.

대칭: C(n, r) = C(n, n−r). r개를 고르는 것은 남길 n−r개를 고르는 것과 같다.
파스칼 점화식: C(n, r) = C(n−1, r−1) + C(n−1, r). 특정 원소 하나를 기준으로 "그것을 뽑는 경우"와 "안 뽑는 경우"로 나눈 것이다. 초기값은 C(n, 0) = C(n, n) = 1.

파스칼 삼각형과 이항 정리

파스칼 점화식을 표로 채우면 파스칼 삼각형이 된다. 각 수는 바로 위 두 수의 합이다.

n=0:          1
n=1:        1   1
n=2:      1   2   1
n=3:    1   3   3   1
n=4:  1   4   6   4   1

n번째 줄은 (a + b)^n을 전개한 계수와 같다. 이것이 이항 정리다.

(a + b)^n = Σ_{r=0..n} C(n, r) · a^(n−r) · b^r

(a+b)를 n번 곱할 때 각 괄호에서 a와 b 중 하나를 고르는데, b를 r번 고르는 방법이 C(n, r)가지라서 그렇다. 그래서 C(n, r)을 이항 계수라고도 부른다. a = b = 1을 넣으면 Σ C(n, r) = 2^n, 즉 부분집합의 총 개수가 나온다.

중복을 허용하면

종류	상황	개수
순열	서로 다른 n개에서 r개를 순서 있게, 중복 없이	n! / (n−r)!
중복 순열	순서 있게, 같은 것을 여러 번 뽑을 수 있음	n^r
조합	순서 없이, 중복 없이	n! / (r!(n−r)!)
중복 조합	순서 없이, 중복 허용	C(n+r−1, r)
같은 것이 있는 순열	`aabbb`처럼 같은 문자가 섞인 나열	n! / (p! q! …)

중복 조합은 "별과 막대"로 이해한다. r개의 별 사이에 막대 n−1개를 끼워 n칸으로 나누는 방법의 수와 같아서 C(n+r−1, r)이다. 예: 사과·배·감 중에서 과일 5개를 사는 방법은 C(7, 5) = 21.

코드로 다루기

개수만 필요할 때

from math import comb, perm, factorial
 
perm(10, 3)    # 720
comb(10, 3)    # 120

n이 커서 나머지 연산(mod p)이 필요하면 팩토리얼과 그 역원을 미리 구해 두고 C(n, r) = n! · (r!)⁻¹ · ((n−r)!)⁻¹ mod p로 계산한다. 역원 구하는 법은 정수론 기초에 있다.

파스칼 점화식으로 표 채우기

나눗셈 없이 덧셈만 쓰므로 정수 오버플로나 나머지 연산과 잘 맞는다. 동적 계획법의 전형적인 예다.

def binom_table(n):
    C = [[0] * (n + 1) for _ in range(n + 1)]
    for i in range(n + 1):
        C[i][0] = C[i][i] = 1
        for j in range(1, i):
            C[i][j] = C[i - 1][j - 1] + C[i - 1][j]
    return C
 
binom_table(5)[5][2]   # 10

경우를 하나씩 만들어야 하면 파이썬 itertools의 permutations(순열), combinations(조합), product(repeat=r)(중복 순열), combinations_with_replacement(중복 조합)를 쓴다. 직접 짜려면 재귀로 「이번 자리에 무엇을 놓을지」(순열)나 「이 원소를 넣을지 말지」(조합)를 고르며 내려간다. 코드와 가지치기는 완전 탐색과 백트래킹에 있다.

완전 탐색이 가능한지 가늠하기

경우의 수를 먼저 세면 다 만들어 볼 수 있는지 바로 판단된다. 1초에 약 1억 번 연산으로 어림하면 모든 순열(n!)은 n이 10 안팎(10! ≈ 363만), 모든 부분집합(2^n)은 20~~25까지다. 두 개·세 개를 고르는 쌍은 C(n, 2) ≈ n²/2, C(n, 3) ≈ n³/6이라 각각 n이 수천~~1만, 수백~1,000 정도까지 감당한다. 이보다 크면 정렬·그리디·DP로 줄일 방법을 찾는다. N 범위별 목표 복잡도 표는 코딩 테스트 접근법에 있다.

정리

순서를 구분하면 순열 n!/(n−r)!, 구분하지 않으면 조합 n!/(r!(n−r)!).
C(n, r) = C(n−1, r−1) + C(n−1, r)는 원소 하나를 넣느냐 마느냐로 나눈 것이고, 파스칼 삼각형과 이항 정리로 이어진다.
중복 순열은 n^r, 중복 조합은 C(n+r−1, r).
경우의 수를 먼저 세어 보면 완전 탐색이 가능한지 바로 판단할 수 있다.

버그 제보