[Lv.2] 피보나치 수

문제설명 피보나치 수는 F(0) = 0, F(1) = 1일 때, 1 이상의 n에 대하여 F(n) = F(n-1) + F(n-2) 가 적용되는 수 입니다. 예를들어  ● F(2) = F(0) + F(1) = 0 + 1 = 1  ● F(3) = F(1) + F(2) = 1 + 1 = 2  ● F(4) = F(2) + F(3) = 1 + 2 = 3  ● F(5) = F(3) + F(4) = 2 + 3 = 5 와 같이 이어집니다. 2 이상의 n이 입력되었을 때, n번째 피보나치 수를 1234567으로 나눈 나머지를 리턴하는 함수, solution을 완성해 주세요. 제한사항    ● n 은 2이상 100,000 이하의 자연수입니다.

 

1. 재귀함수 이용 (Overflow 발생)

class Lv2_Fibonacci
{
    static void Main(string[] args)
    {
        Console.WriteLine($"{Solution(10000)}");
    }

    static int Solution(int n)
    {
        int answer = 0;

        answer = Fibonacci(n - 1) + Fibonacci(n - 2);

        return answer;
    }

    static int Fibonacci(int n) // 재귀함수 값이 커질 수록 Overflow
    {
        switch (n)
        {
            case 0:
                return 0;

            case 1:
                return 1;
        }

        n = Fibonacci(n - 1) + Fibonacci(n - 2);

        return n;
    }
}​

이렇게 작성하니 n의 값이 커질 수록 Overflow가 발생, for문 이용해서 반복하기로 결정

 

2. for문 이용

    class Lv2_Fibonacci
    {
        static void Main(string[] args)
        {
            Console.WriteLine($"{Solution(10000)}");
        }

        static int Solution(int n)
        {
            int[] arr = new int[n + 1];
            arr[0] = 0;
            arr[1] = 1;
            int answer = 0;

            for (int i = 2; i <= n; i++)
            {
                arr[i] = ((arr[i - 1] + arr[i - 2]) % 1234567);
            }
            answer = arr[n];

            return answer;
        }
    }

재귀 함수보다 빨랐지만 n의 값이 커질 수록 int의 범위를 넘어가 음수로 표현되어 for문 내에서 1,234,567을 미리 나눠줬다.

[int의 범위는 -2,147,483,648 ~ 2,147,483,647 까지]

 

피보나치 수는 매우 빠르게 커지므로 int, long 으로 표현하기 어려워 1,234,567로 나눈 나머지를 계산하면 숫자가 일정 범위 내로 유지되어 오버플로우를 방지 할 수 있다.

 

※ 피보나치 수는 주기성(Pisano Period)을 가지는데 이는, 피보나치 수열을 m으로 나눈 나머지가 반복적으로 나타나는 패턴의 길이이다.