[Algorithm] Dynamic Programming(DP, 다이나믹프로그래밍)

Dyanamic Programming

Dynamic programming은 기본적으로는 최적화 알고리즘(optimization algorithm)이다. 즉, 어떠한 문제도 DP를 사용하지 않아도 문제를 풀 수 있다. 하지만, DP를 사용하면 더 좋은 방법으로 문제를 풀어나갈 수 있다.

방법론

• Top-down : 문제를 더 작은 하위 문제로 나누어서 해결해 나가는 방식이다. 이 때, 메모를 하면서나아가는 방식인 Memoizaion을 활용한다.

  • Memoization : 메모는 하위 문제를 계산하여 미리 기록해 두는 것으로, 여러번 계산할 필요없이 이전에 값을 가져다 쓸 수 있다.
    • 복잡한 문제를 풀 때, Tabulation보다 코딩하기 쉽다.
    • 모든 경우의 sub problem을 고려할 필요가 없다.
    • 재귀 호출이 많을 경우, stack overflow나 메모리 문제가 발생할 수 있다.
    • Tabulation 보다 느릴 수 있다.
    • Memo를 할 때는 함수 결과로 절대로 나올 수 없는 수로 초기화 해야한다.
  • ex. from n(end) to 1(start)

• Bottom-up : 문제를 시작(하위)부터 끝(상위)까지 차근히 계산하면서 이를 다음에 이용해 풀어가는 방식이다.

  • Tabulation : 테이블에 값을 처음부터 채워나가는 것과 같다.
    • 복잡한 문제를 특정한 순서로 풀 때, Memoization 보다 코딩하기 어렵다.
    • Tabulation을 할 때는 함수 결과로 절대로 나올 수 없는 수로 초기화 해야한다.

• ex. from 1(start) to n(end)

Example

#include <iostream>

int recursive(int x)
{
    if (x == 0)
        return 0;
    if (x == 1 || x == 2)
        return 1;

    return recursive(x - 1) + recursive(x - 2);
}

int td[32] = {0, };

int dp_topDown(int x)
{
    if (x == 0)
        return 0;
    if (x == 1 || x == 2)
        return 1;
    if (td[x] != 0)
        return td[x];

    return td[x] = dp_topDown(x - 1) + dp_topDown(x - 2);
}

int bu[32] = {0, };

int dp_bottomUp(int n)
{
    bu[1] = 1;

    for (int i = 2; i <= n; i++)
    {
        bu[i] = bu[i - 1] + bu[i - 2];
    }
    return bu[n];
}

int main()
{
    int n = 10;

    std::cout << "Recursive" << recursive(n) << std::endl;
    std::cout << "TopDown " << dp_topDown(n) << std::endl;
    std::cout << "BottomUp " << dp_bottomUp(n) << std::endl;

    return 0;
}

Reference
[1] https://www.codesdope.com/course/algorithms-dynamic-programming/