(파이썬 python) 백준 11051번 : 이항 계수 2

이항계수를 구하는 구하는 알고리즘을 짜면 되는 문제이다.

 

1. 이항계수의 정의를 이용하여 그대로 구현!

이항계수를 구하는 공식은 고등학교때 당연히 배웠지만 까먹었다 해도 문제는 없다.

우리에겐 구글이 있기 때문에...!!

구글에 이항계수만 검색해도 친절하게 설명해주는 블로그와 사이트들이 많이 있다. 자신이 보기 편한 것을 보고 이해하고 그 공식을 구현하면 쉽게 풀리는 문제이다.

사실 이미 알고있는 공식을 구현하기만 되는 것이라 따로 머리를 크게 쓰고 아이디어를 짜낼 필요도 없다.

이항계수 공식

아래의 첫번째 코드가 이항계수의 공식을 가장 충실히 따라 알고리즘을 구현한 코드이다.

python에는 math라이브러리에 펙토리얼을 구할 수 있는 기능들이 있지만

연습도 할 겸, 코드량도 많지 않으니 팩토리얼 함수를 구현하여 이항계수를 구하는 코드를 짯다.

n, k = map(int,input().split())

def factorial(n):
    ans = 1 
    for i in range(2,n+1):
        ans *= i
    return ans

def bino_coef_factorial(n,k):
    return factorial(n) // (factorial(k) * factorial(n-k))

print(bino_coef_factorial(n,k) % 10007)

간단하게 통과!

 

2. 동적 계획법 1: 이항계수의 성질 이용하여 구현!

아래의 코드는 이항계수의 성질과 동적계획법(Dynamic Programming)을 이용하여 구현하였다.

그렇다면 우선 이항계수의 어떤 성질을 이용하였는가??

이항계수의 성질 1

이항계수는 위와 같은 항등식을 만족하는데 이 식에 대한 증명은 쉽다.

직접 손으로 풀어보면 쉽게 좌,우항이 같음을 알 수 있을 것이다.

 

또 한가지 다른 성질은 n개의 수에서 0개를 뽑거나 n개 모두 뽑는 경우의 수는 1이라는 것이다. 이것은 당연한 말로 하나도 안뽑는 경우 혹은 모두 뽑는 경우가 모두 선택하거나 모두 선택하지 않거나 같은 경우이기 때문이다. 말장난 같지만 조금만 생각해보니 무슨 말인지 알 수 있었다.

따라서 이항계수는 아래의 성질을 만족한다.

이항계수 성질 2

아래의 코드는 이러한 이항계수의 성질을 이용하여 재귀방법을 사용하여 구현한 것 이다.

import sys
sys.setrecursionlimit(10**6)

n, k = map(int,input().split())

def bino_coef_1(n,k):

	# 이항계수 성질 2
    if k == 0 or n == k: 
        return 1
       
    # 이항계수 성질 1 - 재귀
    return bino_coef_1(n-1,k)+bino_coef_1(n-1,k-1)

print(bino_coef_1(n,k) % 10007)

그러나 이 알고리즘의 문제는 문제는 부분문제의 중복(overlapping subproblems)이라는 치명적 문제가 있다.

무슨말인가 하면 백준에 나온 예제(5 combination 2)로 위의 코드를 실행시켜 보면 부분문제들을 여러분 중복으로 풀어야 한다는 것을 알 수 있다. 

부분문제의 중복(overlapping subproblems)

첫번째 제출했을 때 재귀오류(RecursionError)가 떳다. 그래서 재귀깊이 제한을 늘려주었다.

역시나 부분문제의 중복(overlapping subproblems)으로 인해서 시간초과가 뜬다. 

 

3. 동적 계획법 2: 바텀업 방식으로 풀기(Memoization)

2번에서 재귀를 이용하여 풀었던 방법은 탑바텀으로 위에서 아래로 내려가면서 문제를 풀어나간다. 그러나 문제는 언급했듯이 부분문제의 중복이 있다. 따라서 이 문제를 해결하기 위해서는 바텀업 방식을 이용해서 풀면 된다. 메모이제이션이라고 이미 풀었던 문제는 다시 풀지 않고 메모해두었다가 필요할 때 바로바로 찾는 아이디어이다.

 

2차원 리스트의 캐쉬를 만들어서 그 공간에 미리 계산해 둔 값들을 넣어주고 필요할 때 찾아쓰는 방식으로 메모이제이션을 구현했다.

이때 이항계수2 의 성질을 이용해서 모든것을 뽑는 경우의 수, 하나도 뽑지 않는 경우의 수는 1로 초기화 한 후 이항계수 성질1을 이용해서 나머지 값들을 계산한다.

n, k = map(int,input().split())

def bino_coef_2(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]

print(bino_coef_2(n,k) % 10007)

시간초과가 떳었는데 이번엔 다행히 맞는다고 알려준다:)

---

 

참고블로그 https://shoark7.github.io/programming/algorithm/3-ways-to-get-binomial-coefficients

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

알고리즘, 코딩관련 공부를 하기 시작하면서부터 알게 된 블로그인데 굉장히 친절하고 자세하게 개념들을 알려주신다. 정말 도움을 많이 받고 있다. 자신가 알고 이해하는 내용을 다른사람에게 설명하는 쪽으로 탁월하신듯하다! 정말 감사하다.