□ 동적 프로그래밍(Dynamic Programming)

동적 프로그래밍(Dynamic Programming)

하나의 대문제(Univ_Problem)는

여러개의 소문제(Sub_Problems)에 대한 결과값을 통해 해결한다.

이 때,

일부 소문제의 결과값을 도출하기 위해

다른 소문제의 결과값을 필요로 하는 경우가 생긴다.

(=중복되는 계산을 요구)

따라서, 하나의 소문제를 해결할 때마다, 결과값을 테이블에 저장하여,

중복되는 계산을 요구하는 경우, 테이블에서 해당 소문제의 결과값을 

divide and conquer 기법에서는

분할 객체간에는 독립성을 가지기 때문에, 필요한 경우 합치기만 하면 된다.

dynamic programming 에서는

분할 객체(소문제)간 중복되는 계산을 요구하기도 한다.

피보나치의 경우

"Fn = F(n-1) + F(n-2), (n>=2)" 의 계산에

분할 정복 방법을 적용한다면,

F(10) = F(9) + F(8) 인데

F(9)를 구하기 위해서는 다시 F(8)을 구해야 하기 때문에

중복되는 계한을 요구한다.

동적 프로그래밍에서는

소문제의 해 [ F(8) ]를 표에 저장해 놓으므로,

F(9)의 계산에 필요한 F(8)의 값을 계산후 테이블에 저장하여,

F(10)의 계산에 필요한 F(8)의 값을 요구할 때, 테이블을 참조하여

중복된 계산을 피한다.

[출처] 동적 프로그래밍(Dynamic Programming)이란?|작성자 moonv11