토픽 19 / 82

동적 프로그래밍 (Dynamic Programming)

큰 문제를 작은 부분 문제로 나누고 중복되는 부분 문제의 해를 저장(메모이제이션)하여 재사용함으로써 효율적으로 해결하는 알고리즘 설계 기법

목적: 중복 계산 제거, 최적화 문제, 효율적 해결

특징: 중복 부분 문제, 최적 부분 구조, 메모이제이션, Bottom-Up/Top-Down

조건

접근 방식

Top-Down vs Bottom-Up 상세 비교

메모이제이션(Memoization): 계산 결과를 저장하여 재사용, 딕셔너리/배열

단계: ① 부분 문제 정의 → ② 재귀 관계식(점화식) 도출 → ③ 기저 케이스 정의 → ④ 테이블 채우기 → ⑤ 최종 답 도출

시간 복잡도: 부분 문제 수 × 각 문제 해결 시간

공간 복잡도: O(n) ~ O(n²) - 테이블

장점: 중복 계산 제거, 최적해 보장, 효율적(지수→다항)

단점: 공간 사용 많음, 점화식 도출 어려움, 모든 문제 적용 불가

적용사례: 피보나치, 최장 공통 부분 수열(LCS), 배낭 문제, 최단 경로(Floyd-Warshall), 편집 거리

비교: DP(중복/메모이제이션/최적) vs 분할 정복(독립/재귀) vs 탐욕(지역/빠름/최적 보장 안함)

연관: 메모이제이션, 피보나치, LCS, 배낭 문제, 최적화