[알고리즘] Dynamic Programming - Binomial Coefficient

학교에서 들은 알고리즘 분석 강의 내용을 복습하면서 작성한 글입니다.
April 8, 2024 6:07 PM

 

divide-and-conquer

• top-down의 recursive approach
• 서로 관련되지 않은 더 작은 요소들로 나눠준다

Dynamic Programming(DP)

• bottom-up으로 작은 요소 먼저 해결 후 → 해당 결과를 저장해놓았다가 → 필요 시 가져다 쓴다 (다시 해결할 필요없이, 기존에 저장해놓은것 이용하면 됨)
• 나눠진 요소들이 서로 연관있는 것 → 중복이라 비효율적 → dp 사용이 더 나음

💡 과정
recursive property 찾아내기
아래 → 위로 계산 </aside>

 

---

Binomial Coefficient

Dynamic Programming 사용

- Recursive Property

 

B[i][j] = B[i-1][j-1]+B[i-1][j] (0<j<i)
            = 1 (j=0 or i=j)

int bin2(int n, int k)
{
	index i, j;
	int B[0...n][0...k];
	for (i=0;i<=n,i++)
		for (j=0;j<=minimum(i,k);j++)
		 if (j==0|| j=i)
			 B[i][j]=1;
			else
				B[i][j] = B[i-1][j-1] + B[i-1][j];
	return B[n][k]
{

 

i	0	1	2	...	k	k+1	...	n
num of passes	1	2	3	…	k+1	k+1	…	k+1

 

1+2+3+..+k+(n-k+1)(k+1)

= k(k+1)/2 + (n-k+1)(k+1)

= (k+1)(2n-k+2) / 2 → θ(nk)

 

 

Divide-and-Conquer 사용도 가능

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

-> 하지만 시간 복잡도 측면에서 비효율적이다.