[알고리즘]동적 계획(Dynamic Programming)_이항계수

💡동적 계획(Dynamic Programming)

 - 작은 문제부터 해결하여 그 결과를 큰 문제를 푸는데 사용하는 bottom-top 방식의 알고리즘

   (분할정복과 반대)

 

 

💡이항계수

 

✔️ 재귀호출을 사용한 하향식 접근 방식

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

- 항의 개수 = 2(n, k) - 1 

-  bin(n-1,k) 값 => bin(n-2,k-1), bin(n-2, k) 필요 (재귀호출에 의해서)

   bin(n-1,k-1)값 => bin(n-2,k-1), bin(n-2,k-2)필요 

- 위에서 아래로 , 큰문제를 작은문제로 분할하여 계산하는데 위 예시처럼 분할되어 독립적으로 수행되는 특성 때문에

  같은 계산을 여러번 반복하는 문제 발생

 

✔️ 동적계획 방식

int bin(int n, int k){
	int i,j;
	int B[MAX][MAX]; // 배열 B 생성한다.

	for (i=0;i<=n,i++){
		for (j=0;j<=min(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];
}

- B[0][0] 부터 시작하여 결국 마지막 B[n][k]에 구하고자 하는 값이 저장된다.

- 배열에 값들이 다 저장되어 있기 때문에 반복문이 반복되면서 그저 미리 저장되어 있던 배열의 값을 사용하면 된다.

- 시간복잡도 = o(n^2)