컴퓨터공학 300 주제 시리즈의 007번째 글이다. 전체 지도는 여기.

한 줄 요약

경우의 수는 곱의 법칙과 합의 법칙 두 가지에서 출발한다. 순서가 중요하면 순열, 순서가 중요하지 않으면 조합이고, 비둘기집 원리는 “칸보다 물건이 많으면 어딘가 겹친다” 는 단순한 사실로 존재를 증명한다.

왜 필요한가

알고리즘의 실행 시간을 따지는 일은 결국 “몇 번 반복하는가” 를 세는 일이다. 무차별 대입이 가능한지, 비밀번호 공간이 충분히 큰지, 테스트 조합이 몇 개인지, 해시 충돌이 언제 나기 시작하는지도 모두 세기 문제다.

세기를 잘못하면 판단이 틀어진다. “부분집합을 다 시도해 보자” 는 원소 20 개면 약 백만 번이지만 원소 60 개면 현실적으로 끝나지 않는다. 이 감각이 있어야 문제를 보는 순간 “이건 완전 탐색으로 안 된다” 를 알아챈다.

핵심 개념

두 기본 법칙

  • 합의 법칙: 겹치지 않는 두 경우 A, B 중 하나를 고르는 방법은 n(A) + n(B) 가지.
  • 곱의 법칙: A 에서 하나 고르고 이어서 B 에서 하나 고르는 방법은 n(A) × n(B) 가지.

(이 글에서 n(A) 는 집합 A 의 원소 개수다.)

예: 영문 소문자 26 개와 숫자 10 개로 만든 길이 8 의 문자열은 각 자리마다 36 가지이므로 36⁸ 가지다. 곱의 법칙을 8 번 쓴 것이다.

겹치는 경우에는 포함-배제 원리로 고친다. n(A ∪ B) = n(A) + n(B) − n(A ∩ B). 1 부터 100 까지에서 2 또는 3 의 배수는 50 + 33 − 16 = 67 개다.

순열

서로 다른 n 개에서 r 개를 순서 있게 뽑아 늘어놓는 방법의 수다.

P(n, r) = n × (n-1) × ... × (n-r+1) = n! / (n-r)!

첫 자리 n 가지, 둘째 자리 n−1 가지, … 를 곱한 것이다. n 개 전부를 늘어놓으면 n! 가지다. 10! = 3,628,800 이고, 20! 은 약 2.4 × 10¹⁸ 이다. 외판원 문제를 모든 경로를 시도해서 풀 수 없는 이유가 이 증가 속도다.

조합

서로 다른 n 개에서 r 개를 순서 없이 고르는 방법의 수다.

C(n, r) = n! / (r! (n-r)!)

순열 P(n, r) 은 “고르기” 와 “고른 r 개를 늘어놓기(r! 가지)” 를 곱한 것이므로 C(n, r) = P(n, r) / r! 이다. 이처럼 같은 것을 두 가지 방법으로 세어 등식을 얻는 방식을 조합적 증명이라 한다.

상황 순서 중요 중복 허용 공식
순열 O X n! / (n−r)!
중복순열 O O nʳ
조합 X X C(n, r)
중복조합 X O C(n+r−1, r)

중복조합은 “별과 막대” 로 센다. 서로 같은 공 r 개를 n 개 상자에 나누는 것은, 별 r 개와 칸막이 n−1 개를 한 줄에 늘어놓는 방법의 수와 같다.

이항 정리와 파스칼 삼각형

C(n, r) 을 이항계수라 부르는 이유는 (x + y)ⁿ 을 전개했을 때 xʳyⁿ⁻ʳ 의 계수이기 때문이다. 자주 쓰는 항등식은 다음과 같다.

  • 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, 1) + … + C(n, n) = 2ⁿ: 모든 부분집합의 수.

비둘기집 원리

정리. n+1 개 이상의 물건을 n 개의 칸에 넣으면, 적어도 한 칸에는 물건이 2 개 이상 들어간다.

증명. 모든 칸에 많아야 1 개씩 들어 있다면 물건은 많아야 n 개다. 모순이다. ∎

일반형. N 개를 k 칸에 넣으면 어떤 칸에는 적어도 ⌈N/k⌉ 개가 들어간다.

증명은 단순하지만 쓰임은 넓다.

  • 사람이 367 명이면 생일이 같은 두 사람이 반드시 있다.
  • 무손실 압축 알고리즘은 모든 입력을 줄일 수 없다. 길이 n 비트 문자열은 2ⁿ 개인데, n 비트보다 짧은 문자열은 2⁰ + 2¹ + … + 2ⁿ⁻¹ = 2ⁿ − 1 개뿐이다. 모든 입력을 줄이려면 두 입력이 같은 출력을 가져야 하고, 그러면 복원할 수 없다.
  • 해시 출력이 b 비트면 2ᵇ + 1 개의 서로 다른 입력 중 둘은 반드시 충돌한다.

생일 문제: “반드시” 와 “아마도” 의 차이

비둘기집 원리는 367 명이 되어야 충돌을 보장한다. 하지만 충돌이 일어날 가능성이 높아지는 시점은 훨씬 빠르다. n 명 모두 생일이 다를 확률은 365 × 364 × … × (365−n+1) / 365ⁿ 이다. 이 값은 n = 23 에서 처음으로 1/2 아래로 떨어진다(아래 코드로 확인한다).

일반적으로 N 칸에 무작위로 넣을 때, 대략 √N 개 정도부터 충돌 확률이 무시할 수 없게 된다. b 비트 해시라면 2ᵇᐟ² 근처다. 해시나 무작위 ID 의 길이를 정할 때 이 제곱근 규칙을 기억해야 한다.

직접 해 보기

파이썬 math 모듈의 perm, comb 와 itertools 로 공식을 확인하고, 생일 문제를 정확히 계산한다.

import math
from itertools import permutations, combinations, combinations_with_replacement

items = "ABCDE"
print(math.perm(5, 3), len(list(permutations(items, 3))))
print(math.comb(5, 3), len(list(combinations(items, 3))))
print(math.comb(5 + 3 - 1, 3), len(list(combinations_with_replacement(items, 3))))

# 파스칼의 법칙과 부분집합 합
n = 10
print(all(math.comb(n, r) == math.comb(n-1, r-1) + math.comb(n-1, r) for r in range(1, n)))
print(sum(math.comb(n, r) for r in range(n + 1)) == 2**n)

# 포함-배제: 1..100 에서 2 또는 3 의 배수
print(sum(1 for x in range(1, 101) if x % 2 == 0 or x % 3 == 0))

# 생일 문제: 모두 다를 확률이 처음 1/2 미만이 되는 n
def all_distinct(n, days=365):
    p = 1.0
    for i in range(n):
        p *= (days - i) / days
    return p
n = next(n for n in range(1, 366) if all_distinct(n) < 0.5)
print(n, round(1 - all_distinct(n), 4))

# 32비트 해시에서 충돌 확률이 1/2 을 넘는 대략의 원소 수
print(round(math.sqrt(2 * math.log(2) * 2**32)))

실행 결과다.

60 60
10 10
35 35
True
True
67
23 0.5073
77163

마지막 줄은 근사식 n ≈ √(2 ln 2 · N) 으로 계산한 값이다. 32 비트 해시는 약 7 만 7 천 개만 넣어도 충돌이 일어날 확률이 절반이다. 2³² 가 약 43 억이라는 것과 비교하면 매우 작은 수다.

현업에서는

  • 무작위 ID 의 길이. UUID 버전 4 는 128 비트 중 122 비트를 무작위로 채운다(RFC 9562, UUID). 생일 문제의 제곱근 규칙에 따르면 충돌이 걱정되기 시작하는 규모는 2⁶¹ 근처다. 반대로 “짧은 ID 가 보기 좋다” 며 32 비트 무작위 값을 쓰면 수만 건 수준에서 충돌을 만난다.
  • 조합 테스트. 설정 플래그가 10 개면 모든 조합은 2¹⁰ = 1024 가지다. 모든 쌍만 덮는 쌍별(pairwise) 테스트가 실무에서 쓰이는 이유가 이 수의 폭발이다.
  • 비밀번호 공간. 소문자·숫자 8 자리는 36⁸, 약 2.8 × 10¹² 가지다. 대소문자·숫자 12 자리는 62¹², 약 3.2 × 10²¹ 가지다. 길이를 늘리는 것이 문자 종류를 늘리는 것보다 효과가 크다는 것이 지수 법칙에서 바로 보인다.
  • 스케줄링. 파드 30 개를 노드 6 개에 배치하면 어떤 노드에는 적어도 ⌈30/6⌉ = 5 개가 올라간다. 일반형 비둘기집 원리다. 용량 계획에서 “최악의 노드” 를 가늠할 때 그대로 쓴다.

확인 문제

  1. 서로 다른 책 7 권 중 3 권을 골라 책장에 순서대로 꽂는 방법은 몇 가지인가?
  2. 같은 사탕 10 개를 아이 4 명에게 나눠 주는 방법(0 개 받는 아이 허용)은?
  3. 1 부터 1000 까지에서 3, 5, 7 어느 것으로도 나누어떨어지지 않는 수는 몇 개인가?
  4. 1 부터 10 까지의 수 중 6 개를 고르면, 합이 11 인 두 수가 반드시 포함됨을 보여라.

풀이

  1. P(7, 3) = 7 × 6 × 5 = 210.
  2. 중복조합 C(10 + 4 − 1, 10) = C(13, 3) = 286.
  3. 포함-배제로 1000 − (333 + 200 + 142) + (66 + 47 + 28) − 9 = 457.
  4. {1,10}, {2,9}, {3,8}, {4,7}, {5,6} 다섯 칸에 6 개를 넣으므로, 어떤 칸에서는 두 수를 모두 고른다.

더 읽을거리 (References)