알고리즘
DP
다른 이름: Dynamic Programming , 동적 계획법 , 다이나믹 프로그래밍
정의
Dynamic Programming. 동적 계획법. 중복 부분 문제를 메모이제이션(Top-Down) 또는 테이블(Bottom-Up)로 저장해 재사용. O(2^n) → O(n^2) 최적화. 피보나치, LCS, LIS, 배낭 문제. "최대/최소", "경우의 수" 키워드
상세 설명
기술 스펙
- 메모이제이션 (Top-Down): 재귀 + 캐시 (Python @lru_cache)
- 테이블 (Bottom-Up): 반복문 + 배열
- 시간복잡도: O(상태 개수 × 전이 비용)
- 공간복잡도: O(상태 개수), 최적화 시 O(1)~O(n)
- 최적 부분 구조: 큰 문제의 최적해 = 작은 문제의 최적해 조합
- 중복 부분 문제: 같은 계산 반복
실무 활용
- 피보나치: F(n) = F(n-1) + F(n-2)
- LCS (Longest Common Subsequence): 문자열 유사도
- LIS (Longest Increasing Subsequence): 증가 부분 수열
- 배낭 문제: 무게 제한 내 최대 가치
- 백준: 1463 (1로 만들기), 9251 (LCS)
장점
- 극적 최적화: O(2^n) → O(n^2) 또는 O(n)
- 정확한 답: 완전 탐색 대비 빠르고 정확
- 다양한 응용: 경로, 문자열, 조합 최적화
- 증명 가능: 수학적 귀납법
단점 및 제약
- 어려운 상태 정의: 문제마다 DP 테이블 설계 필요
- 디버깅 어려움: 테이블 초기화 실수
- 공간 복잡도: 큰 테이블 메모리 부담
- 그리디와 혼동: 최적 부분 구조 여부 판단
호환성
C++, Python, Java 모두. @lru_cache (Python), vector (C++)
표준 정보
표준화 기구: Richard Bellman (1950s), 알고리즘 교과서 표준
출시 연도: 1953년