MIT - Introduction to Algorithms
- Lecture 19. Dynamic Programming I: Fibonacci, Shortest Paths
동적 프로그래밍 1: 피보나치, 최단 거리 Review
Copyright to MIT & Srini Devadas & Erik Demaine
https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-006-introduction-to-algorithms-fall-2011/lecture-notes/
code, data, note pdf : https://courses.csail.mit.edu/6.006/fall11/notes.shtml
한글 번역과 슬라이드를 보고싶은 분은 Edwith - 파이썬을 이용한 알고리즘의 이해 항목 강의를 참조하세요.
URL : https://www.edwith.org/introalgorithm/
DP(Dynamic Programming, 동적프로그래밍)이란?
동적 프로그래밍 줄여서 DP(Dynamic Programming)은 일반적이고 강력한 방법론으로 최단 경로 같은 최적화 문제에 유용하다일종의 완전 탐색이라고 생각할 수 있으며 careful brute force라는 표현을 사용하기도 한다.
보통 완전 탐색이라고 이야기하면 지수 분포를 생각하지만 영리한 방식으로 다항 시간으로 더 빠르게 수행이 가능하는 것이 가능하다.
일반적으로 Divide & Conquer 방식으로 생겨난 subproblems들을 recursion + re-use 방식 + memorization을 합쳐서 DP라고 이야기한다.
지금은 나오지 않지만 5 page DP = recursion + memorization + guessing의 과정이라고 재정의를 내린다.
오늘 전반적으로 memorization의 필요성에 대한 시간 복잡도의 관점에서 바라볼 것이다.
Dynamic Programming 어원
앞에서 최단 거리에서 음을 가지는 Cycle 그래프의 최단 거리를 찾기위해 사용했던 Bellman Ford Algorithm을 만든 사람 중 한명인 Richard E.Bellman(1920-1984)의 상사 였던 국방 장관과 국회의원들이 Research 관련된 단어를 병적으로 기피했기에 대안으로 만든 단어라는 내용이 정설입니다.
그렇기에 Memorized라는 dict를 넣어 한번 계산한 Fibonicci에 대해서는 저장해놓도록 하는 과정을 거쳤습니다.
이는 결과적으로 시간을 줄이게 하는 역할을 잘 수행했고 Polynomial Time complexity를 가지게 됩니다.
Bottom-up DP Algorithm
우리는 위에서 아래로 재귀를 통해 구할 수도 있지만 아래에서부터 차근히 쌓아올라가면서 결국 원하던 숫자의 피보나치 숫자를 찾아낼 수도 있습니다.
마치 n=5를 찾기 위해 위에서 했던 방식은
fib(5) = fib(4)+fib(3)
fib(4) = fib(3)+fib(2)
fib(3) = fib(2)+fib(1)
fib(2) = 1
까지 구하고 다시 재귀를 통해 위로 올라갔다면
Bottom-up DP는 memorization과 함께
f(1),f(2),fib(3) = fib(2)+fib(1), fib(4) = fib(3)+fib(2), fib(5) = fib(4)+fib(3)를 통해 답을 구해가는 것 입니다.
아마 우리는 이 방식에 익숙하겠지요
$O(n)$
같은 DP라는 것을 알 필요가 있습니다.
최단 거리를 찾고자 할 때 어떻게 해야할까요?
Guessing을 통해 전부 다 돌아봐서 가장 좋은 길을 선택하는 것으로 해결할 수 있지만 효율적으로 Guessing을 해야겠지요
앞에서 다뤘던 Bellman Ford Algorithm과 같은 효율적인 알고리즘을 통해 우리는 좀 더 빠른 시간 안에 재귀를 통해 답을 찾아낼 수 있습니다.
비순환형 그래프인 DAG의 경우에는 어떨까요 앞에서 배웠던 이 그래프의 시간복잡도는 $O(V+E)$로 찾아낼 수 있습니다.
순환형 그래프인 Bellman Ford Algorithm의 경우는 $O(VE)$입니다.
오늘 수업을 토대로 우리는 DP에 대해 다음과 같이 정의 할 수 있습니다.
DP = Divide & Conquer Subproblems Recursion
+ Memorization
+ Effectively Guessing
