[TIL] 동적 계획법으로 중복 계산 줄이기

DP가 성립하는 조건

동적 계획법, 즉 DP는 큰 문제의 답을 작은 문제의 답으로 만들 수 있을 때 사용합니다. 피보나치 수열을 예로 들면 F(5)는 F(4)와 F(3)의 합으로 표현됩니다. 이렇게 작은 문제의 최적 답이나 계산 결과가 큰 문제의 답을 구성하는 성질을 최적 부분 구조라고 부릅니다.

또 하나 중요한 조건은 같은 작은 문제가 반복해서 등장한다는 점입니다. 피보나치를 단순 재귀로 구현하면 F(3), F(2) 같은 값이 여러 번 다시 계산됩니다. DP의 핵심은 이 중복 계산을 배열이나 테이블에 저장해두고, 필요할 때 꺼내 쓰는 것입니다.

DP는 "모든 경우를 보되, 이미 계산한 답은 다시 계산하지 않는다"는 감각으로 접근하면 이해하기 쉽습니다. 일반 재귀 피보나치는 대략 O(2^n)까지 커질 수 있지만, DP로 저장하면 O(n)에 처리할 수 있습니다.

Top-Down: 재귀와 메모이제이션

Top-Down 방식은 문제를 재귀적으로 내려가며 풀고, 이미 구한 값은 메모이제이션 배열에 저장합니다. 자연스럽게 점화식을 코드로 옮길 수 있어 처음 생각하기 쉽습니다.

#include <iostream>
#include <vector>
using namespace std;

vector<int> dp;

int fib(int n)
{
    if (n <= 1) return n;

    if (dp[n] != -1)
        return dp[n];

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

int main()
{
    int n = 10;
    dp.assign(n + 1, -1);

    cout << fib(n);

    return 0;
}

여기서 핵심은 if (dp[n] != -1) return dp[n];입니다. 이미 계산한 값이면 재귀를 더 내려가지 않고 바로 반환합니다.

• 장점: 재귀 구조를 그대로 사용할 수 있어 점화식을 떠올리기 쉽다.
• 단점: 입력이 크면 재귀 깊이 때문에 스택 오버플로우가 날 수 있고, 함수 호출 비용이 있다.

Bottom-Up: 반복문과 테이블

Bottom-Up 방식은 가장 작은 값부터 차례대로 테이블을 채워 큰 답까지 올라갑니다. 재귀를 사용하지 않기 때문에 실행 흐름이 안정적이고, 코딩 테스트에서도 자주 쓰입니다.

#include <iostream>
#include <vector>
using namespace std;

int main()
{
    int n = 10;
    vector<int> dp(n + 1);

    dp[0] = 0;
    dp[1] = 1;

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

    cout << dp[n];

    return 0;
}

• 장점: 재귀보다 안정적이고, 반복 범위와 성능을 예측하기 쉽다.
• 단점: dp[i]의 의미와 점화식을 제대로 세우지 못하면 테이블을 채울 수 없다.

DP 풀이 순서

DP 문제는 코드부터 쓰기보다 배열의 의미를 먼저 정해야 합니다. dp[i]가 무엇을 뜻하는지 한 문장으로 정의하면 초기값, 점화식, 반복 범위가 따라오기 쉬워집니다.

1. dp 배열의 의미를 정한다.
2. 점화식이 시작될 초기값을 정한다.
3. 현재 답을 이전 답으로 표현하는 점화식을 세운다.
4. 인덱스가 터지지 않도록 반복 범위를 정한다.

예시: 계단 오르기

한 번에 1칸 또는 2칸 오를 수 있을 때, n번째 계단까지 가는 방법의 수를 구한다고 해보겠습니다. n번째 계단에 도착하는 방법은 두 가지입니다.

• n - 1번째 계단에서 1칸 오른다.
• n - 2번째 계단에서 2칸 오른다.

따라서 dp[n] = dp[n - 1] + dp[n - 2]로 표현할 수 있습니다. 여기서 dp[i]는 i번째 계단까지 가는 방법의 수입니다.

#include <iostream>
#include <vector>
using namespace std;

int main()
{
    int n;
    cin >> n;

    vector<int> dp(n + 1);

    dp[0] = 1;
    dp[1] = 1;

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

    cout << dp[n];

    return 0;
}

이 예제에서 dp[0] = 1은 "아무것도 하지 않는 방법 1개"로 해석합니다. 이런 초기값 해석이 DP에서는 자주 중요합니다. 초기값은 점화식의 출발점이기 때문입니다.

DP를 의심할 신호

모든 문제를 DP로 풀 수 있는 것은 아니지만, 아래 조건이 보이면 먼저 DP 가능성을 떠올려볼 만합니다.

• 이전 답으로 현재 답을 표현할 수 있다
• 현재 상태가 더 작은 상태의 결과로 만들어지면 점화식을 세울 수 있습니다.
• 같은 계산이 반복된다
• 완전탐색이나 재귀에서 같은 하위 문제가 여러 번 등장하면 저장해서 재사용할 수 있습니다.
• 경우의 수, 최댓값, 최솟값, N번째 값을 묻는다
• 계단 오르기, 타일 채우기, 정수 삼각형, 배낭 문제, LIS, 동전 교환, LCS 같은 문제가 대표적입니다.

자주 하는 실수

dp[i]의 의미를 정하지 않고 코드부터 짠다

가장 먼저 적어야 하는 문장은 dp[i] = ?입니다. 이 정의가 없으면 초기값과 점화식이 서로 어긋나기 쉽습니다.

초기값을 대충 넣는다

dp[0], dp[1] 같은 값은 점화식의 출발점입니다. 출발점이 틀리면 이후 테이블을 아무리 잘 채워도 결과가 틀립니다.

인덱스 범위를 확인하지 않는다

dp[i] = dp[i - 1] + dp[i - 2]처럼 이전 두 칸을 참조한다면 반복문은 최소 i = 2부터 시작해야 합니다. i = 1부터 돌리면 dp[-1]처럼 잘못된 접근이 생길 수 있습니다.

정리

• DP는 큰 문제를 작은 문제로 나누고, 이미 구한 답을 저장해 중복 계산을 줄인다.
• 최적 부분 구조와 중복 부분 문제가 보이면 DP를 사용할 수 있는지 의심해볼 만하다.
• Top-Down은 재귀와 메모이제이션으로 자연스럽게 작성하기 쉽다.
• Bottom-Up은 반복문으로 작은 값부터 테이블을 채워 안정적으로 동작한다.
• 풀이 전에는 반드시 dp[i]의 의미, 초기값, 점화식, 반복 범위를 정한다.

DP는 처음에는 어렵게 느껴지지만, 결국 "현재 답을 이전에 구한 답들로 어떻게 표현할 것인가"를 찾는 연습입니다. 이 문장 하나를 붙잡고 문제를 쪼개면 코드보다 먼저 구조가 보이기 시작합니다.