Dynamic Programming & Memoization

1. Overview

동적 계획법 및 메모이제이션(Dynamic Programming & Memoization, DPM)은 "기억하지 않는 자는 과거의 실수를 반복한다"는 격언을 알고리즘 세계에 구현한 성능 최적화의 정수입니다.

복잡한 문제는 종종 수많은 작은 조각들로 구성되는데, 이 조각들은 서로 겹치는 경우가 많습니다. 학습자는 한 번 계산한 결과를 메모리(Cache)에 적어두고 재사용하는 메모이제이션(Memoization) 기술을 배웁니다. 또한, 작은 문제부터 차근차근 해답을 쌓아 올리는 상향식(Bottom-up, Tabulation) 접근법과 그 기반이 되는 **점화식(Recurrence Relation)**의 수리적 도출을 익힙니다. 이를 통해 지수 시간($O(2^n)$)의 수렁에 빠진 문제를 다항 시간($O(n^2), O(n)$)으로 구출해 내는 고도의 설계 통찰력을 확보합니다.

2. Scope & Boundaries

In-Scope

• DP Two Properties: 최적 부분 구조(Optimal Substructure)와 중복 부분 문제(Overlapping Subproblems) 판별
• Top-down vs Bottom-up: 재귀 기반의 Memoization과 반복문 기반의 Tabulation 물리 경로 비교
• State Definition: 문제를 풀기 위해 필요한 최소한의 변수(State)와 결정(Decision) 설계
• Classic DP Cases: 배낭 문제(Knapsack), 최장 공통 부분 수열(LCS), 행렬 곱셈 순서 등

Out-of-Scope

• 중복이 없는 단순 분할 정복 문제 (04-03-01 노드로 위임)
• 선형 계획법(Linear Programming)의 고차원 수학적 증명 (수치 해석 영역으로 분담)

Boundaries

• DPM vs. Greedy: Greedy가 '당장의 이익'만 보고 달린다면, DPM은 '모든 하위 가능성'을 기억하고 결합하여 전역 최적해를 물리적으로 보증함으로써 구분합니다.

3. Counterexample

• 단순히 "표를 채우는 법"이라 설명하는 것은 DPM 학습이 아닙니다. 왜 피보나치 수열의 단순 재귀가 데이터 $n=50$만 되어도 컴퓨터를 멈추게 하는지 그 중복 호출의 '기하급수적 물리 팽창'을 증명할 수 있어야 하며, 문제에 최적 부분 구조가 없음에도 억지로 DP를 적용했을 때 왜 틀린 답이 물리적으로 도출되는지(예: 최장 경로 문제 중 일부 케이스) 분석하지 못한다면 DPM의 적용 한계를 놓친 것입니다.

4. Prerequisites

• Complexity Analysis & Big-O (Basic): 시간-공간 트레이드-오프 이해가 필수입니다. (04-01-04 CAB)
• Recursion & Divide-and-Conquer (Recommended): 재귀적 사고 기초 이해가 권장됩니다. (04-03-01 RDC)

5. Learning Map

1. The Overlap Trap: 똑같은 계산을 수만 번 반복하는 재귀의 물리적 낭비를 목격합니다.
2. The Memory Anchor: 계산 결과를 배열(Table)에 못 박아 두는 메모이제이션을 도입합니다.
3. Bottom-up Ascent: 기초(Base Case)부터 한 층씩 해답의 탑을 쌓아 올리는 물리 시퀀스를 익힙니다.
4. State Transition: 현재의 결과가 미래의 결과로 이어지는 지능형 점화식 설계를 완성합니다.

6. Learning Topics

Basic

Core: 메모이제이션과 중복 제거 (Memoization)

• Why to Learn: 한 번의 기억이 수백만 번의 연산을 아끼는 물리적 기적을 체험하기 위해서입니다.
• What to Learn:
  • Lookup Table: 계산 결과를 보관하는 물리적 메모리 보관소(배열/맵)
  • Recursive Mapping: 함수 인자값을 테이블의 인덱스로 사상하는 법
  • Speed-up Observation: 기억 전후의 물리적 실행 시간 격차 측정
• How to Learn:
  • 피보나치 함수를 재귀로 짜되, 호출될 때마다 로그를 찍어 중복 호출을 직접 눈으로 확인 실습
  • 이미 계산된 값이 테이블에 있으면 즉시 반환하는 '기억장치'를 코드에 삽입
• Implement: 메모이제이션이 적용된 팩토리얼 및 피보나치 수열 코드

Recommended

Core: 점화식 도출과 상향식 DP (Tabulation)

• Why to Learn: 재귀 오버헤드를 없애고 반복문으로 문제를 해결하여 물리적 안정성을 확보하기 위함입니다.
• What to Learn:
  • Tabulation: 작은 인덱스부터 테이블을 채워나가는 물리 순찰
  • Recurrence Relation: $DP[i] = f(DP[i-1], DP[i-2])$와 같은 수리 규칙 설계
  • Space Optimization: 이전 값 몇 개만 필요할 때 배열 전체가 아닌 몇 개의 변수로 줄이는 기법
• How to Learn:
  • '계단 오르기' 문제를 통해 1단계와 2단계 전의 상태가 어떻게 현재를 결정짓는지 점화식 유도 실습
  • $1$차원 DP에서 $n$개의 공간 대신 $2$개의 공간만 써서 메모리 효율을 높이는 물리적 리팩토링
• Implement: 반복문을 사용하여 공간 복잡도를 최적화한 DP 알고리즘

Practical

Core: 2차원 DP와 최적 경로 탐색 (Multi-dimensional DP)

• Why to Learn: 변수가 두 개 이상 얽힌 현실의 복잡한 최적화 문제를 해결하기 위해서입니다.
• What to Learn:
  • Matrix States: $DP[i][j]$ 형태의 격자 공간 설계 물리학
  • Knapsack Algorithm: 무게 제한과 가치 사이에서 최적의 조합을 고르는 선택 모델
  • LCS (Longest Common Subsequence): 두 문자열 간의 유사성을 격자 탐색으로 찾아내는 법
• How to Learn:
  • 배낭 문제의 테이블을 손으로 직접 채워보며, 특정 물건을 '넣었을 때'와 '안 넣었을 때'의 물리적 분기 분석 실습
  • 2차원 공간에서의 최소 비용 경로 찾기를 통해 DP가 어떻게 모든 경로를 함축하는지 연구
• Implement: 0/1 Knapsack 문제를 해결하는 2차원 DP 테이블 엔진

Advanced

Core: 비트마스킹과 트리 DP (Specialized DP)

• Why to Learn: 상태의 수가 너무 많거나 구조가 비선형적일 때 물리적 해결 불가능을 해결 가능으로 바꾸기 위함입니다.
• What to Learn:
  • Bitmask DP: 방문 상태나 선택 여부를 비트(0, 1)로 표현하여 메모리 효율을 극대화하는 기법
  • DP on Trees: 부모 노드의 결과가 자식들의 결과합으로 결정되는 위상적 DP 물리학
  • Coordinate Compression in DP: 좌표의 범위는 크지만 개수가 적을 때 주소를 압축하는 기술
• How to Learn:
  • 외판원 문제(TSP)를 비트마스킹을 이용해 지수 시간을 다소 경감시키는 물리 레이아웃 설계 실습
  • 트리의 독립 집합(Independent Set) 크기를 구하며 재귀와 DP가 나무 구조에서 맺는 관계 분석
• Implement: 비트 연산자를 활용하여 방문 상태를 관리하는 고도화된 DP 최적화

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 등)에 저장하여 처리 속도를 높이는 아키텍처를 제안할 수 있는 가?