알고리즘

DP (Dynamic Programming)

중복되는 부분 문제를 메모이제이션 또는 타뷸레이션으로 저장해 재계산을 피하는 기법. 최적 부분 구조와 중복 부분 문제 속성이 필요하다.

핵심 포인트

• Top-down(재귀 + 메모): 자연스러운 구현, 스택 오버플로 주의
• Bottom-up(반복): 공간 최적화 유리, LCS·배낭·행렬 연쇄 곱셈 등
• 점화식 도출이 핵심 — 상태 정의 → 전이 관계 → 기저 조건
• 대표 문제: 피보나치, 최장 공통 부분 수열(LCS), 0/1 배낭