Explaining Dynamic Programming "동적 프로그래밍 (DP)"

moon.kick·2025년 5월 3일

Explaining Dynamic Programming

User mentioned "동적 프로그래밍 (DP)", and they likely want an explanation. I think they’re looking for an in-depth discussion on DP—what it is, when to use it, and how to spot DP problems like Fibonacci, coin change, and knapsack. I'll make sure to clarify the difference between memoization vs tabulation, and provide clear examples along with code.

I'll keep the tone energetic and structured to match their previous vibe, maybe even using some Korean examples for familiarity!

11초 동안 생각함

🎲 Dynamic Programming (DP) 완전 공략 가이드
(“암기” → “감각” → “응용” 순으로 설계했어요. 편하게 따라오세요!)

1. DP란?

키워드	한줄 정의	직관
Overlapping Sub-problems	같은 계산을 계속 반복한다	“F₄를 구하려는데 F₂를 두 번, F₃도 두 번…”
Optimal Sub-structure	큰 문제의 최적해가 작은 문제의 최적해로 조합된다	“0-1 배낭: ‘남은 무게 w에서 최대 가치’ → 한 물건 넣느냐 마느냐”

DP = “한 번 푼 건 저장해 두고, 작은 최적해를 재사용해 큰 최적해를 만든다.”

2. 두 얼굴: Memoization vs Tabulation

방식	구현	장점	단점
Top-Down (Memoization)	재귀 + 딕셔너리(배열) 캐시	코드 직관적, 필요한 것만 계산	재귀 깊이 = 호출 스택 사용, 함수 호출 오버헤드
Bottom-Up (Tabulation)	작은 값부터 ↑ 배열 채우기	스택 OK, 상수 오버헤드 ↓	복잡한 상태일 때 순회 순서 설계 필요

3. DP 문제 해결 4-Step 템플릿

State 정의
- “무엇이 변할 때 새로 계산해야 하나?” → 보통 인덱스·용량·잔돈 등이 변수
Recurrence(Transition) 수립
- 현재 상태를 더 작은 상태로 분해
Base Case
- 가장 작아서 바로 답을 알 수 있는 상태
Implementation
- Top-Down 혹은 Bottom-Up + 캐시 배열 사이즈 점검

📌 tip: “상태 수 × 상태당 연산” = 시간 복잡도, 캐시 배열 크기 = 공간 복잡도!

4. 대표 예제 ⓔ코드 & 직감

4-1. 피보나치 (1D DP, O(n))

def fib(n):
    if n < 2:  # base
        return n
    dp = [0, 1] + [0]*(n-1)
    for i in range(2, n+1):
        dp[i] = dp[i-1] + dp[i-2]
    return dp[n]
# 공간 최적화 → 두 변수만 써도 OK

4-2. 0-1 Knapsack (2D DP, O(nW))

def knapsack(items, W):
    # items = [(w,v), …]
    n = len(items)
    dp = [[0]*(W+1) for _ in range(n+1)]
    for i,(w,v) in enumerate(items, 1):
        for cap in range(W+1):
            if w > cap:            # 못 넣음
                dp[i][cap] = dp[i-1][cap]
            else:                  # 넣을지 말지
                dp[i][cap] = max(dp[i-1][cap],
                                 dp[i-1][cap-w]+v)
    return dp[n][W]
# 1D 배열 cap 역순 순회로 공간 O(W) 가능

4-3. LIS(최장 증가 부분수열) – 이분 탐색 결합 (O(n log n))

길이 k인 증가 subseq의 최소 끝값을 dp[k]로 유지
매 원소마다 bisect_left(dp, x) 위치 갱신

DP + 그리디/이분 = 하이브리드 패턴도 많습니다!

5. 흔한 패밀리별 초심자 → 중급 러닝 코스

단계	문제 유형	키 포인트
Level 1	1D: Climbing Stairs, House Robber, Fibonacci	점화식 바로 보이도록 훈련
Level 2	2D 그리드: Unique Paths, 최소비용 경로	방향성·경계 조건
Level 3	배낭류: 0-1, Unbounded, Partition Equal Subset	용량(capacity) 축
Level 4	문자열: LCS, Edit Distance, Palindrome Partitioning	두 인덱스(i, j) → 2D
Level 5	DP + 비트마스크/트리: Traveling Salesman, Tree DP	상태 압축·트리 순회
Level 6	DP + 슬라이딩 윈도: 수열 합 최적화, Convex Hull Trick	점화식 가속, deque

6. 시간·공간 복잡도 감 잡기

유형	상태 수	per-state 연산	T	S
1D (index)	n	O(1)	O(n)	O(n) → O(1) 최적화 가능
2D (i, j)	n²	O(1)	O(n²)	O(n²)
배낭 (i, W)	n·W	O(1)	O(nW)	O(nW) → O(W)
비트마스크	n·2ⁿ	O(1)	O(n 2ⁿ)	O(n 2ⁿ)

7. 디버깅 & 실전 팁

배열 범위 먼저: dp 크기 부족 → IndexError 💥
Base Case 체크: n=0,1 시험 입력 필수
메모리 초과(ML) 나면?
- 테이블 압축, defaultdict sparse 캐시, 비트마스크 등
Visualize: 표·격자 그려서 상태 전이 화살표 직접 그려보면 속이 뻥!

8. 연습 플랫폼 & 추천 문제 세트

난이도	사이트	문제 리스트(예시)
입문	백준 1463, 1699, 2579	1D 점화식
중급	LeetCode 62, 198, 300, 518	그리드·배낭·LIS
고급	백준 2098(TSP), 13913(경로 출력)	비트마스크·경로 추적
도전	AtCoder DP Contest (A~Z)	모든 유형 한꺼번에