이항 계수 2 11051 - (백준, DP)

1. 조합 공식 변형(n​Ck​ = n(n-1)(n-2)...(n-k+1) / k!)을 활용한 시간 복잡도를 최소화한 풀이

import sys
input = sys.stdin.readline

N, K = map(int, input().split())

result = 1
for i in range(K):
    result *= N
    N -= 1

divisor = 1
for i in range(2, K+1):
    divisor *= i

print((result // divisor) % 10007)

2. 

이제 좀 알고리즘답게 풀어볼 시간이다. 바로 동적 계획법을 사용한 방법인데 언제나 이야기하지만 동적 계획법이라는 용어는 난해한 용어를 좋아하는 전문가들을 전문가답게 만들어주는 용어고 일반인이 이해하기에는 ‘기억하며 풀기’라고 생각하면 된다.

 

전체 집합에서 아무것도 고르지 않는 방법은 1가지이고, 동시에 모두를 선택하는 것도 1가지 방법뿐이다. 그리고 3번 성질을 이용하면 이항계수를 그보다 작은 두 개의 부분식으로 쪼갤 수 있고 이 식들은 더 잘게 계속계속 쪼개질 수 있다. 쪼개지면서 n과 k가 점차 작아지는데 k가 0이 되는 순간과 n과 k가 같아지는 순간은 무조건 1이다. 성질에 의해 정의된 것이니까.

이 개념을 파이썬으로 재귀적으로 구현하면 다음과 같다.

def bino_coef(n, k):
    if k == 0 or n == k:
        return 1
    return bino_coef(n-1, k) + bino_coef(n-1, k-1)


>>> bino_coef(4, 2)

6

간단한 재귀함수의 활용이다. 이는 2.1번과 3번 성질을 그대로 활용했다. 결과는 나오지만 이 함수는 치명적인 문제를 안고 있다. 바로 부분문제의 중복(overlapping subproblems)으로 이 때문에 함수의 성능이 치명적으로 나쁘다.

부분문제의 중복이라는 현상을 설명하기 위해 비슷한 예제인 피보나치 수열에 대한 반복구현의 실행흐름을 가져왔다.

피보나치 수열은 n번째 항을 n-1번째 항과 n-2번째 항의 합으로 표현한 수열로 위의 fib 함수는 실행 시 두 개로 갈라진다. 이항계수 함수도 둘로 갈라지고 인자가 점점 작아져 마침내 기저사례(base case, 또는 탈출지점)에 닿는다는 점에서 같다.

위의 그림에서 7번째 항을 구하기 위해 4번째 항이 몇 번이 계산되는가? 3번째와 2번째는? 즉, 원 문제를 풀기 위한 부분문제가 너무 중복되어서 쓸데없는 시간을 잡아먹고 있는 것이다. 저런 식으로 만약 100번째 피보나치 수를 구하자고 하면 컴퓨터가 멈추고 만다.

대신 동적 계획법은 이미 구한 부분문제의 답을 캐쉬에 저장해서 또 구해야 할 때 바로 답을 내놓고 쓸데없는 계산을 하지 말자고 말한다. 우리는 바로 이렇게 문제를 풀 것이다.

 

우리의 캐시는 원 문제 해결 중 마주치는 부분문제의 이항계수를 한 번 계산 후에 저장한다. 캐쉬는 2차원으로 만든다. 부분문제를 계산할 때, n 은 0부터 n 까지, k 은 0부터 k 까지의 범위를 지니기 때문에 총 가능한 이항계수의 가지의 수는 (n+1) * (k+1) 개가 되기 때문이다. 엑셀 표를 생각하면 된다.

 

자, 캐쉬를 마련했다면 우리는 가지고 있는 2.1 번 성질을 이용해 캐쉬를 먼저 초기화한다. 그 초기화된 최소 단위의 부분문제를 조합해서 최종문제를 해결한다.

실제 코드는 다음과 같다.

def bino_coef(n, r):
    # 1.
    cache = [[0 for _ in range(r+1)] for _ in range(n+1)]

    # 2.
    for i in range(n+1):
        cache[i][0] = 1
    for i in range(r+1):
        cache[i][i] = 1

    # 3.
    for i in range(1, n+1):
        for j in range(1, r+1):
            cache[i][j] = cache[i-1][j] + cache[i-1][j-1]

    return cache[n][r]

n 개의 아이템 중 r 개를 뽑는 ‘bino_coef’ 함수를 만들었다. k 나 r 나 같은 의미다.

1. 먼저 캐쉬를 만든다. 2차원에, 크기는 (n+1) * (r+1) 가 된다.
2. 캐쉬를 초기화한다. r 이 0이거나, n 이 r 과 같은 경우는 2.1번 성질에 따라 그냥 1이 된다. 우리는 이 기초식을 이용해 다음 식을 계속해서 완성해나갈 것이다.
3. 실제로 값을 구한다. i 개의 아이템 중 j 개의 아이템을 선택하는 경우의 수는 그보다 작은 두 값의 합이다. 이때 for 문을 점진적으로 전진하는 것을 기억하면 된다.

 

def ans(n, r):
    # 1.
    cache = [[0 for _ in range(r+1)] for _ in range(n+1)]

    # 2.
    for i in range(n+1):
        cache[i][0] = 1
    for i in range(r+1):
        cache[i][i] = 1

    # 3.
    for i in range(1, n+1):
        for j in range(1, r+1):
            cache[i][j] = cache[i-1][j] + cache[i-1][j-1]

    return cache[n][r]

N, K = map(int, input().split())
print(ans(N,K)%10007)

https://shoark7.github.io/programming/algorithm/3-ways-to-get-binomial-coefficients

[조합론] 이항계수 알고리즘 3가지

https://velog.io/@ledcost/%EB%B0%B1%EC%A4%80-11051-%ED%8C%8C%EC%9D%B4%EC%8D%AC-%EC%9D%B4%ED%95%AD-%EA%B3%84%EC%88%98-2-%EC%8B%A4%EB%B2%841-%EC%A1%B0%ED%95%A9%EB%A1%A0

[백준 11051 파이썬] 이항 계수 2 (실버1, 조합론)