이항계수 구하기 STEP by STEP

단순 무식(Naive Approach)

단순 무식한 방법은 이항계수의 정의를 그대로 구현하는 것이다. $_nC_r = \frac{n!}{(r!(n-r)!)}$의 공식을 직접 계산한다.

장점:

구현이 매우 간단하다
작은 수에 대해서는 빠르게 결과를 얻을 수 있다

단점:

n이 커질수록 팩토리얼 계산으로 인한 시간 복잡도가 매우 증가한다 (O(n))
큰 수에 대해서는 오버플로우가 발생할 수 있다

def factorial(n):
    if n <= 1:
        return 1
    return n * factorial(n-1)

def combination_naive(n, r):
    if r > n:
        return 0
    if r == 0 or r == n:
        return 1
    return factorial(n) // (factorial(r) * factorial(n-r))

# 예시
print(combination_naive(5, 2))  # 10
print(combination_naive(10, 3)) # 120

실제 사용 예시:

n = 5, r = 2인 경우의 계산 과정

5! = 5 × 4 × 3 × 2 × 1 = 120
2! = 2 × 1 = 2
3! = 3 × 2 × 1 = 6
$_5C_2$ = 120 / (2 × 6) = 10

다이나믹 프로그래밍(Dynamic Programming)

파스칼의 삼각형 원리를 이용한 방법이다. 점화식 $_nC_r = _{n-1}C_r + {n-1}C{r-1}$을 활용하여 중복 계산을 피한다.

파스칼의 삼각형 예시:

장점: