피보나치 수열 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)으로 시간이 단축된다.