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

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

2018, Oct 23    

들어가며

이항계수는 내 기억에 고등학교 수준에서 배웠던 경우의 수 개념으로 나를 한동안 괴롭혔던 문제이다. 가령 “‘a’, ‘b’, ‘c’ 중 2개를 선택해 뽑는 조합을 모두 출력하라”와 같은 문제를 난 오랫동안 헤맸었는데 이제는 쉬운 풀이는 할 수 있는 수준이다.

그런데 조합의 경우 각각을 출력하는 것이 아닌 조합의 경우의 수 자체를 구하는 것은 꽤나 쉬운 일이다. 개념적으로 어렵지 않은 수식을 활용해 팩토리얼로 바로 구할 수 있기 때문이다. 프로그래밍에서도 똑같이 구현할 수 있다. 그러나 문제를 해결하는 방법은 보통 여러 가지일 때가 많고 이들을 모두 살펴보면 배울 것이 많다. 그건 이항계수도 마찬가지이다.

이번 포스트는 이항계수를 구하는 서로 다른 세 가지 알고리즘을 확인해보려고 한다. 첫 번째는 가장 쉬운 구현, 두 번째는 동적 계획법을 활용한 구현, 세 번째는 동적 계획법을 활용한 또다른 구현이다. 특히 세 번째 구현이 매우 의미가 있는데 확장성이라는 측면에서 다른 두 알고리즘의 추종을 불허한다. 첫 두 알고리즘은 알고 있었어도 세 번째는 몰랐을 수 있으니 확인 바란다.

이항계수란?

이항계수(Binomial Coefficient)는 조합론에서 등장하는 개념으로 주어진 크기 집합에서 원하는 개수만큼 순서없이 뽑는 조합의 가짓수를 일컫는다. 2를 상징하는 ‘이항’이라는 말이 붙은 이유는 하나의 아이템에 대해서는 ‘뽑거나, 안 뽑거나’ 두 가지의 선택만이 있기 때문이다. 이 개념을 모르는 사람은 없을 것이라 생각한다.

전체 집합에서 원소의 개수 n에 대해 k개의 아이템을 뽑는 이항계수(조합의 수)는 다음과 같이 정의한다.


\[ \binom{n}{k} = n C k = \frac{n!}{(n-k)!k!} (단, 0 \le k \le n) \quad \cdots 1 \]


위 공식을 이용해서 4개의 집합 중에서 2개를 순서없이 고르는 조합의 수는 ‘4! / 2! / 2!’, 즉 6이 된다. 이는 고등학교에서 배운 조합의 개념과 일치한다. 후에 설명할 팩토리얼을 사용한 이항계수 구현은 이 공식을 그대로 이용한다.

추가적으로 중요한 이항계수의 성질은 다음과 같다.


\[ \displaylines{ \binom{n}{k} = \binom{n}{n-k} \quad \cdots 2 \\ \\ \binom{n}{k} = \binom{n-1}{k} + \binom{n-1}{k-1} \quad \cdots 3 \\ \\ \sum_{k=0}^{n} \binom{n}{k} = 2^n \quad \cdots 4 } \]

2번은 조금만 생각해보면 상식적이다. n개 중에서 k개를 간택하는 것은 선택받지 못할 나머지 (n-k)개를 선택하는 것과 같다.
3번은 언뜻 보면 ‘뭐지?’ 할 수 있는데 이항계수의 정의식을 조작하면 2번식을 유도할 수 있다. 직접 해보는 것을 추천한다. 알고리즘을 공부하는 사람이라면 이 식은 기본적으로 외우고 있어야 하는 식이다. 이후 동적 계획법 알고리즘에서 사용할 것이다.
4번은 파스칼의 삼각형과 관련이 깊다.

우리의 구현은 언급한 특성 중 1번과 2번을 사용한다. 그리고 남은 알고리즘 하나는 이 성질과는 직접적인 상관이 없는 직관성으로 구현할 것이다.

구현을 시작해보자!

1. 팩토리얼: 이항계수의 정의 이용하기

이항계수의 정의를 이용한 방식은 팩토리얼을 사용한다. 팩토리얼은 파이썬에서는 math 모듈에서 지원하고 있지만 어렵지도 않은 거 그냥 구현하기로 한다.

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


def bino_coef_factorial(n, r):
    return factorial(n) // factorial(r) // factorial(n-r)

팩토리얼을 사용한 무난한 이항계수 알고리즘이다. 1번 정의를 충분히 활용했다. 주의할 점은 factorial 함수가 ‘0!’ 도 1을 문제없이 반환할 수 있도록 하는 것이다. 그렇지 않으면 밑의 이항계수 함수가 ZeroDivisionError 를 일으킬 수 있다.

이 함수는 잘 작동하지만 잠재적인 위험성이 있다. 기본적으로 팩토리얼은 지수 증가보다도 크게 증가하는데 n 이 15만 되어도 1조를 훌쩍 넘겨버린다. 파이썬에서는 상관없지만, 타 언어에서는 구하는 수가 매우 크지 않더라도 오버플로우가 쉽게 발생할 수 있기 때문에 주의해서 사용해야 한다. 물론 우리의 사랑스러운 파이썬에서는 일반적으로 오버플로우를 걱정하지 않고 이 함수를 이용할 수 있다. :)

2. 동적 계획법 1: 이항계수의 성질 이용하기

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

이 방법은 앞서 살펴본 이항계수의 성질 중 2번과 3번을 활용해 문제를 푼다. 2번을 통해 우리는 다음을 알 수 있다.


\[ \binom{n}{0} = \binom{n}{n} = 1 \quad \cdots 2.1 \]


전체 집합에서 아무것도 고르지 않는 방법은 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)으로 이 때문에 함수의 성능이 치명적으로 나쁘다.

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 문을 점진적으로 전진하는 것을 기억하면 된다.

3. 동적 계획법 2: 완전탐색 Memoization

위의 두 방법은 가장 일반적이며 또 실제로 유용하기도 하다. 하지만 이항계수만을 위한 함수로 확률이나 통계 등의 확장과는 거리가 있는데 지금 소개하는 방법은 확률 등으로 확장성이 매우 뛰어나다. 그래서 달달 외우라고 하고 싶은 심정이다.

중요한 장이라 몇 개의 절로 나누어 생각한다. 먼저 이항계수를 좀더 ‘문제의 본질’의 측면에서 바라보고, 그 개념을 바탕으로 문제를 동적 계획법으로 다시 푼다. 그리고 이 방법의 장점을 설명한다음, 생각을 뒤집어 다시 한 번 구현해본다.

3.1. 문제 다시 보기

1번과 2번 구현은 사실 이항계수의 개념보다는 정의에 충실한 방법이다. 이항계수는 개념적으로는 n 개의 품목 중 k 개의 아이템을 뽑는 조합의 수이지만 1, 2번은 개념에서 유도되는 성질만으로 문제를 해결했다. 그러니까, 내 느낌에는 저 구현들에서 뭔가 뽑는다는 생각이 직관적으로 들지 않는다.

이번 3번 방법은 그 과정이 실제로 ‘뽑는 작업’을 수반한다.


n 에 대해 k 개의 아이템을 뽑는다…는 경우의 수는 조금만 달리 생각하면 아이템을 선택할 기회가 n 번 있을 때 결국 k 개를 뽑았을 경우의 수와 일치한다. 같은 말 아닌가 하고 말할 수 있지만 후자는 각 기회가 분리될 수 있다.

  • 주어진 기회는 n 번이며 각 기회에서 우리가 선택할 수 있는 전략은 1. 선택하거나, 2. 선택하지 않거나 이다.
  • 우리는 0번에서 시작해서 한 번씩 선택하며, 결국 n 번째까지 선택했을 때 k 개가 선택된 경우의 수를 알고 싶다.

그렇다면, 0번째부터 시작해서 각 단계마다 하나를 선택하거나 선택하지 않는 방법을 모두 계산해서 최종적으로 k 개가 모인 경우만 세보자.

3.2. 구현해보기

2번에서도 하나의 문제가 그보다 작은 부분문제로 나뉘었다. 여기서도 문제가 나뉘지만, 그 정의가 완전히 다르다.


func(times, got) : 그동안 times만큼 기회가 있었고, 그동안 got만큼 선택했을 때, n번째에 다다랗을 때 k개를 선택하는 경우의 수


위의 상황에서, 결국 주어진 기회를 모두 사용했고(times = n 과 같고) & 결과 k 개가 선택되었다면(got = k) 조합이 하나 완성되었기에 1을 반환하고, k 개가 완성되었다면 세면 안 되기 때문에 0을 반환한다.

실제 코드를 확인하자.

def bino_coef(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] = choose(times+1, got) + choose(times+1, got+1)
	return cache[times][got]

    # 6.
    return choose(0, 0)
  1. n 개의 품목 중 k 개를 선택하는 조합의 수를 반환하는 ‘bino_coef’ 함수를 정의하고 캐쉬를 초기화한다.
    여기서 눈여겨볼 것이 값을 이전과 달리 -1로 초기화하고 캐시의 크기도 (n+1) * (n+1) 로 키웠는데 그 이유는 잠시 뒤 확인한다.
  2. 이 기회에 선택할지, 안 할지를 결정하는 choose 함수를 만들었다. 인자로는 그 동안의 기회를 나타내는 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 인 경우만 합산해서 결과를 내놓는다.


이제 왜 캐쉬의 크기가 2번과 달리 더 켜졌는지와 캐쉬의 모든 초기값이 -1인지를 이해할 수 있다.
2번의 경우는 우리가 선택하는 가짓수를 통제했기 때문에 (n+1) * (r+1) 로도 충분했지만 이번에는 컴퓨터가 n 번 동안 0개부터 n 개를 선택하는 값을 모두 만들기 때문에 캐쉬를 키워줘야 했다. 가령 n 개 중에 n 개 선택하는 조합의 수는 2번식의 캐쉬에 담을 수 없다.

초기값의 경우는 캐쉬의 값을 계산했는지의 여부는 0보다는 -1이 더 확실하게 파악할 수 있기 때문이다. 이항계수 문제에서 k 가 n 보다 크면 값은 무조건 0이다. 개념적으로 당연하다. 그런데 캐쉬에 값이 0으로 되어 있으면 이게 계산한 값인지, 아니면 초기화된 값인지 알 수 없다. 경우의 수는 0보다 작을 수 없다. 그래서 초기값으로 -1을 선택한 것이다.


작은 값으로 실험을 해보자. 기회가 한 번일 때 그중 한 번 선택했을 때, 선택하지 않았을 때 모두 1로 정상적으로 나온다. n 을 2, 3, … 등으로 키워 나가면 (0, 0)부터 시작하는 트리를 그릴 수 있다는 것을 알 수 있다. 이 트리를 한 번 그려보면 확실히 이해할 수 있다. 나도 그렇게 했다.

3.3. 함수 확장하기

앞서 이 방법의 장점은 확장성이 뛰어난 것이라고 말했다. 실제로 확장해보자.


지금까지의 코드는 n 개중 k 개를 선택하는 이항계수를 선택하는 코드였지만, 문제에 따라서는 ‘100개의 품목 중에서 80개 이상 선택하는 경우의 수를 구하여라’, ‘100번의 시도 끝에 5번 이하로 성공했을 경우의 수를 구하여라’와 같이 k 가 범위로 주어질 수도 있다.

이때에는 3번 코드를 한 줄만 바꿔주면 된다. 가령 최종적으로 k 개 이상 선택된 경우의 수는 3번 코드의 3번 부분을 살짝 손봐주면 된다.

if times == n:											# 3.
    return got >= k

아까는 got == k로 마지막에 선택한 개수가 k 개인 경우만 1을 반환했다. 이때는 got 이 k 보다 커도 0이 나왔는데 위와 같이 바꾸면서 k 개 이상이면 모두 1을 반환한다. 이하는 부호만 반대로 바꿔줘면 된다.


또한 다음 확장은 위를 확률을 구하는 함수로도 바꿀 수 있다는 것이다.
가령 이번에는 동전을 n 번 던질 때 앞면이 k 개가 나오는 확률을 계산하는 문제를 살펴보자. 이 문제는 단순한 3번식을 ‘2 ^ n’으로 나눠주면 구할 수 있지만 3번식의 5번 부분을 살짝만 바꿔줘도 구할 수 있다.

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

원식의 5번 부분이다. 다음 단계로 함수를 진전시키는데 이를 확률로 확장하려면 각 choose 식 앞에 확률을 곱해주면 된다.

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

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

이 방법의 장점은 각 사건의 확률이 동전 던지기와 달리 동일하지 않거나, 사건의 개수가 2개가 아닌 여러 개일 때로 응용이 가능하다는 것이다. 총 확률의 합이 1이기만 하면 된다.

이 둘을 조합해 동전을 10번 던져 앞면이 8번 이상 나올 확률을 구하는 함수를 짜보면 다음과 같다.

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)


0.0546875

정말 아름다운 일이 아닐 수 없다! 내가 이항계수 포스트를 쓰기로 한 것은 이 함수를 알게 된 것을 기록하기 위해서였다.

이 식은 원점부터 시작해서 양갈래로 나뉘는 트리를 그리는 것을 꼭 추천한다. 우리 식은 초기 (0, 0)부터 시작해서 올라가는 방법을 택했다. 그래서 난 Bottom-up이라고 부른다.

3.3. 한 번 더 비틀기: Top-Down으로 구현

여기까지 온 거 조금 더 나아가보자. 동전을 던져서 앞면이 나왔으면 뒷면이 나오지 않은 것이고, 로또에 당첨된 것은 로또에 당첨되지 않는 것을 하지 않은 것이며, 내가 오늘 생존하면 난 오늘 죽음을 피한 것이다. 사건을 반대방향으로 시야를 뒤집어 생각하면 도움이 될 때가 많다.

우리의 문제는 n 개의 아이템 중 k 개의 아이템을 선택하는 것이다. 그렇다면 이 문제는 동시에 n 개의 아이템 중 선택하지 않는 것을 n-k 번 선택하는 것과 동일하다. 이는 이항계수의 성질과도 일치한다.

3번식은 기본적으로 제로에서 시작해 하나씩 추가해 k 개가 되는지 확인한다. 그래서 Bottom-up이라고 이야기했다. 그렇다면 같은 식을 개념을 살짝 뒤집어서 꽉 채운 상태에서 하나씩 빼나가면서 최종적으로 n-k 개가 되는지 확인하면 어떨까? 본질적으로 똑같다. 일주일 동안 커피를 마실 날을 결정하는 것은 일주일 동안 커피를 마시지 않을 날을 결정하는 것과 같으니까! 이런 접근을 Top-down 이라고 하겠다.

Top-down 접근방식으로 3번을 재구성하면 다음과 같다.

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

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

    # 2.
    def choose(times, left):
        # 3.
        if times == 0:
	    return left == 0

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

	# 5.
	cache[times][left] = choose(times-1, left) + choose(times-1, left-1)
	return cache[times][left]

    return choose(n, n-k)

시야를 바꾼다. 이번에는 times 번 안에 left(n-k) 개를 모두 털어야 한다. 내가 기회를 쓸 때마다 기회는 줄어들고, 하나씩 털 때마다 남은 개수도 하나씩 줄기 때문에 아까와 달리 ‘-1’이 주로 사용되었다. 조금 더 비관적으로 보이기도 한다.

마치며

이항계수를 구현하는 여러 가지 코드를 살펴보았다. 팩토리얼을 사용하는 일반적인 방법부터 동적 계획법 연습용으로 많이 쓰이는 표준 코드, 그리고 조합의 의미를 살리고 확장성이 뛰어난 다른 한 가지 방법까지. 사실 이 포스트는 세 번째 코드를 위해 작성했다.

언제나 문제를 푸는 방법은 단 한 가지가 아니다. 맞닥뜨린 문제에 대해 다양하게 접근하고 구현해보자. 그렇기에 3번 코드를 굳이 두 가지 방법을 같이 제시했고, 이는 아무리 생각해도 의미 있는 시도였다고 생각한다. 그리고 조금은, 철학적이기까지 한 것 같다.

또 어떤 알고리즘이 기다리고 있을지. 더 나은 코드를 위한 우리의 도전은 멈추지 않는다.

Twitter Facebook Google+
# Algorithm # binomial_coefficient