[프로그래머스] Lv.2 피보나치 수.java

피보나치 수.java

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

Recursive 방식은 피보나치 수열의 정의 그대로를 코드로 구현한 방법, 이전 값들을 계속해서 재귀적으로 호출하면서 계산하기 때문에 연산량이 많아져서, 큰 수에 대해서는 시간이 많이 소요될 수 있다.
Dynamic programming 방식은 중복 계산을 피하는 방법, 전에 계산한 값을 메모리에 저장해두고, 다음 계산 시에는 해당 값을 바로 가져와서 사용한다. 이전 계산 값들을 참조하면서 새로운 계산 값을 구하는 방식으로, 계산량이 많은 Recursive 방식에 비해 빠른 속도로 값을 계산할 수 있다.

출처: 프로그래머스 코딩 테스트 연습, https://school.programmers.co.kr/learn/challenges