[알고리즘] 동적 계획법(Dynamic Programming) & 메모이제이션(Memoization)

[알고리즘] 동적 계획법(Dynamic Programming) & 메모이제이션(Memoization)

---

동적 계획법이란?

주어진 문제를 세분화시키고, 최적의 해법을 찾아내기 위한 방법

DP를 이용하면 중복된 부분을 제거하여 다시 계산하지 않아도 되는 장점이 있다. 이는 연산의 효율을 높여주는데 큰 역할을 한다.

이를 알아보기 위해서는 '피보나치 수열'로 알아보기 쉽다

피보나치 수열은 위와 같은 구조로 '재귀 함수'를 통해 구현된다.

즉, index 0과 1을 제외하고 f(n) = f(n-1) + f(n-2)로 정의가 가능하다.

하지만, index의 값이 커질수록 호출되는 재귀함수가 무궁무진하게 커지는 문제가 발생한다.

지금처럼 빨간 원으로 묶인 부분은, 완전히 똑같은 부분을 다시 불러오는 모습을 볼 수 있다.

이처럼 기본적인 재귀 함수를 통해서 피보나치 수열에 대한 값을 도출 해낼 수는 있지만 효율적인 알고리즘이라고 보기는 힘들다.

이처럼 중복되는 부분을 제거할 수 있다면, 보다 효율적인 알고리즘을 짤 수 있는데 이때 사용되는 것이 바로 동적 계획법(Dynamic Programming)이다.

중복되는 부분을 제거하기 위해 HashSet을 사용해서 구현하면 된다.

이처럼 기존의 정보를 기억해두고, 중복을 걸러내기 위한 장치를 '메모이제이션'이라고 부른다.

기본 피보나치 수열의 알고리즘과 동적 계획법을 적용한 알고리즘을 비교해보자

import java.util.HashMap;
 
public class fibonacci {
 
    static int count = 0; // 함수 호출 수
    static int index = 30; // 피보나치  수
    static int result = 0; // 피보나치 결과 값
    
    static double start, end = 0; // 시간 측정
    
    public static void main(String[] args) {
        
        //일반 피보나치
        start = System.currentTimeMillis();
        result = fibo(index);
        end = System.currentTimeMillis();
        
        System.out.println("[일반 피보나치] index:" + index + ", 결과값:" + result);
        System.out.println("함수 호출 수: " + count + ", 수행시간: " + (end-start) + "ms");
        
        System.out.println("=====================================");
        
        count = 0;
        result = 0;
        
        //DP 피보나치
        HashMap<Integer, Integer> dp = new HashMap<>();
        
        start = System.currentTimeMillis();
        result = fibo_DP(dp, index);
        end = System.currentTimeMillis();
        
        System.out.println("[DP 피보나치] index:" + index + ", 결과값:" + result);
        System.out.println("함수 호출 수: " + count + ", 수행시간: " + (end-start) + "ms");
        
    }
    
    public static int fibo(int index){
        count++; // 함수 호출 수 증가
        
        if(index == 0) {
            return 0;
        } else if (index <= 2){
            return 1;
        } else {
            return fibo(index-1) + fibo(index-2);
        }
    }
    
    public static int fibo_DP(HashMap<Integer, Integer> dp, int index){
        count++; // 함수 호출 수 증가
        
        if(dp.containsKey(index)){ // 연산한적 있으면 그 값 return
            return dp.get(index);
        } else if (index == 0) {
            return 0;
        } else if (index <= 2) {
            return 1;
        } else {
            int val = fibo_DP(dp, index-1) + fibo_DP(dp, index-2);
            dp.put(index, val);
            
            return val;
        }
    }
 
}
 

출력 값은 아래와 같다

index를 30으로 뒀을 때, 피보나치의 결과 값은 832040으로 두 메소드에서 같은 값이 나오는 것을 볼 수 있다.

하지만 함수 호출 수를 확인했을 때 어마어마한 차이가 난다. 

DP 피보나치는 이미 저장된 정보를 메모이제이션하면서 다시 같은 정보가 들어왔을 때 추가로 함수를 호출하지 않아도 된다.

이로써 함수 호출에 대한 시간 비용을 상당히 절약할 수 있는 효과를 가져다 주는 것이 다이나믹 프로그래밍이다.