[프로그래머스 코딩테스트] 피보나치 수(Java)

  문제 설명

  피보나치 수는 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 이하인 자연수입니다.

 

  입출력 예

n	return
3	2
5	5

class Solution {
    pubilc int solution(int n) {
        int index = 0;
        if (n < 2) {
            index = 2;
        } else {
            index = n + 1;
        }
        int[] arr = new int[index];
        arr[0] = 0;
        arr[1] = 1;
        for (int i = 2; i <= n; i++) {
            arr[i] = (arr[i - 1] + arr[i - 2]) % 1234567;
        }            
        int answer = arr[n];
        return answer;
    }
}

  피보나치 수는 재귀함수의 대표적인 예입니다. 그러나 이 문제를 재귀함수만으로 풀고자 한다면 시간초과로 통과할 수 없습니다. 이럴 때 사용할 수 있는 것이 동적 프로그래밍(Dynamic Programming, DP)입니다. 이는 중복되는 연산을 재활용하는 특징이 있습니다. 이 코드는 동적 프로그래밍 중, 타뷸레이션(Tabulation)을 활용한 것입니다. 이는 같은 동적 프로그래밍 알고리즘 중 하나인 메모이제이션(Memoization)과 달리 재귀 호출을 사용하지 않습니다. 코드도 보다 직관적인 편입니다.

  타뷸레이션은 배열을 이용하므로 배열의 크기를 지정해주어야 합니다. 만약 n이 2보다 작다면 index의 크기는 2이고, 그렇지 않다면 n + 1로 할당합니다. 이렇게 구한 index를 arr의 배열 크기로 지정합니다.

  arr[0]과 arr[1]은 각각 0과 1로 고정입니다. for문이 n만큼 순회합니다. 배열의 0번과 1번은 값이 정해졌으므로 i는 2부터 시작합니다. arr[i] 는 arr[i - 1]과  arr[i - 2]를 더한 값입니다. 문제에서 1234567로 나눈 나머지를 반환하라고 했으므로, 제시한 대로 했습니다. 이는 수열이 매우 큰 값이 될 수도 있기 때문에 연산량을 줄이기 위한 용도로 생각됩니다.

class Solution {
    static int fi(int a) {
        if (a <= 1) {
            return a;
        } else {
            return fi(a - 1) + fi(a - 2);
        }
    }
    public int solution(int n) {
        int answer = fi(n);
        return answer % 1234567;
    }
}

  재귀함수만을 이용한 풀이입니다. 코드는 간단하지만 만약 n이 커질 경우에는 같은 계산을 반복하는 탓에 비효율적이므로, 앞선 동적 프로그래밍을 이용하는 것이 관건입니다.

왼쪽 타뷸레이션, 오른쪽 재귀함수 풀이