[To Be Algorithm Genius] (2) DP

유영재·2024년 5월 3일

DP Java algorithm memoization

To Be Algorithm Genius

목록 보기

2/3

두번째 시간이 돌아왔습니다.
너무 어려운 (다 어렵긴 함) DP, Dynamic Programming, 동적 계획법 입니다. (다 같은 말임)
한번 가볼까요 ? 따라오세요 얼른. Come on.

0. Memoization

Memorization 인 줄 알았죠? 메모"리"제이션 아니고 "메모"이제이션 입니다.
DP는 메모이제이션을 무조건 사용한다고 봐도 무방한데요.

💡 Memoization

이전의 계산한 결과를 저장해 (메모하여) 중복 계산을 피하는 것을 의미합니다.
시간적 효율성은 당연히 증가하게 됩니다.

1. DP 접근 방법

N-1 또는 N-2번째 답을 이용해 N번째 답을 구할 수 있을 지 고민해봅니다.
경우의 수 문제다? DP인 경우가 굉장히 많습니다.
초기값으로 1,2번째 값까지는 직접 세팅해주고 점화식으로 N번째 값을 구하는 것이 일반적입니다.

초기값 세팅과 점화식 작성이 포인트 !

2. 피보나치 수열로 알아보는 DP

1. 피보나치 수열이 뭔데?

피보나치 수열이란, 💡
N-2와 N-1번째 값을 더하여 N 값을 나열한 수열입니다.
ex) 1, 1, 2, 3, 5, 8, 13, 21 ...

이를 코드로 생각나는 대로 작성해볼까요?

class DP {
    private static long fibo (int n) {
        if (n <= 2) 
            return 1;
        
        return fibo(n - 1) + fibo(n - 2);
    }
    public static void main(String[] args) {
        System.out.println(fibo(50));
    }
}

직관적으로 떠올렸을 때, 재귀함수로 구현하면 되겠다고 생각이 드는데요!
n-2 번째와 n-1번째 피보나치 수를 더해서 n번째 피보나치 수를 구하는 일반적인 코드입니다.

2. 실행시켜 볼까?

근데, 여기서 문제는 fibo(50)을 호출하면 이 메소드가 몇번 호출될까요?
cnt 변수를 넣어서 함수 호출 횟수를 세봤는데요 ..

?? 25172538049 번 호출됐네요 250억번 .. ??!!
왜 이런 결과가 나왔을까요 ? 아래 그림을 같이 봅시ㄷr

fibo(50) 을 호출하면 재귀적으로 계속 꼬리를 물어 함수를 호출하는데요,
중복된 연산이 발생하는 것이 보이시나요 ?
숫자가 작아질수록 중복되는 연산 횟수가 더욱 많아지고, 250억번이라는 기상천외한 연산 횟수가 나올 수 있는 거랍니다 ..

이게 만약 코딩테스트 환경이었다면, 250초 정도 걸린다는 겁니다 ..
이러면 바로 시간초과겠죠 ? 어떻게 해결하면 좋을까 .. 🤓 고민해보면!

아까 0장에서 이야기한 메모이제이션을 적용해볼게요!

3. 메모이제이션을 이용해보자!

메모이제이션, 즉 메모를 하면서 중복 연산을 줄인다는 건데요!

직전 값을 한번 계산했으면, 이를 배열에 저장해두고 이 값이 필요할 때 다시 연산을 하지 않고도 꺼내서 써서 시간적 효율성을 증가시키는 방식입니다.
코드로 살펴볼까요?

class DP {
    private static long [] dp = new long [101];
    private static long cnt = 0;
    
    private static long fibo (int n) {
        cnt++;

        if (dp[n] > 0) // n번째 피보나치 수를 알고 있다면 바로 리턴
            return dp[n];

        if (n <= 2)
            return 1;

        return dp[n] = fibo(n - 1) + fibo(n - 2); // 메모하기
    }
    public static void main(String[] args) {
        System.out.println(fibo(50));
        System.out.println(cnt);
    }
}