YEAHx4YEAHx4

Dynamic Programming (dp)

다이나믹 프로그래밍

YEAHx4

YEAHx4

2025-04-22
11 mins

Dynamic Programming (dp)

dp는 굉장히 널리 사용되는 기법으로 정말 다양한 난이도의 문제에서 사용됩니다. 배열을 기반으로 과거의 어떤 상태를 미리 계산해두고 그 값을 계속 재활용해 효율적인 작동을 하도록 만드는 것이 dp입니다. 다양하게 사용되는 만큼 형태도 다양하고 다른 알고리즘과 함께 사용되기도 하며 여러가지 최적화를 통해 더 효율적으로 동작하게 만들 수도 있습니다.

\( m \)개의 정수 \( a_i \)를 입력받아서 \( a_i \)번째 피보나치 수를 \( 10^9 + 7 \)로 나눈 나머지를 출력하는 문제를 생각해봅시다. 단, \( F_0 = 0, \,\, F_1 = 1 \)이고 \( 0 \leq a_i \leq 10,000 \) 입니다. 이전에 살펴봤던 대로 재귀를 통해 구현하게 되면 시간복잡도가 \( O\left(2^{\max(a_i)}\right) \)로 굉장히 커지니 불필요한 반복을 줄일 방법을 찾아야 합니다. 입력은 최대 1만까지 들어올 수 있고 \( m \)개의 피보나치 수를 출력 하면 되는데, 0번부터 1만번까지 피보나치 수를 미리 계산해 둔다면 매번 새로 구하지 않고 바로바로 가져다 출력하기만 하면 됩니다. 코드로 바꾸면

constexpr int MOD = 1e9 + 7;

int main() {
    int fibo[10001];
    fibo[0] = 0; fibo[1] = 1;
    for (int i = 2; i <= 10000; i++)
        fibo[i] = (fibo[i - 1] + fibo[i - 2]) % MOD;

    int m; cin >> m;
    while (m--) {
        int n; cin >> n;
        cout << fibo[n] << '\n';
    }
}

이렇게 fibo 배열을 통해서 선형 시간에 피보나치 수를 모두 구해놓고 필요할 때마다 접근해서 사용할 수 있었습니다. 이 코드에서 핵심은 fibo[i - 1] + fibo[i - 2] 입니다. 이렇게 구성하면 이전에 계산했던 값을 추가적인 계산 없이 바로바로 가져다 쓸 수 있습니다. 이런 방식을 dp라고 부릅니다. dp는 일반적으로 배열로 구현되며 배열의 인덱스로 어떤 상태를 나타내서 필요한 상태의 값을 \( O(1) \)에 가져오는 것이 핵심입니다.

위 코드처럼 낮은 인덱스에서 높은 인덱스로 올라오는 방식을 bottom-up dp라고 합니다. 가장 대중적으로 사용되는 방식이며 보통 반복문으로 구현됩니다. 그렇다면 반대로 위에서 내려오는 방식도 있습니다. 이것을 top-down dp라고 부르고 보통 재귀를 통해 구현됩니다. 앞 챕터에서 재귀로 피보나치를 구했던 코드에서 약간만 수정하면 됩니다. 일종의 메모이제이션이라고도 볼 수 있습니다. 코드로 구현해 봅시다.

constexpr int MOD = 1e9 + 7;
int dp[10001];

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

    return dp[x] = (fibo(x - 1) + fibo(x - 2)) % MOD;
}

int main() {
    fill(dp, dp + 10001, -1);

    int m; cin >> m;
    while (m--) {
        int n; cin >> n;
        cout << fibo(n) << '\n';
    }
}

bottom-up 코드는 시작하자마자 1만개의 피보나치 수를 모두 계산하고 시작했는데, top-down 에서는 요청을 받으면 계산했습니다. 결과는 똑같지만 메모리와 속도 측면에서 약간의 차이가 있습니다. bottom-up은 모두 계산하고 시작하기 때문에 실행하고 약간의 딜레이 후 입력을 받기 시작합니다. 대신 입력이 들어오면 출력은 바로 나옵니다. top-down에서는 아무런 딜레이 없이 시작하지만 입력이 들어온 후 값이 계산되어 있지 않다면 그때 계산하고 출력합니다. 여기서 1만 길이의 배열을 미리 만들어서 저장해 두는 것이 비효율적이라고 느껴질 수 있습니다. 실제로 어떤 숫자가 들어올지 모르기 때문입니다. 그런 경우 top-down 방식에 1만개짜리 배열을 만드는 대신 hash map을 적용해 그때그때 필요한 숫자만 저장해서 메모리를 최대한 줄일 수 있습니다. 어떤 방식이던 자신의 목적에 맞게 작성하면 됩니다. 보통은 메모리가 시간보다 쌉니다.

연습문제

dp는 길게 설명하기보단 직접 많은 문제를 풀어 보는 것이 중요합니다. 그래서 기초적인 dp를 소개하고 많은 연습문제를 제시하는 것으로 마치도록 하겠습니다. 아래 문제는 기본적인 dp의 유형입니다. 이 외에도 비트마스킹을 이용한 dp, 트리에서의 dp 등 여러 알고리즘과 같이 조합될 수 있습니다. 또, convex hull, divide and conquer 등 여러 기법을 사용해서 최적화하는 고급 기술들도 등장하게 됩니다. 고급 최적화 알고리즘에 대해서는 다른 챕터에서 자세히 얘기해 보도록 합시다.