[ 프로그래머스 ] 피보나치 수

문제

---

https://school.programmers.co.kr/learn/courses/30/lessons/12945

풀이

---

n번째 피보나치 수를 1234567으로 나눈 나머지를 리턴하는 함수를 작성하기 위해 먼저, 피보나치를 구현했다. 그런데 조건으로 n은 2 이상 100,000 이하인 자연수라는 조건이 붙어 있으므로, 일반적인 재귀로 풀게되면 제한 시간을 초과할 확률이 높다. 따라서 메모이제이션 (Memoization)을 활용, 피보나치를 구현하였다.

※ 메모이제이션(memoization) : 컴퓨터 프로그램이 동일한 계산을 반복해야 할 때, 이전에 계산한 값을 메모리에 저장함으로써 동일한 계산의 반복 수행을 제거하고 실행 속도를 빠르게 하는 기술

알고리즘에 따른 속도 차이

#include <string>
#include <vector>

using namespace std;

int Fibonacci(int n)
{
    if (n <= 1)
    {
        return n;
    }

    return (Fibonacci(n - 1) % 1234567 + Fibonacci(n - 2) % 1234567);
}

int fibonacci_iter(int n) 
{

    if (n <= 1)
    {
        return n;
    }

    else 
    {
        int result = 0;
        int iterA = 0, iterB = 1;

        for (int i = 2; i <= n; i++) 
        {
            result = iterA + iterB;
            iterA = iterB;
            iterB = result;

            result %= 1234567;
            iterA %= 1234567;
            iterB %= 1234567;

        } 
        return result;
    }

}

int solution(int n) 
{
    int answer = 0;

    answer = fibonacci_iter(n);

    /*answer %= 1234567;*/

    return answer;
}