이항 계수 및 관련 알고리즘 정리

이항 계수

한 문장으로 말하자면, 두 개의 항(이항)을 전개하여 계수로 나타낸 것
즉, $(a + b)^n$ 을 전개하였을 때 계수를 나타내는 것이다.

사실 필자는 여기까지는 이해를 못했다가, $\binom{n}{k}$가 조합 ${}_nC_k$를 의미한다는 것을 보고 감이 잡혔다.

위 $(a + b)^n$에서
n = 2인 경우는 $a^2 + 2ab + b^2$이고, 계수는 [1, 2, 1]이다.
n = 3 인 경우는 $a^3 + 3a^2b + 3ab^2 + b^3$ 이고, 계수는 [1, 3, 3, 1]이다.

이러한 이항 계수는 n의 제곱에 대해 전개하면 다음과 같은 항이 나타난다.
$(a + b)^n = [a^nb^0, a^{n - 1}b^1, a^{n - 2}b^2, ..., a^{n - r}b^r, ..., a^2b^{n - 2}, a^1b^{n - 1}, a^0b^n]$
위 내용은 계수는 제외하고 항만 나타낸 것이다.
각 항에서 계수를 구하고 싶다. 즉, $(a + b)^n$을 전개하였을 때, $a^{n - r}b^r$에 대한 계수를 구하는 것이 목표이다.

그렇다면 계수는 어떻게 구해야 할까?
먼저 $(a + b)^3$을 봐보자.
$(a + b)^3 = (a + b)(a + b)(a + b)$이다. 이때 각 b를 $b_1$, $b_2$, $b_3$ 으로 생각해보자.

그렇다면
$(a + b)(a + b)(a + b)$ = $(a + b_1)(a + b_2)(a + b_3)$이다.
$(a + b_1)(a + b_2)(a + b_3)$ = $a^3 + (b_1 + b_2 + b_3)a^2 + (b_1b_2 + b_2b_3 +b_3b_1)a + b_1b_2b_3$ 이 된다.

위 식을 해석해보면
$a^3$ 항은 $[b_1, b_2, b_3]$ 중에서 하나도 뽑지 않았다. 즉 0개를 뽑는다.
$a^2$ 항은 $[b_1, b_2, b_3]$ 중에서 하나씩 뽑아서 모두 더한 값이다.
$a^1$ 항은 $[b_1, b_2, b_3]$ 중에서 두개씩 뽑아서 곱한 후 모두 더한 값이다.
$a^0$ 항은 $[b_1, b_2, b_3]$ 중에서 세개를 뽑아 곱한 값이다.

쉽게 설명하자면 b가 n개 있을 때, n개중 r개를 뽑는다는 말이다.
n개중 r개를 뽑는다? -> 바로 ${}_nC_r$이 생각났다!

즉,
$a^3$ 항은 $[b_1, b_2, b_3]$ 중에서 하나도 뽑지 않았으니 ${}_3C_0$이 된다.
$a^2$ 항은 $[b_1, b_2, b_3]$ 중에서 하나씩 뽑는 것이니 ${}_3C_1$이 된다.
$a^1$ 항은 $[b_1, b_2, b_3]$ 중에서 두개씩 뽑는 것이니 ${}_3C_2$이 된다.
$a^0$ 항은 $[b_1, b_2, b_3]$ 중에서 세개를 뽑는 것이니 ${}_3C_3$이 된다.

그렇다면 $(a + b)^n$에서는?

$(a + b)^n = {}_nC_0a^nb^0 + {}_nC_1a^{n-1}b^1 + {}_nC_2a^{n-2}b^2 + ... + {}_nC_ra^{n-r}b^r + ... + {}_nC_{n-1}a^1b^{n-1} + {}_nC_na^0b^n$ 이 된다.

즉, $(a + b)^n = \displaystyle\sum_{r=0}^{n}{}_nC_ra^{n-r}b^r$ 이다.

아무튼! 결론적으로 이항계수 $\binom{n}{k}$를 구해달라는 뜻은 ${}_nC_k$를 구하여라 라는 뜻과 같다!

그렇다면 ${}_nC_k$은 어떻게 구하나?

고등학교 시간때 배운걸 기억해보자.
${}_nC_r = \frac{n!}{r!(n - r)!}$ 이다.

즉, $n!$과 $r!$, $(n - r)!$ 을 구해서 계산하면 되겠다.
하지만, 적은수에서는 가능하지만 크기가 커진다면? 엄청난 메모리를 소모할 수 있겠다.
따라서 다른 방식으로 문제를 푸는 것이 바람직하다.

먼저 조합에 대한 성질에 대해 알아보자

1. ${}_{n+1}C_{r+1} = {}_nC_r + {}_nC_{r + 1}$ 이다.

해당 성질에 대해 알고 있었다고하면 필자는 까먹었다...

따라서 풀어 써보자면,

${}_{n+1}C_{r+1} = \frac{(n + 1)!}{(r + 1)!(n + 1 - (r + 1))!} = \frac{(n + 1)!}{(r + 1)!(n - r)!}$ 이다.

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

$\frac{n!((r + 1) + (n - r))}{(r + 1)!(n - r))!} = \frac{n!(n + 1)}{(r + 1)!(n - r))!} = \frac{(n + 1)!}{(r + 1)!(n - r))!}$ 이다.

즉 ${}_{n+1}C_{r+1} = {}_nC_r + {}_nC_{r + 1}$이다!!!
그렇다면, ${}_nC_r = {}_{n - 1}C_{r - 1} + {}_{n - 1}C_r$일 것이다.
위 점화식을 파스칼의 삼각형이라 부른다.

2. ${}_nC_0 = {}_nC_n = 1$이다.

해당 내용은 알고 있다.

위 두가지를 사용하면 재귀 알고리즘을 통하여 구현이 가능하다

int pascalRule(int N, int K){

	//2번 성질
	if(N == K || N == 0){
    	return 1;
    }
    
    //1번 성질
    return pascalRule(N - 1, K - 1) + pascalRule(N - 1, K);
}

하지만, 위 코드처럼 구현하여 재귀 알고리즘을 사용할 경우, 이미 구한 값이더라도 한번 더 구해야하는, 즉 중복 문제가 발생한다. 결국 메모이제이션을 하지 않으면 성능은 많이 떨어지게 된다.

따라서 메모이제이션을 해주어 더욱 효율이 좋은 알고리즘으로 구현 할 수 있다.

int[][] dp = new int[N + 1][K + 1];


int pascalRule(int N, int K){
	
    //이미 값을 구한 경우
    if(dp[N][K] > 0){
    	reutnr dp[N][K];
    }
	
	//2번 성질
	if(N == K || K == 0){
    	return dp[N][K] = 1;
    }
    
    //1번 성질
    return dp[N][K} = pascalRule(N - 1, K - 1) + pascalRule(N - 1, K);
}

필자는 가장 효율적인 아래 알고리즘으로 BOJ 11050 이항 계수 1을 풀었다.
해당 알고리즘 풀이는 이항 계수 1 여기에 있다.

응용 문제(BOJ 11051 이항 계수 2)

해당 문제에서는 위에서 설명한 이항 계수 내용에 추가적으로 구한 값을 10007로 나눈 나머지값을 구하여야 한다.
하지만 N의 범위가 $1 \le N \le 1000$ 이다.
기본적으로 long형은 최대 $2^{63} -1$, 약 92경?!?! 이다.
하지만 20!의 경우 2,432,902,008,176,640,000 = 약 243경이다....
20만 넘어가도 계산 long 범위를 넘어가므로, 계산할수가 없어진다.

그렇다면 어떻게 해야하는가?
이때 필요한 성질이 모듈러 연산이다.
모듈러 연산이란,
$(a + b)\;mod\;m = ((a \;mod \;m) + (b \;mod \;m)) \;mod \;m$
$(a \times b)\;mod\;m = ((a \;mod \;m) \times (b \;mod \;m)) \;mod \;m$
을 만족한다.

이해가 안간다면, 아래 성질 유도 과정을 봐보자.

먼저 $a\;mod\;m = r_1,\;b\;mod\;m = r_2$ 라고 가정하자.

그렇다면, $a = mq_1 + r_1$ 이고, $b = mq_2 + r_2$ 이고,

$a + b = m(q_1 + q_2) + r_1 + r_2$ 이다.

여기서, $r_1 + r_2 = m*q_3 + r3$ 이라고 가정해보자.

그렇다면 $a + b = m(q_1 + q_2 + q_3) + r_3$ 이다.

즉, $(a + b)\;mod\;m = r_3$ 이므로,
$(a + b)\;mod\;m = (r1 + r2) \;mod \;m$이고,
$(a + b)\;mod\;m = ((a \;mod \;m) + (b \;mod \;m)) \;mod \;m$ 이다.

곱셈 연산 유도는 다음과 같다.

먼저 $a\;mod\;m = r_1,\;b\;mod\;m = r_2$ 라고 가정하자.

그렇다면, $a = mq_1 + r_1$ 이고, $b = mq_2 + r_2$ 이고,

$a \times b = (mq_1 + r_1) \times (mq_2 + r_2)$ 이다.

전개하면 $m^2q_1q_2 + mq_1r_1 + mq_2r_1 +r_1r_2$ 가 되고,

m의 배수는 mod m 에서 모두 0이 되므로

$(a \times b) \;mod\; m = (r_1 \times r_2) \;mod \;m$ 이다.

따라서 $(a \times b)\;mod\;m = ((a \;mod \;m) \times (b \;mod \;m)) \;mod \;m$ 이다.

위 모듈러 연산 내용을 코드로 바꿔보면,

(a + b) % m = ((a % m) + (b % m)) % m 이고,
(a b) % m = ((a % m) (b % m)) % m 이다.

우리는 ${}_nC_r = {}_{n - 1}C_{r - 1} + {}_{n - 1}C_r$ 해당 값을 메서드로 구현해 사용했었다.

여기에서 ${}_nC_r \;mod\;p= ({}_{n - 1}C_{r - 1} + {}_{n - 1}C_r)\;mod\;p$ 이다.
따라서, $({}_{n - 1}C_{r - 1} + {}_{n - 1}C_r)\;mod\;p = ({}_{n - 1}C_{r - 1}\;mod\;p + {}_{n - 1}C_r\;mod\;p)\;mod\;p$ 이다.

해당 식을 추가해주면 되겠다.

해당 내용의 풀이는 이항 계수 2 를 참고하자.

응용 문제(BOJ 11401 이항 계수 3)

해당 문제는 N의 크기가 무려 4000000 이고, 1,000,000,007로 나눈 나머지를 출력하는 문제이다.

위에서 구현한 이항 계수 1, 2의 방식으로 푼다면, dp 배열이 400만 * 400만 이 나오기 때문에, 반드시 메모리 초과가 발생 할 것이다.

따라서 해당 문제에서는 페르마의 소정리를 이용하여 구현해야 한다.

모듈러 연산은 위에 적어 놓았다.

기존 방법은 계산한 값에서 모듈러 연산을 적용해 나머지를 구하였는데,
이번에는 ${}_nC_r = \frac{n!}{r!(n - r)!}$ 값 자체에 모듈러 연산을 수행할 것이다.

하지만 모듈러 연산에는 나눗셈(분수 꼴)에 대한 연산은 존재하지 않는다. 그렇다면 어떻게 해아할까?

분수를 뒤집어 $\frac{n!}{r!(n - r)!} = n! \times {r!(n - r)!}^{-1}$ 로 만들 수 있지 않을까?

그렇다면 $n! \times {r!(n - r)!}^{-1}\;mod\;p$ = $(n!\;mod\;p) \times ({r!(n - r)!}^{-1}\;mod\;p)\;mod\;p$ 일 것이다.

하지만 ${r!(n - r)!}^{-1}\;mod\;p$ 해당 값을 어떻게 구할 수 있을까? ${r!(n - r)!}^{-1}$ 값은 어쨌든 0.xxx 꼴로 나올 것이다.

여기서 페르마의 소정리를 사용하게 된다.

페르마의 소정리는 다음과 같다.

a는 정수, p는 소수이고 a와 p는 서로소일때,
$a^p \equiv a(mod\;p)$
이고,
$a^p\;mod\;p \equiv a\;mod\;p$ 이다.

또한,
$a^{p - 1}\;mod\;p \equiv 1(mod\;p)$ 이다.
즉, $a \times a^{p - 2}\;mod\;p \equiv 1(mod\;p)$

위 내용으로서, $a^{-1}(mod\;p)$ = $a^{p - 2}(mod\;p)$ 이 성립한다.

해당 문제에 적용시켜보면,

$a = r!(n - r)!$이고, p = 1,000,000,007 이다.
즉, $r!(n - r)!^{-1}$ = $r!(n - r)!^{1,000,000,007 - 2}$이다.

최종적인 식은
$n! \times {r!(n - r)!}^{1,000,000,007 - 2}\;mod\;p$ = $(n!\;mod\;p) \times ({r!(n - r)!}^{1,000,000,007 - 2}\;mod\;p)\;mod\;p$ 이 된다.

헉. 그렇다면 저 큰 제곱은 어떻게 구하나??
곱셈에서 사용한 내용을 보면 쉽다. 해당 문제는 A를 B번 곱했을때 C로 나눈 나머지의 값을 출력한다.

분할 정복 및 모듈러 연산을 사용하여 A를 B번 곱했을때 C로 나눈 나머지의 값을 알 수 있다.

위 방식을 사용하여 구현한다면 다음과 같다.

private static void solution() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        long N = Long.parseLong(st.nextToken());
        long K = Long.parseLong(st.nextToken());

        long top = factorial(N);

        long bottom = factorial(K) * factorial(N - K) % P;

        System.out.println(top * compute(bottom, P - 2) % P);
    }

    private static long factorial(long N) {
        long num = 1L;

        while (N > 1) {
            num = (num * N) % P;
            N--;
        }
        return num;
    }

    static long compute(long a, long b) {
        if (b == 1) {
            return a % P;
        }

        long tmp = compute(a, b / 2);

        if (b % 2 == 1) {
            return (tmp*tmp % P) * a % P;
        }

        return tmp * tmp % P;
    }

해당 풀이는 이항 계수 3를 참고하면 된다.