[프로그래머스] [Java] 피보나치 수

문제 설명

https://school.programmers.co.kr/learn/courses/30/lessons/12945?language=java

프로그래머스

2 이상의 n이 입력되었을 때, n번째 피보나치 수를 1234567으로 나눈 나머지를 리턴하는 함수, solution을 완성해 주세요.

첫번째 시도 : 재귀함수

class Solution {
    public int solution(int n) {
        int answer = fibo(n);
        return answer % 1234567;
    }
    
    public int fibo(int n) {
        if((n == 0) || (n == 1)) {
            return n;
        }
        else {
            return fibo(n-2)+fibo(n-1);
        }
    }
}

재귀 알고리즘으로 구현하면, 불필요하게 같은 값을 다시 계산하게 되어 계산 속도가 엄청 느리다는 단점이 있다.
이를 위해 한 번 계산한 값을 저장해 두고 재계산하지 않는 메모이제이션 기법을 사용하여 구현해야 한다.

최종 구현 : 메모이제이션(Memoization)

메모이제이션 기법은 컴퓨터 프로그램이 동일한 계산을 반복적으로 해야 할 때, 이전에 계산한 값을 메모리에 저장하여 중복적인 계산을 제거하여 전체적인 실행 속도를 빠르게 해주는 기법으로 동적 계획법(DP : Dynamic Programming)의 핵심이 되는 기술이다.

import java.util.*;
class Solution {
	// n이 100000까지 가능
    static int[] memo = new int[100001];
    
    public int solution(int n) {
        Arrays.fill(memo, -1); // -1로 미리 초기화
        memo[0] = 0;
        memo[1] = 1;
        return fibo(n);
    }
    
    public int fibo(int n) {
        if (memo[n] != -1) {
            return memo[n];
        }
        else {
            memo[n] = (fibo(n-1) + fibo(n-2)) % 1234567;
            return memo[n];
        }
    }
}

Java의 int는 약 ±21억(2^31-1) 까지만 표현 가능한데, 

피보나치 수열은 매우 빨리 커지기 때문에, fibo(100_000) 같은 값은 int 범위를 초과한다.

따라서 fibo 함수에서 미리 나머지 연산을 해주지 않으면 int 범위를 초과하게 된다.