[C++] 조합(Combination) 구하기

nCk 를 구현해보자.

수학시간에 배웠던 것처럼 평범하게 생각해보면

n!/(n-k)!k!

그러나 이걸 코드로 그대로 구현하는데는 큰 위험이 따른다.

n이 조금만 커져도 n!이 int는 물론 long의 한계도 가볍게 뛰어넘는 숫자로 뛰어버린다.

다시한번 수학시간의 기억을 잘 끄집어 내보자.

nCk = n-1Ck-1 + n-1Ck

이 식이 기억나는가?

이 식을 토대로 Recursion을 적용한 함수를 구현 해보자.

그러나 이 식도 문제가 있다.

Recursion 식이 두개나 들어가면서 수행시간이 2의 제곱 꼴로 비대해진다.

해결책은 바로 Dynamic Programming을 이용하는 것!

참조 - http://karnies.tistory.com/33