반응형
memorization
-
알고리즘: 다이나믹 프로그래밍(dynamic programming) 공부하기! (Memorization, Tabulation, 공간최적화)알고리즘 2020. 7. 10. 19:34
다이나믹 프로그래밍(Dynamic Programming)이란? 다이나믹 프로그래밍은 부분 문제들의 답을 중복되지 않게 최적의 방법으로 구하고 이를 통해 기존의 답을 구하는 방식이다. 정리하자면 어떤 한 문제가 최적부분구조와 중복되는 부분 문제가 있을 때 동적 프로그래밍을 사용하면 효율적이다. (두 조건을 만족하지 않아도 다이나믹 프로그래밍을 할 수 있다.) → 최적부분구조(Optimal substructure) 어떤 문제가 최적 부분구조로 이루어져 있을 때, 부분 문제들의 최적의 답을 구해서 기존 문제의 최적의 답을 구할 수 있다. 예를 들면, 최단경로를 찾는 문제가 있다. → 중복되는 부분 문제(Overlapping subproblems) 주로 재귀(recursion)을 사용하는 경우, 중복되는 문제들..