Endless Motivation
피보나치 수열 with memoization 본문
#include
#include #include #include using namespace std; int arr[46] = { 0, }; int fibo(int n) { if (n == 1 || n == 2) { arr[n] = 1; return 1; } else if (arr[n] != 0) { return arr[n]; } else { arr[n] = fibo(n - 1) + fibo(n - 2); return arr[n]; } } int main(){ int n; cin >> n; cout << fibo(n) << endl; return 0; }
재귀형식으로 작성한 피보나치 수열은 약 O(2^n)을 갖는다.
재귀를 하면서 생성되는 fibo(n)의 값을 저장하여 사용한다면 O(n)으로 시간이 단축된다.
Comments