동적 프로그래밍(DP)의 2가지 조건

• [ ] DP를 적용하기 이전에 체크해봐야 할 2가지 조건이 있다 !

최적 부분 구조

: 큰 문제의 최적해는 부분(sub) 문제의 최적해로 구할 수 있어야 한다.

기억하며 풀기(Memoization)

: 동일한 문제를 반복해서 구해야 하는 경우, 한 번 계산된 결과는 저장해 두었다가 활용하는 방식으로 중복 계산을 막는다. → 대표적인 예로 피보나치 수열이 있다.

[Algorithm] 분할정복(Divide-Conquer) & 그리디(Greedy) & 동적계획법(DP)

알고리즘 문제: 피보나치 수

• [ ] 이 문제는 단순하게 n번째 피보나치 수를 구하는 문제이다.

실패 코드

• [ ] DP만 생각하고 문제에 접근했다가, 오버플로우를 고려하지 못해 헤맸던 것 같다.

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

<aside> 💡

문제에서 n번째 피보나치 수를 1234567로 나눈 나머지를 리턴하도록 한 이유 ? → 모듈러 연산 : 연산 도중에 나눗셈을 해도, 최종 결과에 영향을 주지 않으면서 수의 크기를 줄이는 방법.

• 47번째 피보나치 수부터 32비트 정수(int) 범위를 넘어 오버플로우가 발생하기 때문에, 이를 방지하기 위해서 !

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

활용한 수식 참고 - "모듈러 연산"

• 중간에 1234567을 나눠주더라도 결과값에 영향을 미치지 않는다 !

**(A + B) % C ≡ ((A % C) + (B % C)) % C

(증명)
A + B = (q1 * C + r1) + (q2 * C + r2)

→ (A + B) % C = A % C + B % C
= ((q1 * C + r1) + (q2 + C +r2)) % C
= ((A % C) + (B % C)) % C**

</aside>