Dynamic Programming & Memoization

1. Overview

동적 프로그래밍과 메모이제이션(Dynamic Programming & Memoization)은 복잡한 문제를 단순 재귀로 풀면 같은 하위 문제를 수억 번 중복 계산하는 지수 폭탄을 막기 위해, 이미 계산한 결과를 캐시(메모)에 저장하고 재사용하여 O(2ⁿ) 문제를 O(n²) 또는 O(n)으로 단축하는 최적화 패러다임입니다.

학습자는 재귀 + 메모이제이션(Top-Down, Memoization)과 반복 + 테이블 채우기(Bottom-Up, Tabulation) 두 가지 DP 구현 방식의 코드와 시공간 트레이드오프를 뜯어봅니다. 나아가 DP가 적용되기 위한 두 가지 핵심 조건인 **최적 부분 구조(Optimal Substructure)**와 **중복 하위 문제(Overlapping Subproblems)**를 식별하는 눈을 갖추고, 배낭 문제(Knapsack), 최장 공통 부분열(LCS), 편집 거리(Edit Distance), 행렬 연쇄 곱셈(MCM)을 해부하여 DP 설계 역량을 확보합니다.

2. Scope & Boundaries

In-Scope

• DP 두 가지 구현 (Top-Down vs Bottom-Up): 메모이제이션(재귀 + 딕셔너리 캐시), 타뷸레이션(반복 + 배열 테이블), 공간 최적화(Rolling Array).
• DP 적용 조건 (DP Prerequisites): 최적 부분 구조(Optimal Substructure), 중복 하위 문제(Overlapping Subproblems), 상태 정의(State Definition), 점화식(Recurrence Relation) 도출.
• 클래식 DP 문제 (Classic DP Problems): Fibonacci, Coin Change, 0/1 배낭(Knapsack), LCS(Longest Common Subsequence), Edit Distance, Longest Increasing Subsequence(LIS), MCM(Matrix Chain Multiplication).
• DP 최적화 기법 (DP Optimizations): 공간 압축(Space Compression, O(n²)→O(n)), Divide-and-Conquer DP 최적화.

Out-of-Scope

• 그래프 DP(Bellman-Ford, Floyd-Warshall): 그래프의 최단 경로 DP $\rightarrow$ 04-04-01. Graph Foundations & Flow 영역.
• 확률적 DP(Markov Chain, HMM): 확률 모델에 기반한 DP $\rightarrow$ AI/ML 영역.

Boundaries

• D&C vs DP: 분할 정복(04-03-01)의 하위 문제는 독립(Independent)이라 캐싱이 불필요합니다. DP의 하위 문제는 겹침(Overlapping)이라 캐싱이 필수입니다. fib(50) 재귀: fib(48)이 fib(49)와 fib(47) 계산 과정에서 각각 독립적으로 호출되어 중복 계산 → DP 대상. merge_sort(arr[:5])와 merge_sort(arr[5:]): 서로 독립 → D&C 대상.

3. Counterexample

• DP 없는 재귀 LCS의 O(2^m+n) 폭탄 (LCS without Memoization): 두 문자열 s1="ABCDE", s2="ACE"의 최장 공통 부분열(LCS)을 메모이제이션 없는 순수 재귀로 푸는 경우. lcs(i,j)가 lcs(i-1,j-1), lcs(i-1,j), lcs(i,j-1) 세 하위 문제를 각각 재귀로 호출하고, 각각이 또 세 개를 호출하여 호출 트리가 지수적으로 폭발합니다. m=n=100이면 2^200 ≈ 10^60 연산으로 우주가 끝나도 완료되지 않습니다. DP 테이블로 O(mn)에 해결됩니다.
• 잘못된 상태 정의의 부분 최적 함정 (Subproblem Misidentification): 코인 체인지(Coin Change, 동전으로 금액 만들기) 문제를 그리디(Greedy, 항상 가장 큰 동전 선택)로 푸는 실수. 동전 [1,3,4]로 금액 6을 만드는 최소 동전 수: 그리디는 4+1+1 = 3개를 선택하지만, 최적은 3+3 = 2개입니다. 탐욕적 선택이 전역 최적을 보장하지 않으므로 DP가 필요합니다.

4. Prerequisites

• 재귀 (Recursion) (Basic): DP의 Top-Down(메모이제이션)은 재귀 기반이므로 재귀 사고가 필수입니다. (04-03-01 Recursion)
• 배열/딕셔너리 (Basic): 메모이제이션 캐시(딕셔너리)와 DP 테이블(배열) 조작이 필요합니다. (04-01-01 Arrays)

5. Learning Map

6. Learning Topics

Basic

Core Topic 01: 기억하는 재귀와 밑에서 쌓는 테이블, DP 두 패러다임 (Top-Down vs Bottom-Up)

• Why to Learn: 같은 DP 문제를 "재귀 + 메모"(Top-Down)와 "반복 + 테이블"(Bottom-Up) 두 방식으로 구현할 수 있음을 알고, 각 방식의 코드 구조, 스택 공간, 캐시 접근 패턴의 트레이드오프를 정확히 선택하기 위함입니다.
• What to Learn:
  • Concepts: 메모이제이션(Memoization, Top-Down, 재귀+캐시), 타뷸레이션(Tabulation, Bottom-Up, 반복+테이블), 최적 부분 구조, 중복 하위 문제.
  • Skills: @functools.lru_cache 데코레이터, Bottom-Up 점화식 도출.
  • Tools: Python functools.lru_cache(maxsize=None).
• How to Learn:
  • 1단계: fib(10) Top-Down: memo = {}; fib(10) = fib(9) + fib(8) ... 처음 계산되면 memo[n] = result 저장. 이후 fib(9) 안에서 fib(8) 호출 시 memo[8] 즉시 반환. 호출 트리가 2^10 → 10개로 단축되는 역학을 해부합니다.
  • 2단계: fib(10) Bottom-Up: dp[0]=0, dp[1]=1, dp[i]=dp[i-1]+dp[i-2]. 반복문으로 dp[2]부터 dp[10]까지 채워나감. 재귀 스택 없이 O(n) 공간(또는 O(1) 두 변수)으로 해결되는 역학을 뜯어봅니다.
• Implement: 파이썬 fib_memo(n, memo={}) (Top-Down) vs fib_dp(n) (Bottom-Up). fib(40) 실행 시 Naive 재귀(수십초) vs 두 DP(즉시) 시간 비교. @lru_cache 데코레이터 한 줄로 메모이제이션을 자동화하는 방법 증명.

Recommended

Core Topic 02: 배낭 가득 채우기, 0/1 Knapsack DP (0/1 Knapsack)

• Why to Learn: DP의 가장 고전적이고 직관적인 예시인 배낭 문제는, 2D DP 테이블 구축의 패턴을 완벽히 이해하게 해주는 교육적 가치와, 자원 배분(Resource Allocation), 포트폴리오 최적화(Investment), 컴파일러 레지스터 할당의 직접적 응용을 갖춥니다.
• What to Learn:
  • Concepts: 0/1 배낭 문제 정의, dp[i][w] = i번째 물건까지 고려, 용량 w 이하일 때 최대 가치, 점화식 dp[i][w] = max(dp[i-1][w], dp[i-1][w-wt[i]] + val[i]).
  • Skills: 테이블 역추적(Traceback)으로 선택 물건 목록 복원, 1D Rolling Array로 O(n) 공간 최적화.
• How to Learn:
  • 1단계: 물건 [(wt=2,val=3), (wt=3,val=4), (wt=4,val=5)], 배낭 용량 W=5. dp[0~3][0~5] 2D 테이블을 행 단위로 채우는 역학. 물건 1(wt=2)을 넣을지 말지의 분기에 따라 테이블이 채워지는 과정을 해부합니다.
  • 2단계: 최종 dp[3][5]=7에서 역방향으로 테이블을 따라가며 어떤 물건이 선택되었는지(Traceback) 복원하는 역학을 뜯어봅니다.
• Implement: 파이썬 knapsack_01(weights, values, W). 2D dp[n+1][W+1] 테이블 채우기. knapsack([(2,3),(3,4),(4,5)], W=5) → 최대 가치 7과 선택 물건 목록 [(3,4),(2,3)] Traceback 증명.

Practical

Core Topic 03: 두 서열의 최대 공약수와 편집의 최소 비용, LCS와 Edit Distance (LCS & Edit Distance)

• Why to Learn: LCS(Longest Common Subsequence)는 Unix diff 명령어, Git blame, 생물정보학의 DNA 서열 유사도 분석의 핵심이며, Edit Distance(Levenshtein)는 맞춤법 교정기, 검색 퍼지 매칭, NLP 문자열 유사도의 핵심입니다.
• What to Learn:
  • Concepts: LCS 점화식 dp[i][j] = dp[i-1][j-1]+1 (s1[i]=s2[j]) 또는 max(dp[i-1][j], dp[i][j-1]). Edit Distance 점화식(Insert, Delete, Replace 비용).
  • Skills: LCS에서 실제 공통 부분열 복원(Traceback), Edit Distance 편집 연산 시퀀스 복원.
• How to Learn:
  • 1단계: LCS("ABCBDAB", "BDCABA"). dp[i][j]를 채울 때, s1[i]==s2[j]이면 대각선+1, 아니면 max(위, 왼쪽). 최종 dp[7][6]=4이 LCS 길이. 역추적으로 "BCBA" 출력을 해부합니다.
  • 2단계: Edit Distance("kitten", "sitting"). 삽입(위), 삭제(왼쪽), 교체(대각선) 중 최소 비용 선택. 최종 거리 3(s→k, e→i, +ing 삭제)을 뜯어봅니다.
• Implement: 파이썬 lcs(s1, s2) + edit_distance(s1, s2). lcs("ABCBDAB","BDCABA") → ("BCAB", 4). edit_distance("kitten","sitting") → 3. 두 함수 모두 Traceback으로 실제 연산 시퀀스(Insert/Delete/Replace 목록) 복원 출력.

Advanced

Core Topic 04: 테이블 반을 접어버리기, DP 공간 압축 (Rolling Array & Space Optimization)

• Why to Learn: LCS나 배낭 문제의 2D DP 테이블은 O(nm) 또는 O(nW) 공간을 요구하는데, n과 m이 10만이면 수십 기가바이트의 메모리가 필요합니다. Rolling Array로 O(n)으로 압축하는 기법은 실무 DP에서 필수적인 최적화입니다.
• What to Learn:
  • Concepts: Rolling Array(현재 행만 유지), 비트마스크 DP(집합 상태를 비트로 인코딩, TSP), LIS O(n log n) 이진 탐색 최적화.
  • Skills: dp[i][j] → dp[j] (1D), dp[i&1][j] (교대 2행) 변환 패턴.
• How to Learn:
  • 1단계: 0/1 Knapsack Rolling: dp[i][w]는 dp[i-1][w]와 dp[i-1][w-wt]만 참조. 따라서 1D 배열 dp[W+1]을 유지하고, 각 물건을 추가할 때 뒤에서 앞으로(Reverse Order) 업데이트하면 이전 행을 덮어쓰지 않는 Rolling Array 최적화를 해부합니다.
  • 2단계: LIS O(n log n): LIS를 O(n²) DP → O(n log n) 이진 탐색으로 최적화. patience 배열을 유지하며 새 원소를 이진 탐색으로 적절한 위치에 배치하는 역학을 뜯어봅니다.
• Implement: knapsack_1d(weights, values, W). 1D Rolling Array로 2D Knapsack을 구현. weights = [1,2,3,4,5], values = [1,6,10,16,10], W=10 → 최적값과 2D 결과와 동일함을 assert. LIS 두 가지 구현(O(n²) DP vs O(n log n) bisect)의 시간 비교 벤치마크.

7. Terminology

8. References

Primary

• [P2] SWEBOK v4.0 - Software Construction / Runtime Efficiency (Analysis) — DP and complexity.
• [P1] CS2023 - AL/Algorithms and Complexity (Dynamic Programming) — Core requirements.

Secondary

• [Introduction to Algorithms (CLRS)] Cormen — DP formal analysis.
• [Dynamic Programming for Coding Interviews] Meenakshi — Practical problem solving.

Industry

• [Google: Tech Dev Guide (Dynamic Programming)] — Real-world application patterns.
• [TopCoder: Dynamic Programming from Novice to Advanced] — Industry competition strategies.

9. Final Checklist

Primary

• 특정 문제를 해결할 때 '중복되는 부분 문제'를 수리적으로 식별해 내어 DP 적용 가능성을 판단할 수 있는 가? (P1)
• '메모이제이션(Top-down)'과 '타뷸레이션(Bottom-up)'의 물리적 실행 순서와 메모리 활용 차이를 설명 가능한가? (P1)

Secondary

• 주어진 문제의 '최적 부분 구조'를 입증하기 위해 '모순에 의한 증명(Proof by contradiction)' 논리를 소통 가능한가?
• DP 테이블의 공간 복잡도를 $O(n^2)$에서 $O(n)$으로 줄이는 '슬라이딩 윈도우' 식의 물리적 압축을 도출할 수 있는 가?

Industry

• 자연어 처리의 '편집 거리(Edit Distance)'나 유전자 서열 분석 시스템 설계 시 DP가 왜 물리적 표준 인프라인지 기술할 수 있는 가? (SFIA)
• 대규모 분산 환경에서 DP의 계산 결과를 공유 메모리(Redis 등)에 저장하여 처리 속도를 높이는 아키텍처를 제안할 수 있는 가?