[Algorithm] 동적 계획법 (Dynamic Programming)

동적 계획법이란?

- 복잡한 문제를 간단한 여러 개의 문제로 나누어 푸는 방법이다.

- 각 하위 문제를 해결 & 계산한 뒤 저장한다.

- 후에 같은 문제가 나왔을 때 계산하지 않고 저장한 값을 사용한다.

- 대표적인 예로 피보나치 수열을 구할 때 사용한다.

 

 

예) 피보나치 수열

- 첫째 및 둘째 항이 1이며, 그 뒤의 모든 항은 바로 앞 두 항의 합인 수열이다.

 

피보나치 수열을 구하는 함수를 fib()라고 정의하고,

피보나치의 다섯번째 항을 구한다고 하면, 계산은 다음과 같다.

값이 계속해서 중복되어 계산되는 것을 볼 수 있다.

 

하위 값을 계산하면서 미리 저장해놓으면 fib(5)는 앞의 두 값만 더하면 구할 수 있다.