다이나믹 프로그래밍

다이나믹 프로그래밍은

1) 큰 문제를 작은 문제로 나눌 수 있고

2) 작은 문제의 답이 큰 문제에서도 동일할 때

하나의 문제는 한 번만 풀도록 Memoization 하는 알고리즘이다.

 

가령 피보나치 수열을 구할 때

https://youtu.be/FmXZG7D8nS4

fib(15)를 구하려면 fib(14) + fib(13)을 구해야 하는데,

위 그림처럼 동일한 계산을 매우 여러 번 해야 함을 알 수 있다.

 

따라서 한 번 계산한 값을 배열에 memo 해 두고,

배열에 memo 해 둔 값이 있다면 그것을 반환하고

값이 없다면 (처음 계산하는 것이므로) 계산하고 memo 하면 된다.

 

https://youtu.be/FmXZG7D8nS4

 

출처는 사진 아래 링크