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

< 이항계수 > 

 

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

 

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

 

 

 

 

 

< 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];
}

 

 

 

 

이항계수를 구하는 경우, 동적 프로그래밍은 분할 정복과는 달리 중복을 만들지 않고 계산함으로써

더 효율적인 시간복잡도를 갖는다.