조합

머릿말

조합은 고등학교 때 정석으로 배울때는 이런거 배워서 뭐하나 싶지만, 나중에 알고리즘 공부를 하거나, 머신러닝 공부를 하거나, 실생활(?)에 있어서도 익혀두면 쓸모가 많은 개념이라는 생각이 듭니다. 고등학교때는 대충 넘어갔다가 나중에 다시 공부하게 되는 대표적인 수학 분야인 것 같아요.

 

조합의 기본

n개중 순서에 상관없이 k개를 고르는 경우의 수를 조합이라고 하고, $_{n}C_{k}$로 표현

기본 계산식은 다음과 같다.

$$_{n}C_{k} = {n\choose k} = {{n!}\over{k!(n-k)!}}$$

 

집합 분할하기

예시문제) 10명의 학생을 2명, 2명, 2명, 4명으로 분할하는 경우의 수는?

 

풀이) 10명중 2명을 순서에 상관없이 고르고 ($_{10}C_{2}$), 나머지 8명중 2명을 순서에 상관없이 고르고, ($_{8}C_{2}$), 나머지 6명중 2명을 순서에 상관없이 고르고, ($_{6}C_{2}$), 나머지 4명중 4명을 순서에 상관없이 고르고($_{4}C_{4}$).

 

이렇게 하면  $_{10}C_{2} \times _{8}C_{2} \times _{6}C_{2} \times _{4}C_{4} = 18900$이 답인 것 같지만, 

2명씩 나눈 저 세 집단은 간에는 순서가 없다고 봐야한다. 

 

따라서 결과를 $3!$로 나눈 3150이 답이 된다.

 

외부 링크

조합 계산기: http://ko.numberempire.com/combinatorialcalculator.php

n, k만 입력하면 계산해준다.

 

나이브 구현

 

#include <stdio.h>
 
int factorial(int n)
{
    if (n == 0) return 1;
    return n * factorial(n - 1);
}
 
int combination(int n, int c)
{
    if (n < c) return 0;
    return factorial(n) / factorial(c) / factorial(n - c);
}
 
int main(void)
{
    printf("%d\n", combination(10, 2));
    return 0;
 
}
 

 

DP구현

C(n,k) = C(n-1,k-1) + C(n-1,k)라는 성질 이용

typedef long long LL;
LL combination(int n, int k)
{
    const int MAX_N = 51;
    static LL dp[MAX_N][MAX_N] = { 0 };
 
    LL& res = dp[n][k];
    if (res) return res;
    if (n == k || k == 0)
        return res = 1;
    return res = combination(n - 1, k - 1) + combination(n - 1, k);
}

 

위에건 C(n,k)하나만 구하는거고 전체를 구해두려면 다음소스 사용

#include <stdio.h>
 
int main(void)
{
    const int n = 10;
    long long c[n + 1][n + 1] = { 0 };
    c[0][0] = 1;
    for(int i=1;i<=n;i++)
    {
        c[i][0] = 1;
        for(int j=1;j<=n;j++)
        {
            c[i][j] = c[i - 1][j - 1] + c[i - 1][j];
        }
    }
    printf("%d\n", c[10][2]);
    return 0;
 
}

 

N, K가 매우 클때 약분을 이용해서 구하는 방법

#include <stdio.h>
typedef long long LL;
LL combination(LL n, LL kk) {
    LL C[2];
    C[0] = 1;
    LL r = -1;
    for (LL k = 0; k <= kk + 1; ++k)
    {
        LL n0 = k % 2;
        LL n1 = (k + 1) % 2;
        C[n1] = (C[n0] * (n - k)) / (k + 1);
        if (k + 1 == kk) r = C[n1];
    }
    return r;
}
int main(void)
{
    printf("%d\n", combination(25, 12));
    return 0;
 
}