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

🔗 문제 링크

https://programmers.co.kr/learn/courses/30/lessons/12945

👨🏻‍💻 처음 작성한 코드 (Recursive하게 구현)

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

Recursive하게 구현을 하니 메모리 용량 초과때문인지 런타임에러가 나왔다.
그리하여 중복된 연산을 여러번하는 낭비를 줄이기 위해 동적 계획법(Dynamic programming)으로 코딩을 해보았다.

👨🏻‍💻 수정한 코드 (Dynamic programming)

class Solution {
    public int solution(int n) {
        int answer = fibo(n);
        System.out.println(answer);
        return answer;
    }
    
    public int fibo(int n) {
        int[] cache = new int[n+1];
        
        cache[0] = 0;
        cache[1] = 1;
        
        for (int i=2; i<= n; i++){
            // 99999와 같이 큰 수를 넣을 경우 int와 long타입의 범위를 넘어
            // 값들을 문제 조건에 맞게 1234567로 나눈 나머지로 저장
            cache[i] = (cache[i-1] + cache[i-2]) % 1234567;
        }
        
        return cache[n] % 1234567;
    }
}

📝 결론

피보나치는 가장 기본중의 기본인 코드이지만 아무런 생각 없이 Recursive하게 된다면 중복된 연산을 반복해서 해야하는 시간 낭비와 계속 함수 내부에서 함수를 호출하여 메모리를 많이 사용해야하는 메모리 낭비가 발생하게 된다. 이러한 경우는 Dynamic programming을 하여 중복연산과 불필요한 메모리 사용을 줄이도록 코딩해야한다.

또한 "n은 1이상, 100000이하인 자연수입니다"와 같은 문제의 조건을 잘 읽어 문제의 연산을 하며 자료형의 범위를 넘지 않는지도 생각하며 문제를 풀어야겠다.