38. 이항계수 구하기 알고리즘 (재귀 프로그래밍)

1. 개요

이항계수 구하기는 재귀 프로그래밍의 기초이다.

이항계수란 n개의 원소에서 r개의 원소를 뽑아내는 방법의 수를 나타낸다.

즉, nCr과 같이 수학에서 조합을 뜻한다.

이항계수 프로그래밍의 해법은

nCr = n-1Cr-1 + n-1Cr

의 공식으로 이루어진다.

무슨 의미냐면

n개의 원소 중 r개의 원소를 뽑아내는 경우의 수는

맨 마지막 원소 n을 제외한 

n-1개의 원소 중 r-1개를 뽑아내는 경우의 수

+

n-1개의 원소 중 r개를 뽑아내는 경우의 수

의 합이다.

즉, 이미 n번째 원소를 선택했다고 가정하고 나머지 원소 중에서 r-1개를 뽑는 것과

n번째 원소를 제외한 나머지 중에서 r개의 원소를 뽑는 경우의 합이다.

2. 문제

이항계수의 재귀 프로그래밍을 작성하시오.

(일반적인 방법과 메모이제이션을 이용한 재귀적 방법으로 각 방법의 수행시간을 비교하시오.)

3. 코드

3-1) 재귀적 방법

3-2) 메모이제이션을 활용한 재귀적 방법

3-3) 출력

4. 정리

이항계수 문제는 알고리즘 대회 풀이에 들어가는 아주 기본적인 풀이다.

경우의 수를 구하는 대표적인 문제 중 하나로 재귀 점화식의 기본이 된다.

그러니 잘 알아두자.