티스토리 뷰
※ 수학 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)!) 을 이용해서 구합니다.
※ 첨부된 코드는 재귀 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 이 되는 이유는 위의 본문에서
특정 사람을 뽑는 경우와 뽑지 않는 경우를 합한 경우가 되기 때문입니다.