최적화 문제 (optimization problem)
-
문제를 해결하는 최적의 답(optimal solution)을 찾아야 하는 문제
-
최적해는 하나 이상일 수 있다
-
maximum 또는 minimum [value] 를 가지는 {solution} 을 찾는 문제들이 주를 이룬다
- ex1) 가장 빨리 도착하는 {경로} 의 [소요 시간] 은?
- ex2) {언제 주식을 사고 팔 때} 가장 [수익] 이 높은가?
DP (Dynamic Programming)
-
최적화 문제를 해결하는 전략 중 하나
-
subproblem(s)의 optimal solution(s)을 활용해서, problem의 optimal solution을 찾는 방식
-
겹치는(overlapping) subproblems 은 1번만 계산하고, 그 결과를 저장한 뒤, 재사용한다
DP 의 2가지 접근 방식
[ Top-Down approach ]
- 구조
recursive
- subproblem 결과 저장
memoization (function call 의 결과를 저장하는 것)
- 언제 선호되는가?
subproblems의 일부만 계산해도 최종 optimal solution을 구할 수 있을 때
[ Bottom-Up approach ]
- 구조
iterative
- subproblem 결과 저장
tabulation (subproblem의 결과부터 테이블에 차근차근 채워넣는 것)
- 언제 선호되는가?
모든 subproblems을 계산해야 최종 optimal solution을 구할 수 있을 때
DP 를 사용한 알고리즘 설계 순서
- 주어진 문제의 최적해가 구조적으로 어떤 특징을 가지는지 분석한다
- 재귀적인 형태로 최적해의 value를 정의한다
- (주로) Bottom-Up 방식으로 최적해의 value를 구한다
(4.) 지금까지 계산된 정보를 바탕으로 최적해를 구한다
