피보나치 수열

• 피보나치 수열에 대해선 개발을 해봤다면 한번 정도 들어보기는 했을 것이다.

2 이상의 n이 입력되었을 때, n번째 피보나치 수를 1234567으로 나눈 나머지를 리턴하는 함수, solution을 완성해 주세요. n은 2 이상 100,000 이하인 자연수입니다.

• 얼핏보면 간단해 보이나, 입력이 100,000 이하라는 것이 결국에 이 문제의 관건이 될거라고 생각했다.
• 피보나치 수열은 빅오 표기법으로 O(2^n)이다. 하여간 숫자 커지면 별로 안좋다
• 일단 첫번째로 간단하게 짠 코드이다.

#include <string>
#include <vector>

using namespace std;

int solution(int n) {
    int answer = 0;
    vector<int> fibonacci(n, 0);


    
    if (n > 2)
    {
        fibonacci[0] = 0;
        fibonacci[1] = 1;
        for (int i = 2; i <= n; ++i)
        {
            fibonacci[i] = fibonacci[i - 2] + fibonacci[i - 1];
        }
        answer = fibonacci[n] % 1234567;
    }
    else
    {
        answer = n;
    }

    
    return answer;
}

• 정말 의식의 흐름대로 정직하게만 짠 코드이고, 나머지 연산의 특성에 대해 알지 못했기 때문에 오버플로우가 날 수 밖에 없었다.

(a + b) % m = ((a % m) + (b % m)) % m

• 이러한 나머지 연산의 특징을 알게되어 다시 코드에 적용했다.

#include <string>
#include <vector>

using namespace std;

int solution(int n) {
       int answer = 0;
    int m = 1234567;
    vector<int> fibonacci(n + 1, 0);

    if (n > 2)
    {
        fibonacci[0] = 0;
        fibonacci[1] = 1;

        for (int i = 2; i <= n; ++i)
        {
            fibonacci[i] = (fibonacci[i - 2]  + fibonacci[i - 1]) % m;
        }

        answer = fibonacci[n];
    }
    else
    {
        answer = n;
    }

    
    return answer;
}

• fibonacci[i]에 이미 1234567의 나머지를 저장해둬도 괜찮은 특성을 이용해 오버플로우가 나지 않도록 저장하는 방식으로 문제 해결했다.