[알고리즘] CHAP 2. Dynamic Programming (동적 프로그래밍)

이번 챕터에서는 Dynamic Programming에 대해 작성할 예정이다. 목차는 다음과 같다.

 

• 동적 프로그래밍 ?
• Dynamic Programming vs Divide-and-conquer (feat. 피보나치)

 

1. Dynamic Programming이란?

 

진짜 동적으로 프로그래밍을 하는게 아니고, 큰 문제를 작은문제로 나누어 푸는 방법을 말한다. Divide-and-Conquer처럼 문제를 하나 이상의 작은 인스턴스로 분할해 접근하지만, Divide-and-Conquer와 달리 Bottom-up approach를 사용한다. Bottom-up approach는 작은 인스턴트들을 먼저 해결해가는 접근법을 의미한다.

 

Bottom-up approach는 다음과 같은 순으로 진행한다.

• 재귀적 속성 설정
• 작은 인스턴스 먼저 해결 (Bottom up)

DP(Dynamic Programming)은 다음과 같은 순으로 실행된다.

• 작은 첫 인스턴스 해결
• 결과를 저장
• 저장된 결과를 재사용

결과를 저장해두고, 이를 재사용 하는 특징이 있기 때문에 작은 문제가 반복이 일어나고, 그의 답이 같은 경우에 동적 프로그래밍을 사용한다. 

 

---

2. DAC vs DP (by using Binomial Coefficient)

Binomial Coefficient를 이용해 DP와 DAC의 차이를 보이려 한다. 

 1. Binomial Coefficient using DAC

원래는 n과 k를 세로로 쓰지만 작성의 편의상 nCk = [n  k]  로 작성할 예정이다. ( 0 <= k <= n )

[n  k] = n! / (k! * (n - k)!) 로 쓸 수 있다. 고등학교때 4C3 = 3C2 + 3C3 을 배운적이 있는데, 이를 이용하면 다음과 같은 식을 도출할 수 있다.

 

[n  k] = if 0 < k < n, [n-1   k-1] + [n-1   k]

           if  k = 0 or k = n,   1

 

# Code

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

 

DAC는 재귀를 사용하므로 위와 같이 코드를 작성하였다.

 

# Time Complexity

연산개수를 알아보면 다음과 같이 작성할 수 있다.

 

T(n, k) = 2 [n  k] - 1

 

증명은 아래와 같이 할 수 있다.

이는 매우 비효율적인 방법이다.

 

---

2. Binomial Coefficient using DP

같은 문제를 DP를 사용해 해결하려고 한다. Bottom-up으로 접근해보자.

 

재귀적 속성 설정

B[ i ][ j ] = if  0 < j < i, B[i -1][j -1] + B[i -1][ j ]

                if  j = 0 or j = i, 1

 

Bottom-up으로 인스턴스 해결 -> 결과를 저장해둬야함!!

2차원 배열 안에 해당 값을 저장해둔다.

# Code

void bin2(int n , int k) {
	index i,j;
    int B[0..n][0..k];
    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];
        }
    }
}

 

# Time Complexity

연산 개수는 다음과 같이 계산할 수 있다.

 

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

 

Binomial Coefficient 문제를 풀 땐 DP를 이용하는게 DAC를 이용한 것보다 훨씬 효율이 좋다는 것을 알 수 있다!

 

---

이렇게 동적 프로그래밍에 대해 간단히 알아보았다! 다음 챕터에서는 그래프이론에 대해 설명할 예정이다 😎