[TIL] 241218

프로그래머스-피보나치 수

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

시간초과
재귀함수로 구현해서 시간복잡도가 O(2^n)로 증가함

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

DP 적용
배열에 값을 저장해 중복 계산을 줄임
시간복잡도 O(n)
분배법칙을 이용해서 미리 수를 나눠 저장하여 숫자가 커지지 않도록 함

class Solution {
    public int solution(int n) {
        int a = 0, b = 1, temp;

        for (int i = 2; i <= n; i++) {
            temp = (a + b) % 1234567;
            a = b;
            b = temp;
        }

        return b;
    }
}

배열을 선언하지 않고 변수로만 계산할 수도 있다