DP(Dynamic Programming), 동적 프로그래밍

11 Jun 2021

DP(Dynamic Programming), 동적 프로그래밍

DP, 동적 프로그래밍은 큰 문제의 해답에 작은 문제의 해답이 포함되어 있고 이를 재귀호출 알고리즘으로 구현하면 지나친 중복이 발생하는 경우에 이 재귀적 중복을 해결하는 방법을 말한다.

예시로 피보나치수 구하기에 동적 프로그래밍의 개념을 이해할 수 있는 핵심이 들어있는데 한번 알아보자.

피보나치 수는 다음과 같이 정의된다.

f(n) = f(n-1) + f(n-2)
f(1) = f(2) = 1

=> n의 피보나치 수는 n-1의 피보나치 수와 n-2의 피보나치수를 포함하고 있다.
=> 이처럼 큰 문제의 해답에 그 보다 작은 문제의 해답이 포함되어 있으면 최적 부분 구조(Optimal Substructure) 를 가졌다고 한다. DP를 하려면 문제가 일단 이 성질을 가져야 한다.(첫번째 조건)

피보나치 문제의 경우 fib(n)은 fib(n-1)과 f(n-2)을 재귀적으로 호출한다. 이를 c언어로 작성해보자.

#include <stdio.h>
int count;
int fibonacci(int n){
  
  count++;
  if(n == 1 || n == 2){

      return 1;
  } else {
     
      return fibonacci(n-1) + fibonacci(n-2);

  }

}

int main(){
    int result = fibonacci(10);
    printf("result: %d \n", result);
    printf("count: %d \n", count);
    return 0;
}
// 실행 결과
// result: 55 
// count: 109

=> 최적 부분 구조는 문제의 해답(f(n))을 구하기 위해 더 작은 문제(f(n-1)+f(n-2))의 해답을 이용하므로 재귀로 푸는 것이 자연스럽다. 하지만 재귀적 알고리즘이 간명(= 간단명료)하지만 엄청난 비효율을 초래할 수 있는 경우가 있는데 이 피보나치 문제를 재귀로 푸는 경우가 그렇다. 이 피보나치수는 작은 문제들을 중복 호출하기 때문에 지수함수에 비례하는 시간이 든다. 위의 예제만 보더라도 fibonacci(10)을 구하기 위해 함수를 109번이나 호출하였다.
=>예시를 한번 더 들면 fibonacci(5)을 구하려면 f(5) = f(4) + f(3), f(4) = f(3) + f(2), f(3) = f(2) + f(1), f(3) = f(2)+ f(1) 와 같이 진하게 표시된것만 호출된 것인데 총 9번 호출해야 하는 비효율이 발생한다.
=> 이처럼 중복호출로 인한 엄청난 비효율이 발생하는 재귀의 경우는 동적 프로그래밍을 사용하기 위한 두 번째 조건이다.

정리 : 다음의 두 성질을 갖고 있는 문제에 대해 적절한 저장 방법으로 중복 호출의 비효율을 제거한 것을 동적 프로그래밍(DP)이라 한다.

최적 부분구조를 이룬다. ( 큰 문제의 해답에 작은 문제의 해답이 포함될 때 ex) f(n) = f(n-1) + f(n-2) )
재귀적으로 구현했을 때 중복 호출로 심각한 비효율이 발생한다.

DP 방법 1 : for문을 이용한 DP

#include <stdio.h>



int count;
int fibonacci(int n){

  int arr[n];

  int i;
  for(i = 1; i<=n; i++){
      

    if(i == 1 || i == 2){
     
        arr[i] = 1;
    
    } else {
          
        arr[i] = arr[i-1] + arr[i-1];
    }
      
    count++;
  }

  return arr[n];

}

int main(){

    int result = fibonacci(10);
    printf("result: %d \n", result);
    printf("count: %d \n", count);

    return 0;
}
// 실행 결과
// result: 55 
// count: 10 

for 문를 순환하는 것이 수행 시간을 좌우하므로 선형시간 O(n) 알고리즘이다. for문을 한번 돌때 마다 앞서 구해 놓은 피보나치수 두개를 배열에서 가져다 더하기만 하면 된다.
이렇게 선형시간에 해결할 수 있는 것이 재귀적으로 구현하니 지수함수 시간이 들게 된 것이다. -> 엄청난 비효율이다. DP를 사용하도록 하자.

DP 방법 2 : 메모하기(Memoization)를 이용한 DP

재귀적 비효율을 해결하기 위해 재귀적 구현에 다음과 같은 장치를 하여 비효율을 제거할 수 있다.

#include <stdio.h>
#define NUM 10

int arr[NUM];
int count;
int fibonacci_memo(int n){

  if(arr[n] != 0){
    return arr[n];
  } else {
    count++;
    if(n == 1 || n == 2){
      arr[n] = 1;
    } else{
      arr[n] = fibonacci_memo(n-1) + fibonacci_memo(n-2); 
    }
    return arr[n];

  }

}
int main(){

  int result = fibonacci_memo(10);
  printf("result: %d \n", result);
  printf("count: %d \n", count);

  return 0;
}
// 실행 결과 
// result: 55 
// count: 10

=> 전역변수인 배열 arr[NUM]은 모든 원소가 0으로 초기화된다. 따라서 fibonacci_memo(i)가 처음 호출되면 f[i]에 저장하고, 두 번 호출 된 경우에는 이미 f[i]에 0이 아닌 수가 저장되었으므로 재귀적 호출을 하지않고 저장된 f[i]를 리턴한다. 따라서 이러한

방식대로 알고리즘을 수행하면 재귀적 호출이더라도 f(10)을 구하는데 재귀적 호출을

10번밖에 하지 않았고 이는 보통의 재귀 방식으로 f(10) 구하는데 재귀적 호출을 10

번 하는 것보다 훨씬 효율적이라 할 수 있다.
=> 중복된 재귀호출을 피하는 이런 방법의 동적 프로그래밍에는 특별히 메모하기(Memonization)라는 이름이 붙어 있다.(이 단어를 Memorization과 혼동하는데 Memonization이다.) 메모를 한다는 의미로 memo에서 만들어진 단어다.

위의 메모하기 방식을 위에서 아래로 내려가며 해를 구하므로 탑다운(Top-Down) 방식이라고 한다.
for문을 이용한 DP는 아래에서 위로 저장해가면서 해를 구하므로 바텀업(Bottom-Up) 방식이라고 한다.

=> 바텀업 방식이 탑 다운 보다 많이 사용되지만 두 DP 방식 모두 작은 해를 테이블에 저장한다는 점에서 동일하다.

사실 병합정렬, 퀵정렬 등도 큰 문제의 답이 작은 문제의 답을 포함하고 있는 최적 부분 구조이다. 거의 모든 재귀 알고리즘이 최적 부분구조를 구현한다고 할 수 있다. 하지만 이들의 재귀적 구현에는 중복이 발생하지 않는다. 계승도 최적 부분 구조를 갖지만 중복이 발생하지 않는다. 따라서 재귀 중에서도 중복이 발생하는 것과 중복이 발생하지 않는 것을 잘 분별해 DP를 사용하도록 하자.

이 글은 문병로 저자의 ‘쉽게 배우는 알고리즘 - 관계 중심의 사고법’ 의 내용을 읽고 주관적으로 정리하고 요약한 것입니다.