Dynamic Programming
굉장히 어려운 문제가 쉽게 풀리게 해준다.
어떨 때 사용할 수 있는지, 어떻게 동작하는지를 알기 위해 큰 틀을 보겠다.
기본적으로 재귀
재귀는 독립적으로 실행할 수 있어야 한다.
전체 문제가 있고 잘라서 자른 문제가 전체인 것처럼 동작한다.
머지소트는 왼쪽 배열이 오른쪽배열의 영향을 받지 않는다.
하지만 그래프와 같은 경우는 영향을 받을 수 밖에 없다
완전히 독립적으로 잘라서 재귀로 적용하기 힘들다.
독립적인 부분문제의 답으로 전체의 답을 만든다는 점에서
분할정복과 비슷하지만 재사용에서 다르다.
피보나치에서 F(n)의 값은 변하지 않는다.
F(6) = F(5) + F(4)
F(7) = F(6) + F(5)
여러 곳에서 쓰이지만 F(5)의 값은 같다.
By Recursion
정의대로 코드를 짰기 때문에 답이 맞는다.
문제는 느리다는 것.
F(n)은 F(n)에 비례한다.
E 1,1,2,2,4,4,8,8
F 1,1,2,3,5,8,13
G 1,1,2,4,8,16
피보나치의 크기를 정확히 모르지만 지수배로 늘어난다.
같은 값을 여러번 계산하기 때문에 낭비가 있다!
By Memoization
동일한 호출을 한 번만 하기 위해 외부 변수(배열)에 적어두자!
F(5)가 몇번사용되든간에 F(5)가 계산될때만 F(3)이 사용
F(3)은 F(4), F(5)가 계산될 떄 사용
모든 값은 한 번 계산, 두번 사용 = O(n)
Memoization은 재귀를 사용해서 Dynamic보다 느리지만
배열이 어떤 순서로 채워질지 모르는 상황에서 사용 가능하다.
배열이 채워지는 순서까지 안다면
재귀없이 더 빠른 코드를 짤 수 있다. => Dynamic Programming
피보나치의 동작을 그대로 수행하는 것처럼 보이지만
각 배열의 값이 잘 들어가있다는 가정하에 동작한다.
