티스토리 뷰

※ 수학 nCr이 궁금하셔서 들어오신 분들은 가장 아래부터 보시면 됩니다.


안녕하세요? 코딩충입니다.

오늘의 포스팅은 [코딩++ 수학] 카테고리의 첫 포스팅입니다.

"조합의 계산(이항계수, nCr)'은 DP포스팅에서 얘기를 한 적이 있는데 신경써서 읽어보시면 알 수 있습니다.

아래 스샷에서 하일라이트 한 부분이 제가 예고한 부분인데 뭐 중요한 것은 아닙니다. 그냥 조합을 계산하는 재귀 문제가 자주 나와서 DP에서 얘기를 꺼낸 것입니다.

우선 조합(nCr)이 뭐냐하면 (조합, 이항계수라고 부르기도 합니다) 서로 다른 n개 중에서 중복하지 않고 r개를 뽑는 경우의 수 인데 수학 블로그가 아니므로 자세한 부분은 위키피디아를 참고하시고 여기서는 프로그램 위주로 얘기하겠습니다.

프로그램은 아래에 첨부했습니다.

코드는 제가 깨끗하게 하려고 노력을 많이 한 코드(소스)고요, 주석도 많이 달았습니다.

조합의 점화식은 nCr = (n - 1)Cr + (n - 1)C(r - 1) 입니다.

(n - 1)Cr 은 특정한 한 사람을 뽑지 않는 경우의 수이고요, 

(n - 1)C(r - 1)은 특정한 한 사람을 뽑는 경우의 수입니다.

특정한 한 사람을 뽑거나 뽑지 않거나 둘 중에 하나이기 때문에 합치면 전체가 되는 것 입니다.

아래 코드에서 조금만 바꾸면 백준에 있는 여러가지 이항계수(조합) 문제들을 푸실 수 있을 것 입니다.

물론 조합을 저렇게 점화식으로 계산하지 않고 팩토리얼을 이용해 계산을 해야 되는 문제들도 있습니다만 보통 점화식을 이용해 구하는 경우가 다반사입니다. 실제로 수학에서 nCr을 구할떄는 팩토리얼을 이용해서 구합니다. nCr = n! / (r! * (n - r)!) 을 이용해서 구합니다.


조합(nCr) 계산 프로그램.exe.exe

main.cpp


※ 첨부된 코드는 재귀 DP의 전형적인 형태로

1. 종료 조건(가장 작은 부분문제)

2. 중복 계산 방지

3. 메모이제이션 및 점화식



----------------------------------------------------------------------------------------------------------------------------------------------------


※ nCr에 대한 추가 정보

수학 조합 C로 유입이 되는 경우가 많아서 nCr에 대해서 더 설명드리겠습니다.

nCr은 서로 다른 n개중에서 r개를 뽑기만 하는 경우입니다.

그에 반해서 nPr은 서로 다른 n개중에서 r개를 뽑아서 나열하는 경우의 수입니다.

따라서 nPr은 nCr에 r개를 나열하는 경우를 곱한 경우의 수이겠죠?

따라서 nPr = nCr * r!이 됩니다.(by 곱의 법칙)

nPr을 구합시다.

우선 r개의 자리를 생각해봅시다.

그럼 첫번째 자리에는 1~n까지 n개의 수가 들어올수 있죠.

따라서 n가지이고

두번째 자리에는 1~n중에서 첫번째 자리의 숫자를 제외한 n - 1가지가 가능하죠.

이렇게 해서 r번째 자리에는 1~n중 r - 1개의 숫자를 제외한 n - r + 1가지가 가능하죠.

따라서 nPr = n * (n - 1) * (n - 2) * ....... * (n - r + 1)이 되고 다르게 표현하면

nPr = n!/(n - r)!이 됩니다.

따라서 nCr은 n!/(n - r)! * r! 이 됩니다.


nCr = n - 1Cr + n - 1Cr - 1 이 되는 이유는 위의 본문에서

특정 사람을 뽑는 경우와 뽑지 않는 경우를 합한 경우가 되기 때문입니다.

공지사항
최근에 올라온 글
최근에 달린 댓글
Total
Today
Yesterday
링크
«   2024/03   »
1 2
3 4 5 6 7 8 9
10 11 12 13 14 15 16
17 18 19 20 21 22 23
24 25 26 27 28 29 30
31
글 보관함