백준 1003 자바, 파이썬, C# - 피보나치 함수 (BOJ 1003 JAVA, Python, C#)

문제 : https://www.acmicpc.net/problem/1003

코드(자바) : https://github.com/NaHwaSa/BOJ_BaekjunOnlineJudge/blob/master/01000/BOJ_1003.java

코드(파이썬) : https://github.com/NaHwaSa/BOJ_BaekjunOnlineJudge/blob/master/01000/BOJ_1003.py

코드 (C#) : https://github.com/NaHwaSa/BOJ_BaekjunOnlineJudge/blob/master/01000/BOJ_1003.cs

 

 

  Memoization 개념에 대해 익힐 수 있는 아주 좋은 문제이다. 피보나치의 경우 문제에 제시된 기본적인 방식으로 짜게 되면 재귀적으로 호출되는 함수가 기하급수적으로 늘어난다. ->O(2^N)

 

  이 때, 이미 계산된 피보나치 수에 대해 Memoization을 통해 저장해두면 기하급수적으로 늘어나던 함수 호출이 엄청나게 줄어든다. -> O(N)

문제에 제시된 코드를 살짝 바꿔 Memoization을 적용시킨 코드는 다음과 같다.

int fibonacci(int n) {
    if (memoization[n] != -1)
        return memoization[n];
        
    if (n == 0) {
        printf("0");
        return 0;
    } else if (n == 1) {
        printf("1");
        return 1;
    } else {
        return memoization[n] = fibonacci(n‐1) + fibonacci(n‐2);
    }
}

그리고 위 함수 구조를 벗어나 DP로도 풀 수 있는데, 올려둔 코드는 모두 DP로 푼 경우이다. DP로 푼 경우도 O(N) 이므로 별다른 차이는 없다.

 

  사실 피보나치 최적화에는 하나가 더 있는데, 행렬을 이용해 계산하는 방식이다. 이 경우 위의 모든 경우보다 더 빠르게 계산을 할 수 있지만, 사실 너무 대회를 위한 알고리즘 같은 느낌이라 크게 알 필요는 없을 것 같다. 나중에 생각나면 따로 피보나치 최적화에 대해 써봐야겠다.