[알고리즘] 다이나믹 프로그래밍 - Dynamic Programming

다이나믹 프로그래밍(Dynamic Programming)

    => 큰 문제를 작은 문제로 나누서 푸는 알고리즘

 

• 다이나믹 프로그래밍에서 각 문제는 한 번만 풀어야 한다. 
• Optimal Substructure 를 만족하기 때문에, 같은 문제는 구할 때마다 정답이 같다.   
• 따라서, 정답을 한 번 구했으면 어딘가에 메모해놓는다.
• 이런 메모하는 것을 코드의 구현에서는 배열에 저장하는 것으로 할 수 있다. 
• 메모를 한다고 해서 영어로 Memoization 이라고 한다. 

 

 

 

두 가지 속성을 만족해야 다이나믹 프로그래밍으로 문제를 풀 수 있다.

 

1. Overlapping Subproblem

     (문제를 작은 문제로 나눠서 푸는데, 이때 문제들끼리 겹쳐야한다.)

• 큰 문제와 작은 문제를 같은 방법으로 풀 수 있다.
• 문제를 작은 문제로 쪼갤 수 있다. 

예시)  피보나치 수

F0 = 1, F1= 1, Fn = Fn-1 + Fn-2 (n>=2)

문제: N번째 피보나치 수를 구하는 문제

작은문제: N-1번째 피보나치 수를 구하는 문제, N-2번째 피보나치 수를 구하는 문제

 

문제: N-1번째 피보나치 수를 구하는 문제

작은문제: N-2번째 피보나치 수를 구하는 문제, N-3번째 피보나치 수를 구하는 문제

 

=> Overlapping Subproblem 을 만족한다면, 문제의 정답을 작은 문제의 정답을 합하는 것으로 구할 수 있다. 

 

 

 

2. Optimal Substructure

• 문제의 정답을 작은 문제의 정답에서 구할 수 있다.

예시)

 

10 번째 피보나치 수를 구하면서 구한 4번째 피보나치 수

9 번째 피보나치 수를 구하면서 구한 4번째 피보나치 수

...

5번째 피보나치 수를 구하면서 구한 4번째 피보나치 수

4번째 피보나치 수를 구하면서 구한 4번째 피보나치 수

 

4번째 피보나치 수는 항상 같다. 

 

=> Overlapping Subproblem 을 만족한다면, 문제의 크기에 상관없이 어떤 한 문제의 정답은 항상 일정하다. 

 

 

피보나치 수의 구현

int fibonacci(int n){
    if(n<=1){
        return n;
    } else{
        return fibonacci(n-1)+fibonacci(n-2);
    }
}

위의 방식은 겹치는 호출이 생긴다. 

int memo[100]; //n번째 피보나치 수를 저장하기 위한 배열
int fibonacci(int n){
      if(n<=1){
            return n;
      } else {
      		if(memo[n] > 0){ //이전에 구한 값이면 
            		return memo[n];
            }
            memo[n] = fibonacci(n-1) + fibonacci(n-2);
            return memo[n];
      }
}
    

 

 

 

 

 

다이나믹 문제를 푸는 2가지 방식이 있다. 

 

1. Top-down

• 문제를 작은 문제로 나눈다.
• 작은 문제를 푼다. 
• 작은 문제를 풀었으니, 이제 문제를 푼다. 
• 시간복잡도 = 채워야 하는 칸의 수 X 1칸을 채울 때의 복잡도 (피보나치 수의 시간 복잡도 = n X O(1) = O(n) )

    => 보통 재귀 호출을 이용해서 문제를 푼다. (예: 위의 피보나치 수 구현 방식)

int d[100]; //n번째 피보나치 수를 저장하기 위한 배열
int fibonacci(int n){
      if(n<=1){
            return n;
      } else {
      		if(d[n] > 0){ //이전에 구한 값이면 
            		return d[n];
            }
            d[n] = fibonacci(n-1) + fibonacci(n-2);
            return d[n];
      }
}

 

 

2. Bottm-up

• 문제의 크기가 작은 문제부터 차례대로 푼다. 
• 문제의 크기를 조금씩 크게 만들면서 문제를 점점 푼다.
• 작은 문제를 풀면서 왔기 때문에, 큰 문제는 항상 풀 수 있다. 
• 그러다보면, 언젠간 풀어야 하는 문제를 풀 수 있다. 

    => 보통 for문을 이용해서 문제를 푼다. 

int d[100];
int fibonacci(int n){
      d[0] = 0;
      d[1] = 1;
      for(int i=2; i<=n; i++)	{
            d[i] = d[i-1] + d[i-2];
      }
      return d[n];
}

 

 

 

 

 

문제 풀이 전략

• 문제에서 구하려고 하는 답을 문장으로 나타낸다. 
• 문제를 많이 풀어보면서 감을 잡는 것이 중요하다.