#include <iostream>
using namespace std;
int fibo(int n) {
if (n <= 1)
return n;
else
return fibo(n - 1) + fibo(n - 2);
}
int main() {
int num;
cin >> num;
cout << fibo(num);
}
피보나치 수열은 0 1 1 2 3 5 8 13 ... 과 같이 바로 이전의 두 항을 더한 값이 다음 값으로 오게 된다.
처음에 코드를 짤 때에는 많이 생각하지 않고 위와 같이 짰다가 시간초과 오류가 났다.
이유를 찾아보아하니, 계산을 중복되이 하게 되어 위처럼 하게된다면 시간복잡도가 O(2^n)이 된다고 한다.
예를 들면 위에서 num에 값을 입력하면 곧 피보나치 수열에서 num번째 값을 뱉어내게 된다.
(이때 0은 0번째, 1은 1번째이다)
num=5일 때의 일부 과정을 살펴본다면
1) fibo(5) = fibo(4)+fibo(3)
1-1) fibo(4) = fibo(3)+fibo(2)
1-2) fibo(3) = fibo(2)+fibo(1)
1-1-1) fibo(3) = fibo(2)+fibo(1)
1-1-2) fibo(2) = fibo(1)+fibo(0)
1-2-1) fibo(2) = fibo(1)+fibo(0)
중복된 계산을 하게 되는 문제가 생긴다.
이는 곧 오버헤드(함수를 호출하기 위한 준비 시간)가 너무 커지게 된다.
그렇다면 계산한 값은 곧바로 저장해서 다시 연산하지 말고 불러와보자.
=>메모이제이션
이를 사용하게될 시, 시간복잡도가 O(N)이 된다.
약간의 공간을 할당함으로써 연산량이 어마어마하게 줄어들게 되는 것이다.
#include <iostream>
using namespace std;
int memo[20];
int fibo(int n) {
if (n <= 1)
return n;
else {
if (memo[n] == 0) // 계산한 적이 없어 값이 아무것도 저장되어있지 않다면
memo[n] = fibo(n - 1) + fibo(n - 2);
return memo[n];
}
}
int main() {
int num;
cin >> num;
cout << fibo(num);
return 0;
}