[Algorithm] 해커랭크 - Recursion: Fibonacci Numbers

https://www.hackerrank.com/challenges/ctci-fibonacci-numbers/problem

피보나치 수열을 구하는 아주 간단한 예제다.

거의 시키는 대로 구현만 하면 되므로 아주 간단하게 짤 수 있지만 아래 코드의 시간복잡도를 계산해 보면 효율적이지 못한 코드다.

풀이시간 : 1분 50초

int fibonacci(int n) {
    if(n == 0)
    {
        return 0;
    }
    else if(n == 1)
    {
        return 1;
    }
    else
    {
        return fibonacci(n-1) + fibonacci(n-2);
    }
}

한번 함수가 호출 될 때 마다 2번씩 함수를 호출하므로 그림으로 그려보면 바이너리 트리 구조와 같은 형대가 되고, 노드의 갯수가 함수 호출 횟수와 같으므로 시간복잡도는 O(N^2)이다.

하지만 한번 계산한 값을 저장하는 방식으로 구현하면 더 좋은 효율을 낼 수 있고, 다음과 같이 구현할 수 있다.

int fibonacciN[30] = {};
int fibonacci(int n) {
    if(n == 0)
    {
        return 0;
    }
    else if(n == 1)
    {
        return 1;
    }
    else if(fibonacciN[n] != 0)
    {
        return fibonacciN[n];
    }
    else
    {
        return fibonacciN[n] = fibonacci(n-1) + fibonacci(n-2);
    }
}

시간복잡도는 O(N)으로 줄게 된다.

이와 같이 계산한 값을 저장하는 방법을 메모이제이션 이라고 한다.

하지만 만약 입력값 N이 엄청나게 큰 수라면?

도저히 배열에 저장할 엄두가 나지 않는다.

보통 N이 매우 큰 수인경우 그 피보나치 수를 특정 값 a로 나눈 값을 요구하는데, 이런 경우에는 피보나치 수의 성질을 이용해야 한다.

피보나치 수의 성질

 (출처 : 위키백과)

이 식은 피보나치 수열의 정의를 행렬 형태로 나타낸 것을 응용하면 얻을 수 있다.

행렬곱 함수를 구현해 n을 입력한다면 배열을 사용하지 않고도 구할 수 있다.