DP(동적계획법)을 이용한 이항계수 (Binomial Coefficient)

이항계수는 다음과 같이 표현되며

 

다음과 같은 성질을 따른다. 

 

< Divide and Conquer를 이용한 이항계수 구하기 >

int binomial(int n, int k) {
	if (k == 0 || k == n) {
		return 1;
	}
	return binomial(n - 1, k) + binomial(n - 1, k - 1);
}

이렇게 간단하게 구현 가능하지만, 효율적이지는 않다. 알고리즘을 재귀호출하면서 이미 했던 계산을 반복해서 수행하기 때문이다

하지만 동적프로그래밍을 이용하면 중복되는 부분을 커버하여 효율적인 알고리즘을 만들 수 있다.

 

 

< Dynamic programming을 이용한 이항계수 구하기 >

 

Divide and conquer가 top-down 방식이였다면 dynamic programming을 이용하며 bottom-up 방식으로 구성할 수 있다.

int binomial2(int n, int k) {
	int dp[100][100] = { 0, };

	for (int i = 0; i <= n; i++)
		for (int j = 0; j <= min(k, i);j++)
			if (i == j || j == 0)
				dp[i][j] = 1;
			else
				dp[i][j] = dp[i - 1][j] + dp[i - 1][j - 1];

	
	return dp[n][k];
}

 

이항계수를 구하는 경우, 동적 프로그래밍은 분할 정복과는 달리 중복을 만들지 않고 계산함으로써 더 효율적인 시간복잡도를 갖는다.

 

 

알고리즘: Dynamic programming을 이용한 이항계수(Binomial Coefficient) (feat.c++) :: Memo Memo (tistory.com)