동적 계획법 (DP)

DP가 필요한 상황

핵심 정의

• DP(Dynamic Programming)는 중복되는 부분 문제 결과를 저장해 재사용하는 기법입니다.
• 목표는 "같은 계산을 여러 번 하지 않도록" 만드는 것입니다.

DP가 성립하는 2가지 조건

1. 중복 부분 문제(Overlapping Subproblems)
   • 같은 상태를 여러 번 계산한다.
2. 최적 부분 구조(Optimal Substructure)
   • 큰 문제의 해답을 작은 문제 해답으로 조합할 수 있다.

구현 방식

방식	별칭	특징
Top-down	Memoization	재귀 + 캐시
Bottom-up	Tabulation	작은 상태부터 반복문으로 누적

---

Top-down vs Bottom-up 선택 기준

항목	Top-down	Bottom-up
작성 난이도	점화식 그대로 써서 직관적	순회 순서 설계 필요
호출 오버헤드	재귀 오버헤드/스택 사용	재귀 없음, 스택 안전
필요한 상태만 계산	가능	보통 전체 상태 계산
실무 감각	빠른 구현/검증에 유리	성능·안정성 튜닝에 유리

짧은 기준:

• 점화식 검증 단계 -> Top-down
• 성능/스택 안정성 중요 -> Bottom-up

---

콤비네이션 예 (C(n, r))

상태/점화식

• 상태: C(n, r)
• 점화식: C(n, r) = C(n-1, r-1) + C(n-1, r)
• 기저: r == 0 또는 n == r -> 1

Top-down(메모이제이션)

long long cache[51][51];

long long Combination(int n, int r) {
    if (r == 0 || n == r) return 1;
    long long& ret = cache[n][r];
    if (ret != -1) return ret;
    return ret = Combination(n - 1, r - 1) + Combination(n - 1, r);
}

초기화:

memset(cache, -1, sizeof(cache));

복잡도

• 순수 재귀: 지수 시간(중복 호출 폭발)
• DP 적용: 상태 수가 (n+1)*(r+1)이므로 대략 O(n*r)

---

인센트(강화) 예

문제:

• 현재 강화 수치 num에서 목표 N까지 도달하는 경우의 수
• 한 번에 +1, +2, +3 중 하나 증가

점화식:

• E(num) = E(num+1) + E(num+2) + E(num+3)
• 기저:
  • num == N -> 1 (정확히 도달)
  • num > N -> 0 (초과)

Top-down 예시:

long long cache[101];

long long Ways(int num, int N) {
    if (num == N) return 1;
    if (num > N) return 0;
    long long& ret = cache[num];
    if (ret != -1) return ret;
    return ret = Ways(num + 1, N) + Ways(num + 2, N) + Ways(num + 3, N);
}

주의:

• 경우의 수가 커지면 int가 쉽게 overflow -> long long 또는 모듈러 연산 사용

---

DP 설계 템플릿 (실전용)

// 1) 상태 정의
// dp[state]가 무엇을 의미하는지 문장으로 먼저 정의

Type Solve(State s) {
    // 2) 기저 사례
    if (종료조건) return 기본값;

    // 3) 캐시 확인
    Type& ret = cache[s];
    if (ret != 초기값) return ret;

    // 4) 점화식 계산
    ret = combine(Solve(작은상태1), Solve(작은상태2), ...);
    return ret;
}

검증 체크리스트:

단계	질문	예시 (콤비네이션)
1	상태가 무엇인가?	(n, r)
2	기저는 완전한가?	r==0, n==r
3	점화식이 상태를 줄이는가?	n이 감소
4	캐시 범위/초기값이 안전한가?	cache[51][51], -1
5	오버플로우 가능성은 없는가?	long long 사용 여부

---

자주 하는 실수 + 체크 질문

자주 하는 실수

실수	문제
상태 정의 없이 점화식부터 작성	캐시 인덱스/의미 혼선
기저 조건 누락	무한 재귀/잘못된 결과
캐시 초기값과 정상값이 충돌	memo miss/hit 판정 오류
큰 경우의 수를 int로 저장	overflow
Top-down만 고집해 깊은 재귀 사용	스택 오버플로우 위험

체크 질문 (스스로 답해보기)

• 이 문제가 DP 문제인지(중복 부분 문제 + 최적 부분 구조) 어떻게 판별할까?
• Top-down과 Bottom-up 중 무엇을 선택할지 기준이 있는가?
• 캐시 초기값을 무엇으로 둘지, 왜 그렇게 정하는지 설명할 수 있는가?

---