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

---

public class 피보나치수 {

    public static int solution(int n) {

        int[] f = new int[n+1];

        f[0] = 0;
        f[1] = 1;

        for (int i=2; i<n+1; i++) {
            f[i] = (f[i-2] + f[i-1]) % 1234567;
        }

        return f[n];
    }

    public static void main(String[] args) {
        System.out.println(solution(3));
        System.out.println(solution(5));
    }
}

---

 

>>> 동적 프로그래밍 이용 ✏️

 

DP (Dynamic Programming) 동적 계획법

- 복잡한 문제를 더 작은 하위 문제로 나누어 해결하는 알고리즘 설계 기법

- 하위 문제의 결과를 저장하여 중복 계산을 피하고, 전체 문제를 효율적으로 해결한다.

 

 

DP와 재귀적 호출의 차이점

 

하향식(Top-down) 접근, 상향식(Bottom-up) 접근

- 재귀적 호출은 주로 하향식 접근 방식을 사용한다.

- 큰 문제를 작은 하위 문제로 나누어 해결하는 방식이다.

- 동적 계획법은 주로 상향식 접근 방식을 사용한다. 

- 작은 하위 문제들부터 시작하여 그 결과를 저장하고, 이를 이용하여 점진적으로 큰 문제의 해를 구해나간다.

 

Memoization 메모이제이션

- 동적 계획법은 중복되는 계산 결과를 저장하는 메모리 기법인 메모이제이션을 사용한다.

- 이전에 계획한 값을 캐시하고, 다시 필요할 때 해당 값을 가져와 재사용한다.

- 재귀적 호출에서의 중복 계산을 방지하고 계산 속도를 향상시킨다.

 

DP 기법을 적용시킬 수 있는 조건

중복되는 부분 문제 (Overlapping Subproblems)

- DP는 기본적으로 문제를 나누고 그 문제의 결과 값을 재활용해서 전체 답을 구한다. 

- 동일한 작은 문제들이 반복하여 나타나는 경우에 사용이 가능하다.

 

최적 부분 구조 (Optimal Substructure)

- 부분 문제의 최적 결과 값을 사용해 전체 문제의 최적 결과를 낼 수 있는 경우 사용 가능하다.

 

 

장점

- 중복 계산 방지 : 하위 문제의 결과를 저장하여 중복 계산을 피한다.

- 효율성 : 재귀 방식에 비해 훨씬 효율적이다

- 메모리 사용 : 배열을 사용하여 하위 문제의 결과를 저장하므로, 메모리 사용이 효율적이다.

 

단점

- 메모리 사용량이 크다.

- 중간 결과를 저장하기 위해 추가적인 메모리를 사용한다.

- 문제의 크기가 커질수록 필요한 메모리도 증가할 수 있다.

---

for (int i=2; i<n+1; i++) {
    f[i] = f[i-2] + f[i-1];
}

 

이 부분에서 모듈러 연산 (Modular Arithmetic 나머지 연산) 을 적용하지 않으면 메모리와 시간 효율성에 영향을 미친다.

 

f[i] = (f[i - 2] + f[i - 1]) % 1234567;

피보나치 수를 계산할 때 중간 결과에 모듈러 연산을 적용하여 값이 너무 커지지 않도록 한다.

 

 

 

 

---

refer to

https://velog.io/@boyeon_jeong/%EB%8F%99%EC%A0%81%EA%B3%84%ED%9A%8D%EB%B2%95Dynamic-Programming