[Algorithm] 동적 계획법(Dynamic Programming, DP)

큰 문제를 풀기위해 작은문제를 풀어 큰문제를 풀어가는 방법

기존 재귀함수를 이용하여 피보나치 수열을 구하기 위해서는 많은 연산이 중복된다.

이러한 중복을 제거 하기 위해서 메모이제이션(Memoization)이라는 테크닉을 사용한다. 계산된 값을 버리지 말고 저장한다는 뜻이다. 계산이 된 fib(2) 값을 저장해 놓고 있다가, 필요한 경우 계산없이 호출하게 된다.

 

이렇게 저장되는 배열을 캐시라고 한다. 배열 f를 캐싱용으로 하나 만들어 둔다. 이 배열 내부를 -1로 모두 초기화 시키고, 만약 -1이라면 결과값이 저장되어 있지 않으므로 계산을 실행한다.

* 기존 재귀함수 사용

• 재귀함수는 Top-Down 방식이다.

int fibo(int n) {
    if (n == 0) return 0;
    if (n == 1) return 1;
    return fibo(n - 1) + fibo(n - 2);
}

* Top-Down

• 재귀와 같은 방식으로 위(Top)에서 아래로 내려오는 방식이다.

• 함수 호출을 줄이기 위해, 메모이제이션을 사용한다.

• long long fib(long long n){
      if (n == 1 || n == 2)
          return 1;
      if (!memo[n])
          return memo[n];
      memo[n] = fib(n-1) + fib(n-2);
      return memo[n];
  }

* Bottom-Up

• for문을 이용해서 처음값부터 다음값을 계산해 나가는 방식이다.

• 가장 작은 문제들(Bottom)부터 차례차례 답을 구한다.

  long long fib(int n) {
      memo[0] = 0;
      memo[1] = 1;
      for (int i = 2; i <= n; i++) 
          memo[i] = memo[i - 1] + memo[i - 2];
      return memo[n];
  }

* 동적 계획법(DP) 기반의 알고리즘 동작 방식

1. 구하고자 하는 큰 문제를 작은 부분문제로 나눈다. => 동적 프로그래밍을 위해서는 점화식을 찾는 것이 매우 중요하다.
2. 가장 작은 부분 문제(종료 조건, 주로 0 또는 1일때)부터 푼 뒤 값을 저장한다. => 메모이제이션
3. 메모이제이션된 부분 문제들의 해를 이용하여 차례로 더 큰 상위 문제의 답을 구한다.
4. (3) 과정을 가장 큰 문제(구하고자 하는 큰 문제)에 도달할때까지 반복한다.

* DP를 적용할 수 있는 경우

• 작은 문제가 반복해서 발생하는 경우
• 같은 문제가 반복할 때마다 같은 출력을 발생시키는 경우 (메모이제이션)

* 메모이제이션

동적 프로그래밍에서는 같은 문제가 계속해서 반복되고, 이 문제들의 출력이 항상 같다.

따라서 한번 계산한 분할된 문제의 출력물(답)을 저장해 놓고, 이후 다시 같은 문제가 호출 되었을 때 사용하는 방법이다.

* 분할 정복과의 차이

분할 정복은 문제를 분할했을 때 겹치는 문제가 발생하지 않지만 DP는 겹치는 문제가 발생하기 때문에 메모이제이션이 필요하다.

 

참고한 곳: https://coding-all.tistory.com/2