학습 일자 : 2023.
**DynamicProgramming (**동적 계획법)
어떠한 문제에 직면했을 때 부분적인 문제부터 해결하며 얻은 해답을 이용해 전체의 문제를 해결하는 상향식 접근 방식의 알고리즘.
분할 정복과는 반대의 개념임. 분할 정복이 top-down이라면, 동적 계획법은 botton-up 방법임.
동적 계획법 과정
- 문제를 부분으로 나눔
- 가장 작은 부분 문제부터 해를 구한 뒤 테이블에 저장
- 테이블에 저장되어 있는 부분 문제의 해답을 이용해 상위 부분 문제의 최적해를 구함.
[동적 계획법 예시]
| <피보나치 수열 >
❓피보나치 수열 : F(n+2) =F(n+1) + F(n)
- 문제를 부분으로 나누면 N번의 수열을 구하기 위해 정수의 가장 작은 수인 0과 1의 합부터 시작해야 함
- 가장 작은 수부터 점차적으로 큰 수의 합을 반환함
- 가장 마지막 합이 바로 가장 상위 부분의 문제가 됨. |
| --- |
| <피보나치 수열 프로그램>
👩💻 [소스 확인하기] |
최장 공통 부분 순서
p.520