동적 프로그래밍(Dynamic Programming)

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

최적 부분 구조

큰 문제에 해답에 작은 문제의 해답이 포함되어 있는 것

메모이제이션(Memoization)

동적 프로그래밍에서는 작은 문제의 해답을 반복적으로 구하는 비효율을 방지하기 위해서 작은 문제의 해답을 적절한 저장 방법으로 처리해서 해결한다.

Top-Down과 Bottom-Up

동적 프로그래밍을 해결하는 방식에 대해 정리하는 문단
Top-Down 방식은 점화식을 이해하기 쉽다는 장점
Bottom-Up 방식은 함수를 재귀호출하지 않아 시간과 메모리 사용량을 줄일 수 있는 장점이 있다.

Top-Down

가장 큰 문제를 방문 후 작은 문제들을 호출하며 답을 찾는 방식

int fibonacci(int n)
{
    if (n == 0) return 0;
    if (n == 1) return 1;
 
    if (dp[n] != -1) return dp[n];
 
    dp[n] = fibonacci(n - 1) + fibonacci(n - 2);
    return dp[n];
}

Bottom-Up

가장 작은 문제들부터 답을 구해가며 전체 문제의 답을 찾는 방식

int fibonacci(int n)
{
    dp[0] = 0, dp[1] = 1;
    for (int i = 2; i <= n; i++)
        dp[i] = dp[i - 1] + dp[i - 2];
}