프로그래머스(JAVA) - level2(피보나치 수)

 

문제정리

피보나치 수는 1 이상의 n에 대하여 F(n) = F(n-1) + F(n-2) 가 적용되는 수
2 이상의 n이 입력되었을 때, n번째 피보나치 수를 1234567으로 나눈 나머지를 리턴한 함수

 

이라는데 문제를 이해하는데 시간이 좀 걸림..;; 각각 2이상의 수에 나눠서 나머지를 구하라는 건지..

작성한 코드

class Solution {
    public int solution(int n) {
        int[] answer = new int[n + 1]; 

        for (int i = 0; i <= n; i++) {
            if(i == 0){
                answer[i] = 0;
            }else if(i == 1){
                answer[i] = 1;
            }else {
                int sum = answer[i - 1] + answer[i -2];
                answer[i] = sum % 1234567;
            }
        }

        return answer[n];
    }
}

 

문제를 이해하고 나서는 해결하는 데에는 오래걸리지 않음!

시간은

+ 추가🧐

피보나치 수열은 대표적인 동적 프로그래밍의 예라고 한다.
동적 프로그래밍(DP)은 큰 문제를 작은 문제로 나누어 푸는 알고리즘 설계 기법이다. 한 번 계산한 작은 문제의 답을 저장(메모이제이션, Memoization)해서, 나중에 동일한 문제가 다시 나타났을 때 계산을 반복하지 않고 저장된 값을 활용해 효율성을 높이는 것이 핵심이라고 한다.

위 코드를 보았을 대 각 숫자 F(1)부터 F(n)까지 한 번씩만 계산하기 때문제 중복 계산이 제거되는 것을 확인할 수 있다. (시간 복잡도가 줄어든다.)
반복문을 사용하기 때문에 함수 호출 스택을 사용하지 않아 메모리 효율이 더 좋다고 한다.