728x90
nCr 쉽게 구하기 (수정 20190604)
오랫만에 와서 살펴보니 코드와 예시를 든 이미지가 잘못되서 수정하였습니다 ㅜㅡㅜ
nCr 같은 경우는 n개의 숫자에서 r개를 뽑는 경우의 수이다. 경우의 수를 구하는 경우에서 많이 사용한다. nCr의 수식은 아래와 같다.
즉 매번 이 수식을 사용한다는 것은 n! , r!, (n-r)! 를 사용해야 한다. 즉 여기서 말하고자 하는 것은 이 것을 매번 사용할때마다 구하지 않고 미리 다 구해놓아서 그 숫자를 사용하는 것이다.
이것을 1개를 뽑는것 부터 n개를 뽑는 것 까지의 조합을 쭈욱 정리하다 보면 숫자의 특성이 나올 것이다.
위의 것에서 보면 1개에서 뽑는 경우의 수에서 6개의 경우수를 뽑는 것을 쭈욱 나열 한 건데 여기서 숫자가 어떻게 나오는 지에 대한 일정 패턴이 눈에 보일 것이다. 그 것은 바로 아래의 식이다.
저 식이 나오는 이유는 간단하다. 왜냐하면 n개의 공에서 r개를 뽑는 경우의 수는 어찌보면 n-1개의 공에서 r개를 뽑는 수와 n-1 개의 공에서 이미 하나를 뽑았다고 생각하고 r-1개를 뽑는 수를 더한것과 같기 때문이다.
즉 위의 성질을 이용하여서 미리 조합의 수를 구해놔서 그것을 호출하면 된다.
까지 미리 구하는 코드
그래서 50개에서 r 개를 뽑는 경우의 수까지 미리 만드는 코드로 예를 들겠다. 이 조합의 숫자는 2차원 배열로 만들 수 있다.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 | int main(void){ // [n][r] 이다. unsigned long long Combination[51][51] = {}; Combination[1][0] = 1; Combination[1][1] = 1; for (int i = 2; i <= 50; i++){ Combination[i][0] = 1; for (int j = 1; j <= 50; j++){ Combination[i][j] = Combination[i - 1][j - 1] + Combination[i - 1][j]; } } return 0; } | cs |
728x90
'Algorithm > 이론' 카테고리의 다른 글
[STL] vector 사용하기 (0) | 2016.04.04 |
---|---|
[STL] pair 사용하기 (1) | 2016.04.04 |
[그래프의 표현] 인접 리스트 (0) | 2016.04.01 |
[그래프의 표현] 인접 행렬 (0) | 2016.03.31 |
[소수 판별법]에라토스테네스의 체 (0) | 2016.03.24 |
댓글