[알고리즘]다이나믹 프로그래밍(Dynamic Programming, DP)

 1. Dynamic Programming(동적 계획법)이란?

 

 하나의 문제를 여러 하위 문제로 나누어 풀고, 그것들을 결합해서 최종 목적에 도달하는 방식의 알고리즘입니다. 

 

 

 2. DP의 원리, Memoization

 

 동적 계획법의 원리는 처음 진행된 연산은 기록해 두고 이미 진행했던 연산이라면 기록한 값을 가져와 중복 계산을 줄이는 것입니다. 이것을 메모이제이션(Memoization)이라고 합니다. 

 

 

3. DP의 조건

1. 작은 문제가 반복될 경우
2. 같은 문제에 대한 결과가 항상 같을 경우 

 

 

4. DP 사용 예시: 피보나치 수열

 

 DP가 사용되는 예시로 피보나치 수열을 들겠습니다. 

 

(1) 재귀호출을 이용한 풀이 

//재귀호출을 통한 피보나치 수열 구하기 
int fibonacci(int n){
	if(n <= 2)
    		return 1;
        
    return fibonacci(n-1)+fibonacci(n-2);
}

 

 피보나치 수열을 구하는 문제는 위와 같이 재귀 호출을 통해 해결할 수 있습니다. 하지만 이미 연산한 값을 다시 연산하게 된다는 단점이 있습니다. 이러한 문제점을 해결하기 위해 DP를 사용할 수 있습니다.  

(2) DP를 이용한 풀이

 

 DP를 이용하여 처음 연산하는 값은 기록하고 이미 진행된 연산은 기록한 값을 가져오도록 합니다. 

int dp[100] = {0, };  //연산의 결과 기록할 배열

int fibonacci(int n)
{
	if(n <= 2)
    		return 1;
            
    	if(dp[n] == 0)
    		dp[n] = fibonacci(n-1) + fibonacci(n-2);
            
   	return dp[n];
}

 

 

5. DP 접근 방법

 

(1) Bottom-up

 

 Bottom-up은 아래에서 위로 접근하는 방법으로, 작은 문제부터 문제를 풀어나가며 점차 큰 문제를 풀어가는 방법입니다. 

 

 보통 for문을 통해 접근합니다. 

int dp[101] = {0, };

dp[1] = 1;
dp[2] = 1;

int fibonacci(int n)
{
	for(int i=3; i<=n; i++) //bottom-up, 아래에서 위로 
    {
    	dp[i] = dp[i-1] + dp[i-2];
    }
    return dp[n];
}

 

 

(2) Top-down

 

 Top-down은 위에서 아래로 접근하는 방법으로, 큰 문제를 작은 문제로 분할하며 푸는 방법입니다. 

 

 보통 재귀호출을 통해 접근합니다. 

 

int dp[100] = {0, };  

int fibonacci(int n)  //top-down, 위에서 아래로
{
	if(n <= 2)
    		return 1;
            
    	if(dp[n] == 0)
    		dp[n] = fibonacci(n-1) + fibonacci(n-2);
            
   	return dp[n];
}

 

 

6. 장단점

 

•  장점: 그리디 알고리즘은 항상 최적의 해를 구할 수 없는 반면, DP는 모든 방법을 일일이 검토하기 때문에 항상 최적의 해를 구할 수 있습니다. 
•  단점: 그리디 알고리즘에 비해 시간이 오래 걸립니다.