🚀 다이나믹 프로그래밍

: 반복되는 문제가 있을 때, 그 문제는 단 한번만 연산하도록 하는 알고리즘. 즉 한번 푼 것을 다시 푸는 알고리즘 개선한다. DP는 대부분 최적 값을 구할 때 사용된다.


🤔 사용법

  1. 큰 문제를 작은 문제로 나눌 수 있다.
  2. 작은 문제해서 구한 정답을 그것을 포함하는 큰 문제에서도 적용할 수 있다.

메모이제이션

다이나믹 프로그래밍을 구현하는 방법 중 한 종류로, 한 번 구한 결과를 메모리 공간에 메모해두고 같은 식을 다시 호출하면 메모한 결과를 그대로 가져오는 기법을 말한다. 공간을 사용해 시간을 줄인다.


Top-down(메모이제이션)

큰 문제부터 시작해서 작은 문제로 분할해 가면서 푸는 것. 대부분 재귀함수로 구현된다.
ex) fibonacci(4)를 구하는 건 fibonacci(3)과 fibonacci(2)를 구하는 것으로 나눌 수 있고 …

int memo[100];

int fibonacci(int n)
{
    if (n <= 1) //0,1번째 피보나치 수
        return n;
    if (memo[n] != 0) //이미 계산이 되어있다면
        return memo[n];
    memo[n] = fibonacci(n - 1) + fibonacchi(n - 2); //작은 문제로 분할
}


Bottom-up

작은 문제부터 시작해서 작은 문제를 쌓아 큰 문제를 푸는 것. 가장 작은 문제부터 풀고, 점점 크기를 키워 전체를 푼다. Top-down과 달리 for문을 이용해서 다음 값을 계산해 나간다. 다이나믹 프로그래밍의 전형적인 형태이다.
ex) fibonacci(1)을 구하고 fibonacci(2)를 구하면 fibonacci(3)을 구할 수 있음

int f(int n)
{ //f(n)구하기

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

    return dp[n];
}


  • Top-down / Bottom-up 적용해서 푼 문제