경우의 수와 조합론

비밀번호 4자리 숫자는 몇 가지일까요? 친구 10명 중 대표 3명을 뽑는 방법은? 도시 20곳을 한 번씩 들르는 경로는 몇 가지일까요? 이런 "세는" 문제를 다루는 분야가 조합론이에요. 셀 수 있으면 확률을 계산할 수 있고, 보안의 강도를 잴 수 있고, 알고리즘이 감당해야 할 일의 양을 미리 알 수 있어요.

두 가지 기본 법칙

합의 법칙: 또는

동시에 일어날 수 없는 두 경우 중 하나를 고를 때는 더해요.

점심으로 한식 5가지 또는 양식 3가지 중 하나를 고른다면 $5 + 3 = 8$ 가지예요.

곱의 법칙: 그리고

연달아 일어나는 선택은 곱해요.

상의 4벌과 하의 3벌로 옷을 맞춰 입는 방법은 $4 \times 3 = 12$ 가지예요. 상의 하나를 고를 때마다 하의 3가지가 따라붙으니까요.

이 두 법칙이 조합론의 거의 전부예요. 나머지 공식은 이 법칙을 자주 나오는 상황에 맞게 정리한 거예요.

비밀번호의 경우의 수

비밀번호 규칙	경우의 수
숫자 4자리	$10^4 = 10{,}000$
숫자 6자리	$10^6 = 1{,}000{,}000$
영문 소문자 8자리	$26^8 \approx 2.1 \times 10^{11}$
영문 대소문자와 숫자 8자리	$62^8 \approx 2.2 \times 10^{14}$
영문 대소문자, 숫자, 특수문자 12자리	$94^{12} \approx 4.8 \times 10^{23}$

자리마다 고를 수 있는 글자 수를 자릿수만큼 곱한 거예요. 길이가 늘어나면 경우의 수가 지수적으로 늘어나요. 그래서 보안 전문가들은 복잡한 규칙보다 긴 비밀번호를 더 권해요. 보안 트랙에서 다시 다뤄요.

순열: 순서가 중요할 때

계승

$n$ 개를 한 줄로 세우는 방법은 첫 자리에 $n$ 가지, 둘째 자리에 $n-1$ 가지, ... 마지막에 1가지예요.

n! = n \times (n-1) \times \cdots \times 2 \times 1

$n!$ 을 "n 팩토리얼"이라고 읽어요. $0! = 1$ 로 정해요(아무것도 세우지 않는 방법은 한 가지).

$n$	$n!$
5	120
10	3,628,800
20	약 $2.4 \times 10^{18}$
52	약 $8.1 \times 10^{67}$

카드 52장을 섞는 방법은 $52!$ 가지로, 우주의 원자 수(약 $10^{80}$ )에 비할 만큼 커요. 제대로 섞은 카드의 순서는 인류 역사상 한 번도 나온 적 없는 순서일 가능성이 매우 높아요.

n개 중 r개를 뽑아 줄 세우기

10명 중 회장, 부회장, 총무를 뽑는다면 $10 \times 9 \times 8 = 720$ 가지예요. 이걸 순열이라고 하고 이렇게 써요.

{}_nP_r = \frac{n!}{(n-r)!}

조합: 순서가 상관없을 때

10명 중 대표 3명을 뽑는데 직책이 없다면? 같은 세 사람을 어떤 순서로 뽑든 같은 결과예요. 세 사람을 줄 세우는 $3! = 6$ 가지가 모두 같은 경우로 묶이니, 순열을 6으로 나눠요.

{}_nC_r = \binom{n}{r} = \frac{n!}{r!\,(n-r)!}

\binom{10}{3} = \frac{720}{6} = 120

순열과 조합 구별법 뽑은 것들의 순서를 바꿨을 때 다른 결과가 되면 순열, 같은 결과면 조합이에요. 비밀번호와 달리기 순위는 순열, 팀 구성과 로또 번호는 조합이에요.

로또 1등 확률

45개 숫자 중 6개를 순서 없이 고르는 경우는

\binom{45}{6} = 8{,}145{,}060

1등 확률은 약 814만 분의 1이에요. 매주 한 장씩 사면 평균적으로 15만 년쯤에 한 번 당첨되는 셈이에요.

import math
print(math.comb(45, 6))      # 8145060
print(math.perm(10, 3))      # 720
print(math.factorial(10))    # 3628800

조합의 대칭성

\binom{n}{r} = \binom{n}{n-r}

10명 중 3명을 뽑는 것은 남을 7명을 고르는 것과 같아요. 계산할 때 더 작은 쪽으로 바꾸면 편해요.

중복을 허락할 때

중복 순열

같은 것을 여러 번 골라도 되고 순서가 중요하면 $n^r$ 가지예요. 비밀번호가 바로 이 경우예요.

중복 조합: 별과 막대

같은 것을 여러 번 골라도 되고 순서가 상관없는 경우예요. 예를 들어 사과, 배, 귤 중에서 과일 5개를 사는 방법(같은 과일 여러 개 가능)은 몇 가지일까요?

과일 5개를 별 5개로, 종류의 경계를 막대 2개로 나타내면 돼요. ★★|★|★★는 사과 2, 배 1, 귤 2개예요. 결국 7칸 중 막대 2개의 자리를 고르는 문제예요.

\binom{5 + 3 - 1}{3 - 1} = \binom{7}{2} = 21

일반적으로 $n$ 종류에서 $r$ 개를 중복 허락해 고르는 방법은 $\binom{n + r - 1}{r}$ 가지예요.

이항 정리와 파스칼의 삼각형

$(a + b)^n$ 을 전개하면 계수에 조합이 나와요.

(a + b)^n = \sum_{k=0}^{n} \binom{n}{k} a^{n-k} b^k

$(a+b)^3 = a^3 + 3a^2b + 3ab^2 + b^3$ 에서 계수 1, 3, 3, 1이 $\binom{3}{0}, \binom{3}{1}, \binom{3}{2}, \binom{3}{3}$ 이에요. 세 개의 괄호 중 몇 개에서 $b$ 를 고르느냐의 경우의 수이기 때문이에요.

이 계수들을 쌓으면 파스칼의 삼각형이 돼요.

        1
       1 1
      1 2 1
     1 3 3 1
    1 4 6 4 1
   1 5 10 10 5 1

각 수는 바로 위 두 수의 합이에요. 식으로 쓰면

\binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k}

$n$ 명 중 $k$ 명을 뽑을 때 "특정한 한 사람을 뽑는 경우"와 "뽑지 않는 경우"로 나눈 거예요. 이렇게 큰 문제를 작은 문제로 나누는 생각은 알고리즘 트랙의 동적 계획법과 정확히 같은 구조예요.

비둘기집 원리

비둘기 10마리가 집 9칸에 들어가면, 적어도 한 칸에는 두 마리 이상이 들어가요. 너무 당연해 보이지만 강력한 증명 도구예요.

사람이 367명 모이면, 생일이 같은 사람이 반드시 있어요(윤년 포함 366일).
서울 인구 약 940만 명 중에는 머리카락 수가 정확히 같은 사람이 반드시 있어요. 사람 머리카락은 많아야 수십만 개거든요.
해시 함수의 출력이 256비트로 정해져 있다면, 입력은 무한하니 출력이 같은 서로 다른 입력(충돌)이 반드시 존재해요. 그래서 좋은 해시 함수의 조건은 "충돌이 없다"가 아니라 "충돌을 찾기가 사실상 불가능하다"예요.

모든 경우를 다 확인하면 생기는 일

조합론은 알고리즘의 한계를 보여 줘요. 도시 $n$ 곳을 한 번씩 들르는 가장 짧은 경로를 찾는 외판원 문제를, 모든 순서를 다 확인해서 푼다고 해 볼게요. 출발점을 고정해도 경로는 $(n-1)!$ 가지예요.

도시 수	확인할 경로 수	1초에 10억 개 확인할 때
10	362,880	0.0004초
15	약 $8.7 \times 10^{10}$	87초
20	약 $1.2 \times 10^{17}$	약 3.9년
25	약 $6.2 \times 10^{23}$	약 2천만 년

컴퓨터가 아무리 빨라져도 이런 폭발은 감당할 수 없어요. 그래서 "모든 경우를 다 확인하지 않고도 답을 찾는 똑똑한 방법"이 필요하고, 그게 알고리즘 공부의 핵심이에요. 이 문제가 왜 근본적으로 어려운지는 컴퓨터 과학 이론 트랙의 계산 복잡도 강의(P와 NP)에서 다뤄요.

파이썬으로 경우 나열하기

from itertools import permutations, combinations, product

print(list(permutations("ABC", 2)))   # 순열: ('A','B'), ('A','C'), ('B','A') ...
print(list(combinations("ABC", 2)))   # 조합: ('A','B'), ('A','C'), ('B','C')
print(len(list(product("01", repeat=4))))   # 중복 순열: 2^4 = 16

작은 문제에서는 직접 나열해 보면서 공식이 맞는지 확인하는 습관이 좋아요.

연습 문제

티셔츠 5벌, 바지 4벌, 신발 3켤레로 만들 수 있는 차림은?
8명이 달리기를 해서 1, 2, 3등을 정하는 경우는?
8명 중 청소 당번 3명을 정하는 경우는?
대문자 알파벳 26개와 숫자 10개로 만든 6자리 코드는 몇 가지?
사탕 10개를 아이 3명에게 나눠 주는 방법은? (못 받는 아이가 있어도 됨)
한 반에 학생 13명이 있으면 같은 달에 태어난 학생이 반드시 있을까요?

정답

$5 \times 4 \times 3 = 60$ 가지
${}_8P_3 = 8 \times 7 \times 6 = 336$ 가지
$\binom{8}{3} = 56$ 가지
$36^6 = 2{,}176{,}782{,}336$ 가지
중복 조합 $\binom{10 + 3 - 1}{3 - 1} = \binom{12}{2} = 66$ 가지
네. 달은 12개인데 학생이 13명이니 비둘기집 원리에 따라 반드시 있어요.

다음 강의

다음 강의에서는 증명하는 법을 배워요. "그렇다"고 말하는 것과 "반드시 그렇다"는 것을 보이는 것은 전혀 달라요. 증명은 알고리즘이 항상 올바르게 동작하는지 확신하는 방법이기도 해요.