[알고리즘] 이항계수란? 알고리즘 구현

백준 이항계수 1 - 문제 보러가기

이항계수

이항계수란 주어진 집합에서 원하는 개수만큼 순서없이 뽑는 조합의 개수를 의미한다. 여기서 이항 이란 한 개의 아이템에 대해서 뽑거나 뽑지않거나 두가지의 선택이 있기 때문에 붙은 단어이다. 이항계수의 정의는 다음과 같이 표현된다.

성질

• 2번: n개중 k를 선택하는 조합의 수는 결국 n개 중 선택받지 못한 아이템들의 조합의 수와 같다.
• 3번: 이항계수의 정의를 이용하여 3번과 같은 식을 도출해낼 수 있다.
• 4번: 파스칼의 삼각형과 관련이 깊다.

알고리즘 구현

이항계수의 정의를 이용한 구현법

가장 단순하게 이항계수의 정의를 이용하여 구현해보자.

import math

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

python의 팩토리얼 함수를 이용하여 간단하게 풀었다. 물론 함수를 이용하지 않고도 팩토리얼을 직접 구현해도 된다.

이항계수의 성질을 이용한 구현법 (동적계획법)

이항계수의 성질을 이용하여 동적 계획법으로 구현할수도 있다. 여기서 동적계획법이란 한 문제를 작은 단위의 문제로 쪼개어 푸는 방법이다.

위에서 살펴본 이항계수의 성질 3번에 따르면 이항계수는 그보다 작은 두 개의 부분식으로 쪼갤 수 있고, 쪼개진 부분식들은 그보다 작은 식으로 계속하여 쪼개질 수 있다.

또한 성질 2번에 의해서 전체에서 아무것도 선택하지 않는 조합 개수와 모든 아이템을 선택했을 때의 조합 개수는 모두 1이라는 것을 도출해볼 수 있는데, 이 말을 즉슨 부분식들을 쪼개다가 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

이 구현법의 문제점은 부분식의 중복이다. 위 코드에서는 작은 인자를 넘겨가며 재귀적으로 함수를 계속 호출하는데, 결과 값을 얻기위해 같은 부분함수가 여러번 실행되어 심각한 성능 저하를 일으킨다.

이런 문제를 보완하기 위해, 한번 계산한 값은 캐쉬에 저장해가며 풀어보도록 하자.

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]

1. 부분 문제 계산 시에 n의 범위는 0부터 n, k는 0부터 k까지의 범위를 가지기 때문에 (n+1)(k+1) 크기의 2차원 배열로 캐시를 초기화한다.
2. r이 0이 되거나 n과 r이 같은 경우는 1로 값을 넣어준다.
3. 이항계수의 3번 성질을 이용하여 값을 구한다. i개 중 j개의 아이템을 선택하는 경우의 수는 그 보다 작은 두 값의 합이다.

완전 탐색으로 구현

이번에 살펴볼 방법은 보다 확장성이 높은 구현 방법이다. 이 구현법을 잘 익혀두면 확률을 구할때 등에도 활용할 수 있다.

이번에는 n번의 뽑을 기회 중에서 각 아이템을 뽑거나, 뽑지 않는 선택을 모두 계산하여 최종적으로 k개가 되었을때의 경우만 세보는 것이다.

def bino_coef_prob(n, k):
    if k > n:
        return 0

    # 1.
    cache = [[-1 for _ in range(n+1)] for _ in range(n+1)]

    # 2.
    def choose(times, got):
        # 3.
        if times == n:
	    return got >= k

	# 4.
	if cache[times][got] != -1:
	    return cache[times][got]

	# 5.
	cache[times][got] = 0.5 * choose(times+1, got) + 0.5 * choose(times+1, got+1)
	return cache[times][got]

    # 6.
    return choose(0, 0)


>>> bino_coef_prob(10, 8)

1. 캐시를 초기화해준다. 값을 계산을 했는지, 안했는지를 판단하기 위해 0이 아닌 -1로 초기화해주었다. k가 n보다 큰 경우에는 무조건 0이기 때문에 이와 구분하기 위해 -1로 초기화를 한다.
2. 이번에 선택할 수 있는 기회에서 선택을 할지, 말지를 결정하는 함수이다. 인자로는 그 동안의 기회를 나타내는 times 와, 그동안 선택한 품목의 개수인 got 을 받는다. 확실히 하자. 이 함수의 의미는 times 번 동안 got 개를 선택하는 조합의 개수가 아니라, times 번까지 got 개를 선택했을 때, 최종적으로 n 번의 기회를 소진 시에 선택한 개수가 k 가 되는 경우의 수를 반환하는 함수이다.
3. n 번의 선택을 마쳤다면, 함수를 종료시킨다. 이때, 그동안 선택된 개수가 문제에서 주어진 k 와 일치하면 n 개 중 k 를 선택했으므로 1을 반환하되, 값이 다르면 0을 반환한다.(세지 않는다)
4. 그 다음으로 캐쉬에 우리의 부분문제의 답이 저장되어 있으면 그 값을 반환한다. -1은 초기화 값으로 현재 값이 -1이라는 얘기는 이 위치의 값은 건드린 적이 없다는 것, 그러니까 이전에 계산하지 않았기 때문에 계산해야 된다는 뜻이다
5. 캐쉬에 값이 없었으므로 값을 실제로 계산한다. times 번까지 got 개를 선택했을 때, 최종적으로 n 번의 기회를 소진 시에 선택한 개수가 k 가 되는 경우의 수는 times+1 번째에 got 개가 선택되었을 때(이번에 선택하지 않았을 때)와 times+1 번째에 got+1 개가 선택된 경우의 수(이번에 선택했을 때)의 합이다.
6. 함수를 시작한다. 이제 시작이고 그동안 선택한 것도 없으므로 당연히 times 와 got 모두 0이 될 수밖에 없다. 함수가 계속 호출되고, 인자가 점점 커지며 결국 n 번째까지 이를 것이고 그때 선택한 개수가 k 인 경우만 합산해서 결과를 내놓는다.

이 구현 방식을 이용하면 확률을 구하는 함수로도 활용할 수 있다. 예를 들어 동전 n번을 던질 때 앞면이 k개가 나올 확률을 구한다고 할 때, 아래처럼 원식의 5번 부분을 살짝만 변형해주면 된다.

cache[times][got] = 0.5 * choose(times+1, got) + 0.5 * choose(times+1, got+1)	# 5.

동전 던지는 예제라고 한다면 동전을 던져서 앞이 나오는 확률, 뒤가 나오는 확률 모두 0.5이다. 그래서 각 경우의 수에 단위확률을 곱해줌으로써 두 기대값을 구하고 더해줌으로써 확률을 구할 수 있다.

마치며

이항계수가 무엇이고 성질은 어떤게 있는지, 이를 이용해 어떻게 구현할 수 있는지 정리해보았다.3번의 식은 활용도가 높은 만큼 외우다시피 완벽하게 이해하는 것이 도움될 것 같다.

---

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