재귀(recursive)

-> 너무 느리고, 비효율적으로 계산을 해서 시간초과가 남

#include <iostream>
#include <cstdio>
#include <algorithm>

using namespace std;

// 너무 느린 코드!!!

int fibo (int num) {
    int result;

    if (num < 2) {
        return num;
    } else {
        return (fibo(num-1) + fibo(num-2));
    }
    return result;
}

int main() {
    int n;
    scanf("%d", &n);
    printf("%d", fibo(n));
}

memoization

#include <iostream>
#include <vector>

using namespace std;

vector<long long> F;

long long fibo (int num) {
    
    F.push_back(0);
    F.push_back(1);

    if (num < 2) {
        return num;
    } else {
        for (int i=2;i<=num;i++) {
            F.push_back(F[i-1]+F[i-2]);
            //memoization : F[i-1],F[i-2]를 다시 계산하지 않고 저장된 값을 꺼내서 씀

        }
    }
    return F[num];
}

int main() {
    int n;
    cin >> n;
    cout << fibo(n) << endl;
}

• 왜 오류가 났냐면 최대 input 값이 90인데, 결과값은 2880067194370816120로 엄청 크다
• 근데 내가 결과값이 나오는 함수 fibo를 int형으로 하면 그 수를 못 담기 때문에 long long fibo(int num)으로 바꿔주어야 한다.
• 물론 vector도 vector<long long> F;을 써야한다!
• 수가 너무 컸을 때 시간초과가 나거나 틀렸다면 'long long'을 쓰기