[Java] 피보나치 나머지

1. 문제 설명

피보나치 수열이란 0,1부터 시작해 이전의 값을 더해 값을 만들어나가는 수열
N이 주어졌을 때, 피보나치 수열을 N까지 구해 N번째 피보나치수의 마지막 8자리
숫자를 정수형태로 출력하는 프로그램을 작성

입력형식

첫 줄에는 테스트케이스의 수 T가 1이상 10만 이하의 자연수로 주어진다.

각 테스트케이스의 입력은 한 줄로 구성되며, 1이상 100만 이하의 자연수 N	이 공백없이 주어진다.

출력형식

각 테스트케이스별로 한 줄에 정답을 출력한다. 
피보나치 수열의 N번째 숫자를 공백없이 정수형태로 출력한다.  단, 숫자 가장 앞의 0들은 생략한다. 
단, 피보나치 수열의 0번째 숫자는 0이고, 1, 2번째 숫자는 1이다

2. 알고리즘 접근

입력형식을 보면 N이 최대 100만인 것을 알 수 있다
이를 실제로 피보나치를 계산하면 엄청 큰 값이 나올 것이다.
그러나, 이 문제는 주어진 N에 대해 N번째 피보나치 수열에 대해 마지막 8자리 숫자까지
구하면 되는 문제이다
마지막 몇자리 = % (나머지연산)을 이용해서 도출하자

파보나치를 구하는 방법은
f(0) = 0
f(1) = 1
f(n) = f(n-1) + f(n-2)로 정의 할 수 있다.
재귀함수로 푸는 방법이 일반적이지만, 배열을 이용해서 풀어보겠다

정적 데이터 캐싱

피보나치수열 같이 이미 사전적으로 정의된 수열은 언제 어디서나 변하지 않는다

• 한 프로그램 내에서 수열의 값을 사용할 때마다 새롭게 계산할 필요가 없다
• 필요한 시점 전에 한번 계산해두면 계속해서 새롭게 사용할 수 있다

f(0) = 0, f(1) = 1
f(2) = f(0) + f(1) = 1
f(3) = f(2) + f(1) = 1 +1 = 2
f(4) = f(3) + f(2) -> 2 + 1 = 3
f(5) = f(4) + f(3) -> 3 + 2 = 5
이런 식으로 피보나치 수열을 전개하는데 여기서 
f(6)를 구한다고 했을 때 f(0)부터 다시 계산이 아닌 계산한 값 f(5)를 캐싱하여 재 사용하는것

3. 알고리즘 풀이

import java.io.BufferedWriter;
import java.io.IOException;
import java.io.OutputStreamWriter;
import java.util.Scanner;

public class Q3D {
    public static final Scanner sc = new Scanner(System.in);
    public static final BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

    // 정적 데이터 캐싱
    public static final int MAX_N = 1000000 + 1;
    public static int[] FIBONACCI_TABLE;

    public static int[] makeFibonacciTable(int n){
        int[]fib = new int[n + 1];
        fib[0] = 0;
        fib[1] = 1;
        // 배열을 통해 피보나치 구하기
        for(int i = 2; i <= n; i++){
            fib[i] = (fib[i - 1] + fib[i - 2]) % 100000000;
        }
        return fib;
    }

    // 정적 데이터 캐싱을 이용해 값 도출
    public static int getFibo(int n){
        int answer = FIBONACCI_TABLE[n];
        return answer;
    }

    public static void main(String[] args) throws IOException {
        //가능한 모든 범위에 대한 피보나치 수열의 값을 계산해두자
        FIBONACCI_TABLE = makeFibonacciTable(MAX_N); // O(MAX_N) => 100만번 수행 O(N)

        // 테스트케이스 생성
        int caseSize = sc.nextInt();
        for(int i = 0; i < caseSize; i++){   // O(caseSize) + O(N)의 시간복잡도를 결국 가지게 됨
            int n = sc.nextInt();

            int answer = getFibo(n);
            bw.write(String.valueOf(answer) + "\n");
        }
        //불필요한 배열은 가능하면 할당 해제해주는 버릇을 들이자.
        FIBONACCI_TABLE = null;

        bw.flush();
        bw.close();
    }
}

정적 데이터 캐싱을 하지 않고 testcase 안에서 피보나치 수열을 구하는코드라면
O(tc * n)의 시간복잡도를 가졌을 것이지만
이렇게 정적 데이터 캐싱을 거치면 이렇게 효율을 올릴 수 있다!!
잘 활용할 수 있게 여러 문제를 풀어보자