메모이제이션

[C] 피보나치 수열과 메모이제이션

피보나치 수열은 수학에서 첫째 및 둘째 항이 1이며 그 뒤의 모든 항은 바로 앞 두 항의 합인 수열이다. 점화식은 Fn = Fn-1 + Fn-2으로 정리된다. 재귀 함수를 이용한 풀이 #include long long fibo(int n); int main(){ printf("%lld", fibo(10)); return 0; } long long fibo(int n){ if (n < 2) return n; return fibo(n-1) + fibo(n-2); } 당장 fibo(100)만 넣어보면. 프로그램이 계산하다가 뻗어버리는 모습을 볼 수 있다. 불필요한 호출이 일어나서 프로그램이 느려지는건데 간단히 fibo(10) 을 계산하려면 fibo(9), fibo(8) 이 호출되고 fibo(9)가 다시 fib..