이항계수 알고리즘

 

 

이항계수

이항계수란 n개의 원소에서 k개의 원소를 뽑아내는 경우의 수를 의미하며, 공식은 다음과 같다.

$ \binom{n}{k} = \left\{\begin{matrix} \frac{n!}{k!(n-k)!} & (0\leq k \leq n) \\ 0& (k<0) \\ 0& (k>n) \end{matrix}\right. $

 

혹은 $ _nC_k $ 로 나타낸다.

 

이항계수를 구하기 위한 알고리즘은 여러 종류가 있는데, 이중 몇가지를 정리하겠다.

 

이항계수의 성질

$ 1. \binom{n}{k} = \binom{n}{n-k} \\ 2. \binom{n}{k} = \binom{n-1}{k} + \binom{n-1}{k-1} \\ 3. \sum_{k=0}^n \binom{n}{k} = 2^n $

 

 

1. 팩토리얼-재귀 방법

$ \binom{n}{k} = \left\{\begin{matrix} \frac{n!}{k!(n-k)!} & (0\leq k \leq n) \\ 0& (k<0) \\ 0& (k>n) \\ \end{matrix}\right. $

long long factorial (int n) {
  if (n == 0) return 1;
  
  long long result = 1;
  for (int i = 2; i <= n; i++)
    result *= i;
  
  return result;
}


long long binomial_coefficient (int n, int k) {
  return factorial(n) / factorial(n-k)*factorial(k) ;
}

 

 

2. 재귀-이항계수의 성질

$ \binom{n}{k} = \binom{n-1}{k} + \binom{n-1}{k-1} $

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

 

long long binomial_coefficient (int n, int k) {
  if (k == 0 || n == k) return 1;
  
  else 
    return binomial_coefficient(n-1, k) + binomial_coefficient(n-1, k-1);
}

중복된 연산이 있기 때문에 n, k가 조금만 커진다면 성능이 매우 떨어진다.

 

 

3. 동적 계획법 이용

3-1. 이항계수의 정의

long long memo[n+1][r+1];

void binomial_coefficient (int n, int k) {
  
  // nC0, nCn = 1로 초기화
  for (int i = 0; i < n; i++) {
    memo[i][0] = 1;
    memo[i][i] = 1;
  }
  
  // nCk = n-1Ck + n-1Ck-1
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= k; j++) {
      memo[i][j] = memo[i-1][j] + memo[i-1][j-1];
    }
  }
}

 

3-2. 완전탐색 Memoization

앞에서는 이항계수의 정의만을 이용한 코드였다면 이제는 실제로 뽑는 작업을 코드로 옮겨보도록 하자. 실제로 뽑는 작업을 코드로 옮겼을 때 이항계수 변형문제에서 좀 더 빛을 발할 수 있다.

 

아이템을 선택할 기회가 n번 있을 때 k개를 뽑았을 경우의 수와 일치한다. 즉 아래와 같이 나눠볼 수 있다.

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

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

 

long long choose (times, pick){ ... }

// 그동안 times만큼 기회가 있었고, 그동안 pick만큼 선택했을 때, n번째에 왔을 때 k개를 선택하는 경우의 수

주어진 기회를 모두 사용했고 (times = n), 결과 k개가 선택되었다면 (pick = k)

조합이 하나 완성되었기에 1을 반환하고, k개가 완성되었다면 세면 안 되기 때문에 0을 반환한다.

 

#include <iostream>

using namespace std;


long long memo[101][101];
int n, k;


// 기회에 선택할지, 안 할지를 결정하는 choose 함수
// 그 동안의 기회를 나타내는 times 와, 그동안 선택한 아이템의 개수인 pick 을 받는다. 
// times번까지 pick개를 선택했을 때, 최종적으로 n번의 기회를 소진 시에 선택한 개수가 k가 되는 경우의 수를 반환하는 함수
long long choose (int times, int pick) {
    
  // n번의 선택을 마쳤다면, 함수를 종료시킨다. 이때, 그동안 선택된 개수가 문제에서 주어진 k와 일치하면 n개 중 k를 선택했으므로 1을 반환하되, 값이 다르면 0을 반환한다.(세지 않는다)
  	if (k > n) return 0;
    if (times == n) return pick == k;

		// -1은 초기화 값으로 현재 값이 -1이라는 얘기는 이 위치의 값은 건드린 적이 없다는 것, 그러니까 이전에 계산하지 않았기 때문에 계산해야 된다는 뜻이다
    if (memo[times][pick] == -1) 
      memo[times][pick] = choose(times+1, pick) + choose(times+1, pick+1);
		   
    return memo[times][pick];
  }


int main() {
    cin >> n >> k;
  
    for (int i = 0; i < n+1; i++)
      memset(memo[i], -1, sizeof(long long)*(n+1));
  
  	// 함수가 계속 호출되고, 인자가 점점 커지며 결국 n 번째까지 이를 것이고 그때 선택한 개수가 k 인 경우만 합산해서 결과를 내놓는다.
    cout << choose(0, 0) << endl;
    return 0;
}

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

 

 

3-3. 심화과정 - 함수의 확장

• k가 범위로 주어지는 경우

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

 

이때에는 코드를 한 줄만 바꿔주면 된다. 가령 최종적으로 k개 이상 선택된 경우의 수는 아래와 같이 수정해주면 된다.

if (times == n)	return pick >= k

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

 

• 확률을 구해야하는 경우 (이 부분 동작 안함 수정 필요)

가령 이번에는 동전을 n번 던질 때 앞면이 k개가 나오는 확률을 계산하는 문제를 살펴보자.

memo[times][pick] = 0.5 * choose(times+1, pick) + 0.5 * choose(times+1, pick+1)

이를 확률로 확장하려면 각 choose식 앞에 확률을 곱해주면 된다.

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

 

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

 

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

// 이거 안댐

#include <iostream>

using namespace std;


double memo[101][101];
int n, k;


double choose (int times, int pick) {
    
  	if (k > n) return 0;
    if (times == n) return pick >= k;
    if (memo[times][pick] != -1) return memo[times][pick];
		
    memo[times][pick] = 0.5*choose(times+1, pick) + 0.5*choose(times+1, pick+1);
    
    return memo[times][pick];
  }


int main() {
    cin >> n >> k;
  
    for (int i = 0; i < n+1; i++)
      memset(memo[i], -1, sizeof(double)*(n+1));
  
    cout << choose(0, 0) << endl;
    return 0;
}

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

 

 

3-3.1 Top-Down으로 구현

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

#include <iostream>

using namespace std;


long long memo[101][101];
int n, k;


long long choose (int times, int pick) {
    
  	if (k > n) return 0;
    if (times == 0) return pick == 0;
    if (memo[times][pick] == -1) 
    	memo[times][pick] = choose(times-1, pick) + choose(times-1, pick-1);
    
    return memo[times][pick];
  }


int main() {
    cin >> n >> k;
  
    for (int i = 0; i < n+1; i++)
      memset(memo[i], -1, sizeof(long long)*(n+1));
  
  	// 5
    cout << choose(n, n-k) << endl;
    return 0;
}

 

 

4. 페르마의 소정리 (공사중)

작은 범위의 n에서는 위의 방법으로 풀수 있다. 하지만 n이 조금만 커진다면 꽤 시간이 많이 걸린다.

 

$ a^p \equiv a\ (mod\ p) \\ = a^{p-1} \equiv 1\ (mod\ p) \\ = a^{p-2} \equiv \frac{1}{a} \ (mod \ p) $

 

즉, a의 역수는 $ a^{p-2} $

$ _nC_r = \frac{n!}{r!(n-r)!} \%\ p \\ if,\ A = n!\ , \ B = r!(n-r)! \\ then, A*B^{-1} \%\ p \\ A*B^{p-2} \%\ p $

 

$ B^{p-2}$을 구하기 위해 2진수 표현법을 사용핰다.

$ A^{2a} = (A^a)^2 \\ A^6a = (A^a)^6 = (A^a)^4 * (A^a)^2 = (A^a)^{(2^2)} * (A^a)^2 $

 

 

 

da