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

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

프로그래머스

---

[ 오답 노트 ]

 

❌ 기존 오답 코드

결과는 맞게 나오지만 시간 초과가 났다

class Solution {
    public int dfs(int d) {
        if(d == 0) {
            return 0;
        }else if(d == 1) {
            return 1;
        }
        
        return dfs(d-1) + dfs(d-2);
    }
    
    public int solution(int n) {
        int answer = 0;
        // F(3) = F(1) + F(2) = 1 + F(0) + F(1) = 1 + 0 + 1 = 2
        // F(n) = F(n-1) + F(n-2) 
        answer = dfs(n) % 1234567;
        
        return answer;
    }
    
}

 

📌 기존 코드의 문제점

1. 시간 복잡도 문제

• 재귀 호출 방식으로 작성된 dfs 함수는 같은 값을 여러 번 반복 계산합니다.
• 피보나치 수열의 정의 특성상 nnn-번째 값을 계산하려면 이전 두 값을 알아야 합니다.
  • 예: dfs(5)계산 시 dfs(4)와 dfs(3) 호출.
  • dfs(4) 호출 시 dfs(3), dfs(2) 호출 → dfs(3)가 중복 호출됨.
• 시간 복잡도가 O(2^n)으로 매우 비효율적이며, n=100,000같은 큰 입력에서는 시간 초과가 발생합니다.

 

2. 모듈러 연산 위치 오류

• dfs(d−1)+dfs(d−2)를 계산 후 전체를 % 1234567로 나누지 않고, 최종적으로만 나머지 연산을 적용.
• 이 경우 중간 값이 매우 커질 수 있어 불필요한 메모리 및 계산 낭비가 발생할 수 있습니다.

 

3. 스택 오버플로우 가능성 

• 재귀 호출은 스택 메모리를 사용하므로 n이 매우 큰 경우 스택 오버플로우가 발생할 가능성이 있습니다.

 

---

 

[ 정답 코드 & 올바른 풀이 ]

 

📌 올바른 풀이

 

1. 시간 복잡도 문제 해결

• 중복 계산을 방지하기 위해 반복문과 배열을 사용했습니다.
• 시간 복잡도를 O(n)으로 줄였습니다.

 

2. 모듈러 연산 위치 오류 해결

• 피보나치 수열 계산 중간 단계에서 (dp[i-1] + dp[i-2]) 연산을 수행하여 값이 커지는 것을 방지합니다.

 

3. 재귀 제거 

• 재귀 호출을 반복문으로 대체하여 안정성을 높였습니다. 

 

 

---

 

📌 정답 코드

class Solution {
    public int solution(int n) {
        // 피보나치 수열 값을 저장할 배열
        int[] dp = new int[n+1];

        // 초기값 설정
        dp[0] = 0; // F(0) = 0
        dp[1] = 1; // F(1) = 1

        // 반복문을 통해 피보나치 수 계산
// 2 이상의 n이 입력되었을 때, n번째 피보나치 수를 1234567으로 나눈 나머지를 리턴
        for(int i = 2; i <= n; i++) {
            dp[i] = (dp[i-1] + dp[i-2]) % 1234567;
        }

        return dp[n];
    }
}