1. Fibonacci Number
피보나치 수열은
f(0) = 0 이고 f(1) = 1 일 때, f(n) = f(n-1) + f(n-2) 를 따라가는 수열이다.
1.1 Recursion
재귀는 독립적으로 실행할 수 있어야 한다.
전체 문제가 있고 잘라서 자른 문제가 전체인 것처럼 동작한다.
머지소트는 왼쪽 배열이 오른쪽배열의 영향을 받지 않는다.
하지만 그래프와 같은 경우는 영향을 받을 수 밖에 없다
완전히 독립적으로 잘라서 재귀로 적용하기 힘들다.
독립적인 부분문제의 답으로 전체의 답을 만든다는 점에서 분할정복과 비슷하지만 재사용에서 다르다.
피보나치에서 F(n)의 값은 변하지 않는다.
F(6) = F(5) + F(4)
F(7) = F(6) + F(5)
여러 곳에서 쓰이지만 F(5)의 값은 같다.
이 경우 n이 커질수록 중복 호출되는 경우가 많아져서 시간 복잡도가 지수적으로 증가한다.
1.2 메모이제이션 (memoization)
계산 결과를 미리 저장해두고 계산한 적이 있다면 재귀 없이 리턴한다.
이렇게 하면 중복 호출될 일이 없다.
Memoization은 재귀를 사용해서 Dynamic보다 느리지만
배열이 어떤 순서로 채워질지 모르는 상황에서 사용 가능하다.
하지만 순서를 모르므로 걸리는 시간을 파악하지 못한다.
배열이 채워지는 순서까지 안다면
재귀없이 더 빠른 코드를 짤 수 있다. → Dynamic Programming
1.3 Dynamic Programming
재귀 없이 단순히 반복문으로 피보나치 수열을 구할 수 있다. (DP 배열에 이미 계산이 되어 있다고 확신)
피보나치의 동작을 그대로 수행하는 것처럼 보이지만 각 배열의 값이 잘 들어가있다는 가정하에 동작한다.
손으로 하는것이랑 가장 유사한 코드이다