동적 계획법(Dynamic Programming)과 메모이제이션(Memoization)

동적 계획법 Dynamic Programming

 

 

집에 가려고 택시를 탔다고 생각해보자.

그런데 택시가 같은 길을 뱅뱅 돌아가면 시간도 돈도 나의 인내심도 한계에 달할 수 있다.

 

택시 기사가 불필요한 경유지를 제거하고 중복된 경로를 최소화한다면,

보다 효율적인 귀가길이 될 수 있을 것이다.

 

마찬가지로 동적 프로그래밍 또는 동적 계획법은 주어진 문제를 세분화하여 최적의 해법을 찾아내는 방법이다.

이는 중복된 부분을 줄이고 불필요한 요소를 배제함으로써 연산의 효율을 높일 수 있다.

 

예를 들어 피보나치 알고리즘을 통해 살펴보자.

피보나치에 대한 자세한 사항은 앞서 포스팅했던 내용을 참고하자.

 

 

---

~ 광고 타임 ~

---

 

기존 피보나치 알고리즘의 문제점

 

 

인덱스	0	1	2	3	4
값	0	1	1	2	3

 

예를 들어, 위와 같이 수열 { 0, 1, 1, 2, 3 }이 있을 때 길이는 5가 된다.

피보나치 함수 f(n)을 통해 인덱스 4의 값을 구한다고 생각해보자.

 

피보나치 정의에 따라 f(4) = f(3) + f(2)의 형태가 된다.

마찬가지로 f(3) = f(2) + f(1)이 될 것이다.

 

즉, 이를 보면 f(4)는 다음과 같다.

f(4) = f(f(2) + f(1)) + f(2)

 

바로 이 부분에서 비효율적인 연산이 발생한다.

 

이미 f(2)를 실행하여 결과를 알았던 상황에 다시 f(2)를 호출하고 있기 때문이다.

 

이러한 중복을 제거해준다면 보다 효율적인 알고리즘이 될 수 있다.

자바 코드로 살펴보자.

 

 

 

---

~ 광고 타임 ~

---

 

 

JAVA 예제

package dp;

import java.util.HashMap;

public class DynamicProgramming {
	static int cnt = 0, index = 30, temp = 0;
	static double before, after = 0; //시간 측정용
	
	public static void main(String[] args) {
		System.out.println("#아이티-잉");
		
		//일반 피보나치 재귀함수
		before = System.currentTimeMillis();
		temp = fn_Fibonacci(index);
		after = System.currentTimeMillis();
        System.out.println("1. 피보나치\nf(" + index + ")일 때, 결과값 : " + temp + "\n함수 호출 횟수 : " + cnt + ", 수행시간 : " + (after-before) + "ms");
        cnt = 0;
        temp = 0;
        
        //DP 피보나치 재귀함수
        HashMap<Integer, Integer> dp = new HashMap<Integer, Integer>(); //중복연산 방지
                
        before = System.currentTimeMillis();
        temp = fn_DP_Fibonacci(index, dp);
		after = System.currentTimeMillis();
        System.out.println("\n2. 동적계획법 피보나치\nf(" + index + ")일 때, 결과값 : " + temp + "\n함수 호출 횟수 : " + cnt + ", 수행시간 : " + (after-before) + "ms");

	}
	
	public static int fn_Fibonacci(int n){
        cnt++;
        if(n == 0){
            return 0;
        }else if(n <= 2){
            return 1;
        }else{
            return fn_Fibonacci(n-1) + fn_Fibonacci(n-2);   
        }
    }
	
	public static int fn_DP_Fibonacci(int n, HashMap<Integer, Integer> dp){
		cnt++;
		if(dp.containsKey(n)){ //이미 연산했던 적이 있다면, 그 값을 꺼내 돌려준다.
			return dp.get(n);
		}else if(n == 0){
			return 0;
		}else if(n <= 2){
			return 1;
		}else{
			int value = fn_DP_Fibonacci(n-1, dp) + (fn_DP_Fibonacci(n-2, dp));
			dp.put(n, value);
			return value;
		}
    }
}

 

결과

 

 

f(30). 즉, 피보나치수열의 29번째 항에 해당하는 값은 832040이고, 1번과 2번 방법 모두 결과가 동일하다.

그러나 함수 호출 횟수와 수행시간 차이가 굉장히 큰 것을 알 수 있다.

 

HaspMap 클래스를 이용하여 인덱스와 값을 저장해 두었다가 이를 재활용하기 때문이다.

해시맵 클래스는 key와 value 값을 묶어 한 쌍으로 저장하는 자료구조를 가진다.

해시(hash)에 대한 용어 정리는 앞서 포스팅에서 소개한 바 있으니 참고하자.

 

이러한 기억을 위한 별도의 장치를 메모이제이션(Memoization)또는 메모아이제이션(MemoIzation)이라고 한다.

 

 

 

 

마치며

 

동적 프로그래밍의 개념은 사실 어렵지 않으나, 별도의 장치를 마련해야 하기에 머리가 아플 수 있다.

 

프로그래밍에 있어서 가독성도 중요한 만큼,

상황에 맞도록 적절한 방법론과 효율적인 해법을 찾아 적용하도록 하자.

 

 

 

끝