Combination 개수 구하기 (Pascal's Triangle)
Problem Solving/Algorithm notes 2009.02.07 22:22
Combination(조합) 개수 구하는 방법은?
만약에 nCr을 구하는 프로그램을 c로 구현한다고 하면..
나는 당근 이렇게 짤것이다.. -_-
위와같이 짜다보면 직관적이긴 한데..
n이 조금만 커지면 중간에 overflow 나고 막장이 된다.. ㅠ_ㅠ
그런데 조합 개수를 파스칼의 삼각형을 이용하여 구할 수 있다
Binomial Theorem (이항정리)에 의해
(x+y)^n 을 전개했을 때 (x^p)*(y^q) 항의 계수는 놀랍게도 nCp 가 된다..
(여기서 당근 p + q = n 이다)
(x+y)^n 을 전개 해보자..
n = 0: 1
n = 1: x^1 + y^1
n = 2: x^2 + 2*x^1*y^1 + y^2
n = 3: x^3 + 3*x^2*y^1 + 3*x^1*y^2 + y^3
n = 4: x^4 + 4*x^3*y^1 + 6*x^2*y^2 + 4*x^1*y^3 * y^4
...
...
여기서 계수들만 쭉 뽑아서 나열해보면 규칙이 있다..
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
...
...
이게 바로 파스칼의 삼각형인데..
현재 원소의 값은 바로 위에줄에 있는 두개의 원소의 합과 같다..
이러한 규칙을 이용하여 DP로 쉽게 구현할 수 있다.. ㅎㅎ
만약에 nCr을 구하는 프로그램을 c로 구현한다고 하면..
나는 당근 이렇게 짤것이다.. -_-
1 long long get_combi(int n, int r)
2 {
3 int i, j;
4 long long res;
5 r = min(r, n-r);
6 res = 1;
7 for (i = 1, j = n; i <= r; i++, j--) {
8 res *= j;
9 res /= i;
10 }
11 return res;
12 }
2 {
3 int i, j;
4 long long res;
5 r = min(r, n-r);
6 res = 1;
7 for (i = 1, j = n; i <= r; i++, j--) {
8 res *= j;
9 res /= i;
10 }
11 return res;
12 }
위와같이 짜다보면 직관적이긴 한데..
n이 조금만 커지면 중간에 overflow 나고 막장이 된다.. ㅠ_ㅠ
그런데 조합 개수를 파스칼의 삼각형을 이용하여 구할 수 있다
Binomial Theorem (이항정리)에 의해
(x+y)^n 을 전개했을 때 (x^p)*(y^q) 항의 계수는 놀랍게도 nCp 가 된다..
(여기서 당근 p + q = n 이다)
(x+y)^n 을 전개 해보자..
n = 0: 1
n = 1: x^1 + y^1
n = 2: x^2 + 2*x^1*y^1 + y^2
n = 3: x^3 + 3*x^2*y^1 + 3*x^1*y^2 + y^3
n = 4: x^4 + 4*x^3*y^1 + 6*x^2*y^2 + 4*x^1*y^3 * y^4
...
...
여기서 계수들만 쭉 뽑아서 나열해보면 규칙이 있다..
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
...
...
이게 바로 파스칼의 삼각형인데..
현재 원소의 값은 바로 위에줄에 있는 두개의 원소의 합과 같다..
이러한 규칙을 이용하여 DP로 쉽게 구현할 수 있다.. ㅎㅎ
1 /* Combination (Pascal's Triangle) */
2
3 #include <stdio.h>
4 #include <string.h>
5 #define MAXN 51
6
7 /* combi[n][r] = n C r */
8 long long combi[MAXN][MAXN];
9 void get_combi()
10 {
11 int i, j;
12 for (i = 0; i < MAXN; i++) {
13 combi[i][i] = 1;
14 combi[i][0] = 1;
15 }
16 for (i = 0; i < MAXN; i++) {
17 for (j = 1; j < i; j++) {
18 combi[i][j] = combi[i-1][j-1] + combi[i-1][j];
19 }
20 }
21 }
2
3 #include <stdio.h>
4 #include <string.h>
5 #define MAXN 51
6
7 /* combi[n][r] = n C r */
8 long long combi[MAXN][MAXN];
9 void get_combi()
10 {
11 int i, j;
12 for (i = 0; i < MAXN; i++) {
13 combi[i][i] = 1;
14 combi[i][0] = 1;
15 }
16 for (i = 0; i < MAXN; i++) {
17 for (j = 1; j < i; j++) {
18 combi[i][j] = combi[i-1][j-1] + combi[i-1][j];
19 }
20 }
21 }
'Problem Solving > Algorithm notes' 카테고리의 다른 글
| Bell Number (0) | 2009.07.12 |
|---|---|
| Finding Minimum Path Cover in DAG (0) | 2009.06.15 |
| Plane Equation (평면의 방정식) (0) | 2009.04.16 |
| Ellipse (타원) (0) | 2009.04.15 |
| Modular Arithmetic 1탄 - Extended Euclid (2) | 2009.02.22 |
| Combination 개수 구하기 (Pascal's Triangle) (2) | 2009.02.07 |
| Josephus Problem (2) | 2009.01.01 |
| Number of Swap Operations (0) | 2008.07.24 |
| 소수 구하는 방법 (Sieve of Eratosthenes) (2) | 2008.07.15 |
| Horner's Rule (0) | 2008.05.04 |
| GCD SUM (0) | 2008.03.18 |
Comments
작은 Combination 은 파스칼의 삼각형 쓰면 되지만, 구하는 숫자가 커지면 배열에 저장할 수 없는 문제가 있는데..
큰 Combination 의 계산 방법이 여기 블로그에 있네...
http://blmarket.tistory.com/entry/큰-Combination
이거 설명좀.. ㅋㅋ ( 글만 읽어보니 이해가 잘 안감 )
음.. 저건 nCr mod M 을 구하는거네요..?
정수론의 모듈러합동 부분을 좀 봐야될거같아요..~