포스팅 작성을 위한 학습 및 자료 정리 중..

아래는 위키피디아에 나와있는 Dynamic Programming 정의 중 일부를 발췌한 것입니다.

Dynamic Programming refers to simplifying a complicated problem by breaking it down into simpler sub-problems in a recursive manner.

차례

- Dynamic Programming

Dynamic Programming

Dynamic Programming은 최적화와 연관이 있어, 'Dynamic Optimization'으로 불리기도 합니다. 그러면, Dynamic Programming이 도대체 성능과 어떠한 연관이 있는 것일까요? Dynamic Programming 알고리즘은 복잡해 보이는 문제를 하위의 작은 문제들로 쪼개고, 하위 문제들의 결과를 별도의 저장공간에 저장을 합니다. 이렇게 함으로써, 동일한 하위 문제가 나왔을 때 중복해서 계산을 할 필요가 없도록 합니다.

큰 문제를 작은 단위로 나누어 해결하는 방법은 분할정복 방식(Divide-conquer)과 유사합니다. Dynamic Programming의 문제해결 방법이 Divide-conquer 방식과 다른 점은, 하위 문제가 중복해서 발생하게 되면 중복된 문제는 한 번만 연산을 하고 이후 같은 문제를 마주쳤을때 기억하고 있던 결괏값을 가지고 와 처리한다는 것입니다.

Dynamic Programming refers to simplifying a complicated problem by breaking it down into simpler sub-problems in a recursive manner.

dynamic programming approach may be applied to the problem only if the problem has certain restrictions or prerequisites. And after that dynamic programming extends divide and conquer approach with memoization or tabulation technique.

Dynamic Programming Prerequisites/Restrictions As we’ve just discovered there are two key attributes that divide and conquer problem must have in order for dynamic programming to be applicable:

Optimal substructure — optimal solution can be constructed from optimal solutions of its subproblems Overlapping sub-problems — problem can be broken down into subproblems which are reused several times or a recursive algorithm for the problem solves the same subproblem over and over rather than always generating new subproblems

Resources

• (Less Repetition, More Dynamic Programming)[https://medium.com/basecs/less-repetition-more-dynamic-programming-43d29830a630]
• (Dynamic Programming vs Divide-and-Conquer)[https://itnext.io/dynamic-programming-vs-divide-and-conquer-2fea680becbe]