[Algorithm] Dynamic Programming

🤔 동적 프로그래밍(Dynamic Programming)

알고리즘을 짤 때, 보통 분할 정복 기법(Divide-Conquer)을 사용하는 경우가 많다.

분할 정복 기법은 큰 문제를 작은 여러 개의 문제로 나눠 푸는 기법인데, 작은 문제들을 풀다 보면 같은 문제들을 반복해서 푸는 경우가 생기게 된다.

동적 프로그래밍(Dynamic Programming)은 이런 문제들을 매번 다시 계산하지 않고, 테이블을 사용해 계산한 값을 저장해두었다가 재사용하는 기법이다. (쉽게 생각하면, 점화식을 생각하면 된다.)

분할 정복 기법(Divide-Conquer)은 한 문제를 겹치지 않는 부분 문제들로 분할하여 해당 문제들을 재귀적으로 해결한 후, 각각의 결과를 다시 결합하여 원래의 문제를 해결한다.

동적 프로그래밍(Dynamic Programming)은 부분 문제가 서로 중복될 때, 그 해를 테이블에 저장해 두고 각 부분 문제를 풀 때마다 저장해둔 값을 활용한다.

📖 대표 문제

동적 프로그래밍에는 대표적인 세 가지 문제가 있다. (이건 나중에 기회가 되면 정리)

1. 최장 공통 부분 수열 문제 (LCS)

2. 0/1 배낭 문제 (0-1 Knapsack)

3. 막대 자르기 문제 (Rod Cut)

👏🏻 메모이제이션(Memoization)

이미 계산한 내용을 또다시 계산할 때 필요 없는 연산이 생길 수 있다.

피보나치수열을 예로 들어보자면,

int fibo(int n)
{
    if (n == 0)
        return 0;
    if (n == 1)
        return 1;

    return fibo(n - 1) + fibo(n - 2);
}

위와 같이 피보나치 수열을 정의할 수 있다.
만약 n이 5라면 f(5)는?

fibo(1)
fibo(2)
fibo(3) = fibo(1) + fibo(2)
fibo(4) = fibo(2) + (fibo(1) + fibo(2))
fibo(5) = (fibo(1) + fibo(2)) + (fibo(2) + (fibo(1) + fibo(2)) 이므로,

위와 같이 전에 계산한 값을 매번 다시 계산해야 한다.
이런 과정을 막기 위한 것이 Dynamic Programming의 역할이다.

 

위의 fibo 함수를 DP를 활용해서 재정의해보자.

int dp[50];
int fibo(int n)
{
    if (n == 0)
        return 0;
  if (n == 1)
    return 1;
  if (dp[n] != -1)
    return dp[n];

  return dp[n] = fibo(n - 1) + fibo(n - 2);
}

int main()
{
  memset(dp, -1, sizeof(dp));
  cout << "fibo(40) = " << fibo(40) << endl;
}

memset 함수는 dp라는 배열을 -1이라는 값으로 전부 초기화시키는 역할을 한다.

처음 계산하는 값이라면 dp[n]에는 -1이라는 값이 들어있게 된다.

다음에 같은 값을 계산할 때는, -1이라는 값이 아닌 0이나 1 이상의 값이 들어가게 된다.

즉, dp[n] != -1이라는 얘기는 앞에서 이미 계산을 했다는 뜻이 된다.

dp[n]을 반환하면 fibo(n - 1)과 fibo(n - 2)를 더 이상 호출하지 않아 시간을 절약할 수 있게 되고, 이것을 메모이제이션(memoization)이라고 한다.