조합(Combination)과 이항 계수를 python으로 구현해보자.

조합의 정의

조합(Combination) : 서로 다른 n개의 원소에서 r(단, 0<r<n)를 중복 없이, 순서를 고려하지 않고 선택하는 것.
중요한 것은 순열과 같이 선택해서 나열하는 것이 아닌, 선택하기만 하기 때문에 순서는 중요하지 않다는 것이다. (1,2,3,4,5)에서 (2,3)을 뽑는 것과 (3,2)를 뽑는 것을 같은 것으로 본다는 말이다.

 

n개 중에서 r개를 뽑는 조합을 다음과 같이 표현할 수 있다.

$$ _nC_r = \binom{n}{r} $$

조합을 다룰때 빠질 수 없는 순열은 다음과 같이 표현할 수 있다.

$$ {}_n{\rm P}_r $$

순열과 조합

$$ {}_n{\rm P}_r = \frac{n!}{(n-1)!} $$

$$ _nC_r = \frac{n!}{(n-r)!r!} $$

순열과 조합을 구하는 공식은 위와 같다. 순열과 조합이 구하는 공식이 비슷하나 조합에는 분모에 r! 이 추가되어 있는 것을 볼 수 있다. 이는 순열에서는 원소는 같고 순서는 다른 경우의 수를 제거해 주는 역할을 한다.

이항계수

이항계수란, 주어진 크기 집합에서 원하는 개수만큼 순서없이 뽑는 조합의 가짓수를 일컫는다. ‘이항’이라는 말이 붙은 이유는 하나의 아이템에 대해서는 ‘뽑거나, 안 뽑거나’ 두 가지의 선택만이 있기 때문이다. 

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

$$ \binom{n}{r} = _nC_r = \frac{n!}{(n-r)!r!} (단, 0 \le r \le n) $$

위에서 봤던 내용이다. 하지만, 여기서 추가적으로 이항계수의 중요한 성질을 알아보자.

$$ \displaylines{ \binom{n}{r} = \binom{n}{n-r} \quad \cdots 1 \\ \\ \binom{n}{r} = \binom{n-1}{r} + \binom{n-1}{r-1} \quad \cdots 2 \\ \\ \sum_{r=0}^{n} \binom{n}{r} = 2^n \quad \cdots 3  }$$

• 1번 성질 : n개 중에 r개를 선택하는 것은 선택하지 않을 나머지 것들을 고르는 것과 같다고 할 수 있다.
• 2번 성질 : 이항계수의 정의를 조금만 변형해하면 다음 성질을 유도할 수 있다.
  유도하는 과정이 궁금하면 아래를 참고하자.

$$ \binom{n}{r} = \frac{n!}{(n-r)!r!} = \frac{(n-r+r)(n-1)!}{r(r-1)!(n-r)(n-r-1)!}  $$
$$=  \frac{(n-r)(n-1)!}{r(r-1)!(n-r)(n-r-1)!} +  \frac{r(n-1)!}{r(r-1)!(n-r)(n-r-1)!} $$
$$ = \frac{(n-1)!}{r(r-1)!(n-r-1)!} +  \frac{(n-1)!}{(r-1)!(n-r)(n-r-1)!} $$
$$= \frac{(n-1)!}{r!(n-r-1)!} +  \frac{(n-1)!}{(r-1)!(n-r)!}  = \binom{n-1}{r} + \binom{n-1}{r-1} $$

• 3번 성질: 파스칼의 삼각형과 연관이 깊은 식이다.

python으로 구현

이항계수의 정의를 이용해 구현하기

def facto(n):
    return n*facto(n-1) if n>1 else 1
   
def binomial_coefficient(n, r):
	return facto(n) // facto(r) // facto(n-r)

팩토리얼은 간단하게 재귀함수를 이용해 구현하였다. 한줄로 깔끔하고 재귀함수로 표현되어 있어 이해하기도 어렵지 않다. 하지만 팩토리얼 연산은 지수연산 보다도 빨리 증가하는데, n이 15만 되어도 1307674368000(약 1.3조)가 되어버리고, 재귀함수 또한 깊어지게 되면 비효율적이게 된다. 위에서 알아봤던 이항계수를 통해 더 효율적으로 풀어낼 수 있다.

이항계수의 성질 이용해 구현하기

이 방법은 앞서 알아봤던 이항계수의 두 성질을 이용해서 구현한다. 1번 성질을 통해 다음을 알 수 있다.

$$ \binom{n}{0} = \binom{n}{n} = 1 $$

전체 집합에서 아무것도 고르지 않는 방법은 1가지 뿐이고, 동시에 전부 선택하는 것 또한 1가지 방법뿐이다. 여기에 2번 성질을 이용하면, 주어진 이항계수를 보다 작은 두개의 부분식으로 쪼갤 수 있고, 이를 반복하다 r이 0이 되는 순간과 n==r 인 순간일 때는 위와 같이 1을 반환하게 구현할 수 있다. 그것이 아래의 코드이다

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

이항계수는 분명 팩토리얼로 정의된 연산이었는데 덧셈만으로 구할 수 있게 바꾸었다!! 이는 숫자가 커질수록 첫 번째 코드와는 비교할 수 없을 정도로 차이가 날 것이다. 우리가 이항계수의 정의를 이용해 구현한 코드의 시간복잡도는 $ O(n!) $이고, 이항계수의 성질을 이용해 구현한 코드의 시간복잡도는 $ O(2^n) $이다.

마치며

$ O(n!) $에서  $ O(2^n) $으로 시간복잡도가 줄어들기는 했지만, 여전히 느리다고 생각하지 않는가? 여기서 DP(Dynamic Programming), 즉 동적 계획법으로 훨씬 효율적으로 만들 수 있다. 동적 계획법 또한 추후에 알아보도록 하자.

이항 계수는 알고리즘을 공부할때 굉장히 중요한 개념 중 하나이기 때문에 확실히 공부해 두어야겠다.