DP 기초

동적 계획법이란?

동적 계획법(Dynamic Programming, DP) 은 큰 문제를 겹치는 작은 문제들로
쪼개고, 한 번 푼 작은 문제의 답을 저장해 두어 다시 풀지 않는 기법입니다.

재귀에서 같은 계산을 수없이 반복하던 것을, "한 번 구한 답은 적어 두고 재사용"
하는 것으로 바꾸면 지수 시간이 다항 시간이 됩니다.

1. DP가 통하는 두 조건

• 겹치는 부분 문제(overlapping subproblems): 같은 작은 문제가 여러 번 등장한다.
• 최적 부분 구조(optimal substructure): 작은 문제의 최적해로 큰 문제의 최적해를
  만들 수 있다.

이 두 조건이 보이면 DP를 의심하세요. 피보나치, 계단 오르기, 배낭 문제가
대표적입니다.

2. 두 가지 구현 방식

둘은 같은 점화식을 다른 순서로 채울 뿐 본질은 같습니다. 재귀가 자연스러우면
메모이제이션, 반복이 깔끔하면 타뷸레이션을 씁니다.

3. DP 설계의 3단계

DP 문제는 거의 항상 이 순서로 풉니다.

1. 상태 정의: dp[i]가 무엇을 의미하는지 명확히 정한다.
   (예: dp[i] = \(i\)번째 계단까지 오는 경우의 수)
2. 점화식 세우기: dp[i]를 더 작은 dp들로 표현한다.
   (예: dp[i] = dp[i-1] + dp[i-2])
3. 초기값과 순서: 가장 작은 상태(기저)를 정하고, 의존하는 순서대로 채운다.

상태를 무엇으로 잡느냐가 DP의 8할입니다. 상태가 잘 정의되면 점화식은 따라옵니다.

4. 예: 계단 오르기

한 번에 1칸 또는 2칸 오를 수 있을 때 \(N\)칸 오르는 방법의 수.

$$ dp[i] = dp[i-1] + dp[i-2] $$

\(i\)번째 칸에 오는 마지막 발걸음이 1칸이었으면 \(dp[i-1]\)에서, 2칸이었으면
\(dp[i-2]\)에서 왔기 때문입니다. 초기값 \(dp[0]=1, dp[1]=1\).

이 "마지막 선택으로 경우를 나눈다"는 사고가 점화식의 핵심입니다.

5. 복잡도

DP의 복잡도는 보통 (상태의 개수) × (한 상태를 계산하는 비용) 입니다.

• 1차원 상태 \(dp[i]\), 각 전이가 상수 → \(O(N)\).
• 2차원 상태 \(dp[i][j]\), 전이 상수 → \(O(NM)\).

단순 재귀의 지수 시간이, 메모이제이션으로 "상태 수만큼만" 계산하게 되어 극적으로
줄어듭니다.

정리

DP는 "겹치는 작은 문제의 답을 저장해 재사용"하는 기법입니다. 상태를 정의하고,
점화식을 세우고, 순서대로 채웁니다. 상태 정의가 가장 중요하며, 이것이
Silver 이후 수많은 문제의 핵심 무기가 됩니다. 다음 강의에서 코드로 익힙니다.

DP를 코드로

같은 문제를 메모이제이션과 타뷸레이션 두 방식으로 짜 보며 감을 잡습니다.

1. 피보나치: 두 방식 비교

메모이제이션 (top-down)

long long memo[100];
bool done[100];
long long fib(int n) {
    if (n <= 1) return n;
    if (done[n]) return memo[n];      // 이미 풀었으면 재사용
    done[n] = true;
    return memo[n] = fib(n - 1) + fib(n - 2);
}

타뷸레이션 (bottom-up)

long long dp[100];
dp[0] = 0; dp[1] = 1;
for (int i = 2; i <= n; i++)
    dp[i] = dp[i - 1] + dp[i - 2];    // 작은 것부터 채움
// 답: dp[n]

# 타뷸레이션
dp = [0] * (n + 1)
if n >= 1: dp[1] = 1
for i in range(2, n + 1):
    dp[i] = dp[i - 1] + dp[i - 2]

done 배열로 "계산 여부"를 따로 두는 이유: \(0\)이 유효한 답일 수 있어, memo가
\(0\)인 것만으로는 미계산과 구분할 수 없기 때문입니다.

2. 1차원 DP 예: 최대 연속 부분 합

dp[i] = \(i\)번째 원소로 끝나는 부분 배열의 최대 합.

long long dp[100001], ans = LLONG_MIN;
for (int i = 0; i < n; i++) {
    dp[i] = a[i];
    if (i > 0) dp[i] = max(dp[i], dp[i - 1] + a[i]);  // 이어 붙일까 새로 시작할까
    ans = max(ans, dp[i]);
}

ans = a[0]
cur = a[0]
for i in range(1, n):
    cur = max(a[i], cur + a[i])     # 새로 시작 vs 이어 붙이기
    ans = max(ans, cur)

"\(i\)로 끝나는"으로 상태를 잡으면, 각 단계의 선택이 "새로 시작 vs 이어 붙이기"
둘뿐이라 점화식이 단순해집니다.

3. 2차원 DP 예: 격자 경로 수

\((0,0)\)에서 \((n,m)\)까지 오른쪽·아래로만 가는 경로의 수.

long long dp[1001][1001];
for (int i = 0; i <= n; i++)
    for (int j = 0; j <= m; j++) {
        if (i == 0 && j == 0) { dp[i][j] = 1; continue; }
        long long up   = (i > 0) ? dp[i-1][j] : 0;
        long long left = (j > 0) ? dp[i][j-1] : 0;
        dp[i][j] = up + left;          // 위 또는 왼쪽에서 옴
    }

4. 메모리 최적화: 슬라이딩

dp[i]가 dp[i-1], dp[i-2]에만 의존하면 배열 전체가 필요 없습니다.

long long a = 0, b = 1;
for (int i = 2; i <= n; i++) { long long c = a + b; a = b; b = c; }
// 답: b

변수 두세 개로 \(O(1)\) 메모리에 끝낼 수 있습니다.

5. 흔한 실수

• 상태 정의 모호 — dp[i]가 뭘 뜻하는지 한 문장으로 못 적으면 점화식이 꼬입니다.
• 초기값 누락 — 기저 상태를 안 채우면 전부 0/쓰레기. 꼭 먼저 설정.
• 채우는 순서 오류 — dp[i]가 의존하는 값이 먼저 채워져야 합니다.
• 메모 0과 미계산 혼동 — 0이 유효 답이면 별도 방문 플래그 사용.
• 오버플로 — 경우의 수/합은 금방 커집니다. long long 또는 모듈러.

6. 패턴 알아보기

• "경우의 수", "최대/최소 ~", "방법의 수" + 선택이 단계적으로 누적 → DP.
• 단순 재귀가 같은 인자로 여러 번 불린다 → 메모이제이션.
• "\(i\)번째까지/로 끝나는"으로 상태를 잡으면 점화식이 보이는 경우가 많습니다.

실전에서 DP 문제 알아보기

DP의 벽은 "점화식이 안 보인다"입니다. 점화식은 영감이 아니라 절차로
찾는 것입니다. 신호 → 상태 → 전이 순서의 작업 흐름을 정리합니다.

1. 출제 신호

• "경우의 수를 구하시오" — 세는 문제는 거의 항상 DP 또는 조합론입니다.
• "최댓값/최솟값" + 선택이 연속됨 — 계단 오르기, 포도주처럼 매 단계의
  선택이 다음 선택을 제약하는 구조.
• 완전 탐색은 지수인데 \(N\)이 수천~수십만 — 탐색 공간은 크지만 "지금까지의
  요약"이 작다는 신호입니다.
• 현재 결정에 필요한 과거 정보가 적다 — 직전 1~2개의 선택만 알면 충분한
  구조(이게 곧 상태 정의의 힌트입니다).
• 문제 끝에 "~로 나눈 나머지를 출력" — 답이 매우 커지는 세기 문제 = DP
  신호의 단골입니다.

2. 풀이 결정 절차

1. 상태 정의 — "\(dp[i]\) = (앞 \(i\)개만 고려했을 때의) 최적값/경우의 수"를
   한국어 문장으로 완전한 한 문장이 되게 적습니다.
2. 전이 — 마지막 선택을 기준으로 경우를 나눕니다. "마지막 칸을 1칸으로
   왔다면 / 2칸으로 왔다면" 식으로.
3. 기저 — 가장 작은 입력 2~3개를 손으로 계산해 채웁니다.
4. 복잡도 = 상태 수 × 전이 비용을 계산해 제한과 비교합니다.
5. 작은 예제를 표로 손 검산한 뒤에 코딩합니다.

3. 자주 하는 실수

• 상태 부족. "계단을 연속 세 칸 못 밟는다"면 \(dp[i]\)만으로는 직전에 몇 칸
  연속으로 밟았는지 모릅니다. \(dp[i][j]\)(\(j\) = 연속 정보)로 차원을 늘리세요.
  "전이를 쓰다가 과거 정보가 더 필요해지면 상태에 넣는다"가 일반 규칙입니다.
• 모듈러 뺄셈 음수. 세기 DP에서 빼기가 나오면 음수가 될 수 있습니다.

const long long MOD = 1'000'000'007;
dp[i] = (dp[i - 1] + dp[i - 2]) % MOD;          // 더하기는 그냥 모듈러
long long diff = ((a - b) % MOD + MOD) % MOD;   // 빼기는 +MOD 보정 필수

• 불가능 상태와 0의 혼동. 최댓값 DP에서 "아직 도달 불가"를 0으로 두면
  진짜 값 0과 섞입니다. \(-\infty\)(충분히 작은 수)로 초기화해 구분하세요.
• 갱신 순서. 타뷸레이션에서 \(dp[i]\)가 \(dp[i-1]\)을 참조하는데 거꾸로 돌면
  쓰레기 값을 읽습니다. 의존성 방향대로 채우는지 확인하세요.
• 메모이제이션 초기값 충돌. "미계산" 표시를 \(-1\)로 했는데 실제 답이
  \(-1\)이 될 수 있는 문제면 별도 visited 배열로 분리해야 합니다.

4. 연습 방법

이 페이지 오른쪽의 추천 문제는 쉬운 순 → 어려운 순입니다. 1차원 한 줄
점화식부터 시작해 2차원 상태, "상태를 늘려야 풀리는" 문제로 이어집니다.

모든 문제에서 상태 정의 문장을 코드 맨 위에 주석으로 적고 시작하세요.
막히면 코드가 아니라 그 문장을 고치는 것입니다. 3문제 이상 풀어
클리어하면 레이팅의 CLASS 보너스에 반영됩니다.