[알고리즘 설명][Python] 이항 계수(binomial coefficients)

이 게시글은 CS(컴퓨터공학) 프로그래밍 기초를 어느 정도 알고 있다고 가정하고 아주 간단하게 설명하는 게시글입니다.

혹시나 모르는 부분이 있으면 댓글로 질문해주세요.

 

우선 이항 계수를 설명하기 전에 계승(factorial), 즉 팩토리얼이 뭔지 아주 간단하게 알아보겠습니다.

팩토리얼은 1부터 n까지 싹 다 곱한 것을 의미하며 n!로 표시됩니다.

즉, 1!, 2!, 3!, 4!, 5!는 다음과 같습니다.

1! = 1

2! = 1 * 2 = 1! * 2

3! = 1 * 2 * 3 = 2! * 3

4! = 1 * 2 * 3 * 4 = 3! * 4

5! = 1 * 2 * 3 * 4 * 5 = 4! * 5

그러면 0!는 무엇일까요? 위의 수식에서 규칙을 찾아보면 1! = 1 = 0! * 1입니다. 따라서 0! = 1이 됩니다.

저번에 초간단하게 알아본 다이나믹 프로그래밍을 보면 알겠지만 팩토리얼은 결국 초기식과 점화식이 존재하는 dp라는 것을 알 수 있습니다.

 

초기식 : dp[0] = 1

점화식 : dp[i] = i * dp[i-1]

 

이것을 Python 소스 코드로 구현합니다.

이 때 dp 테이블의 이름은 factorial(혹은 줄여서 fact라고 해도 됩니다.)로 하겠습니다.

import sys

input = sys.stdin.readline

LIMIT = 20

factorial:list = [0] * (LIMIT + 1)

# 초기식
factorial[0] = 1

# 점화식
for i in range(1, LIMIT + 1, 1) :
    factorial[i] = i * factorial[i-1]

# 5! 출력
print(factorial[5])

# 10! 출력
print(factorial[10])

# 20! 출력
print(factorial[20])

[결과]

120 (5!와 일치함)
3628800 (10!와 일치함)
2432902008176640000 (20!와 일치함)

 

그러면 이항 계수는 무엇일까요?

이항 계수의 사전적인 뜻은 "이항식에서 이항 정리에 의한 각 항의 계수"를 의미합니다.

이게 뭔 말인지 이해 안 되죠?

원래는 이항식과 이항 정리에 대해 설명하고 넘겨야 하나 초간단 알고리즘 설명에서는 수포자 분들을 위해 이를 과감하게 생략합니다.

 

여기서 조합론에서 조합(어떤 유한한 개수의 원소들을 가진 집합에서 원하는 개수만큼 순서를 고려하지 않고 뽑은 경우의 수)의 정의를 굳이 공부하면서 이항 계수를 공부할려고 하면 뭔가 더 어려워 보일 것입니다.

 

그럴 때 제가 아주 간단하게 이항 계수를 로또로 비유해서 설명할 것입니다.

대한민국에서 로또 혹은 복권은 1부터 45까지 45개의 숫자 중에서 중복되지 않는 숫자 6개를 고르는 방식입니다.

예를 들어 1 4 16 23 31 41(실제 1205회 1등 번호)로 해서 45개의 숫자 중 6개를 고르는 방식입니다.

 

자, 처음에는 45개 중 1개 골라야 하니 경우의 수는 45가지, 그 다음 나머지 44개 중에서 1개 골라야 하니 경우의 수는 45 * 44가지...

같은 원리를 적용하여 45개 중 순서를 6개를 고를 때 나오는 경우의 수는 45 * 44 * 43 * 42 * 41 * 40가지입니다.

이것은 45! / (45 - 6)!와 일치합니다.

 

그리고 아까 조합의 정의에서 순서를 고려하지 않는다는 내용이 분명히 적혀 있어요.

즉, 1 4 16 23 31 41과 4 1 16 41 23 31는 순서까지 고려한 경우이나 순서를 고려하지 않을려면 아까 나온 경우의 수(45! / 39!)에서 또 다시 6!을 나눠줘야 합니다.

이것을 수식으로 표현하면 다음과 같습니다.

$$ \frac{45!}{6! \times (45 - 6)!} $$

아까 전에 작성해놓은 팩토리얼 소스 코드를 활용하여 로또 경우의 수, 그리고 1등 당첨 확률(6개 번호가 모두 맞을 확률)을 아래의 Python 소스 코드로 계산할 수 있습니다.

import sys

input = sys.stdin.readline

LIMIT = 45

factorial:list = [0] * (LIMIT + 1)

# 초기식
factorial[0] = 1

# 점화식
for i in range(1, LIMIT + 1, 1) :
    factorial[i] = i * factorial[i-1]

lottery:int = factorial[45] // factorial[6] // factorial[45 - 6]
print(f"로또 총 경우의 수 : {lottery}가지")
print(f"1등 당첨 확률 : {100 / lottery:.10f}%")

[결과]

로또 총 경우의 수 : 8145060가지
1등 당첨 확률 : 0.0000122774%

 

이것을 통해 45개 번호 중 6개를 고르는 로또의 총 경우의 수가 나왔으며 1등 당첨 확률이 얼마나 낮은지 확인할 수 있습니다.

아, 로또 1등 당첨되고 싶다.

 

여기서 45를 n, 6을 k로 변환합니다.

아래에 있는 식이 바로 이항 계수를 의미합니다.

$$ \binom{n}{k} = {}_nC_k = \frac{n!}{k!(n - k)!} $$

로또 경우의 수는 n = 45, k = 6일 때의 이항 계수와 일치합니다.

이것을 통해 이항 계수를 구해주는 소스 코드를 다음과 같이 구현할 수 있습니다.

import sys

input = sys.stdin.readline

# 컴퓨터 성능에 따라 자유롭게 조절해주세요. 단, 너무 크게만 안 하면 됩니다.
LIMIT = 100

fact:list = [0] * (LIMIT + 1)

# 초기식
fact[0] = 1

# 점화식
for i in range(1, LIMIT + 1, 1) :
    fact[i] = i * fact[i-1]
    
# 입력부
N, K = map(int, input().split())

# 이항 계수 결과값
result:int = fact[N] // fact[K] // fact[N - K]

# 출력부
print(f"{N}C{K} = {result}")

[예시 입력 1]

5 2

[예시 결과 1]

5C2 = 10

 

[예시 입력 2]

45 6

[예시 결과 2]

45 6
45C6 = 8145060

 

이렇게 해서 오늘도 초간단하게 이항 계수를 어떻게 구현하는지 알게 되었습니다.