동적 계획법 (DP, Dynamic Programing) & 메모이제이션(Memoization)

모 회사의 개발자 분과 밥을 먹었는데 요즘 시니어 개발자 구하기가 힘들다며 한탄 섞인 말을 하셨고 그 회사의 면접관이기도 하셨다. 나는 "시니어 개발자 기술면접 때 뭘 중점적으로 질문하는가?" 대한 질문을 하였고 알고리즘 설계에 대한 질문과 시스템에 트래픽이 몰려 부하가 걸리는 것을 대비하는 아키텍처에 대해 질문을 하신다고 한다.

시스템 아키텍처에 대해서는 다들 경험이 있다 보니 다양한 방식으로 구성을 하는데 알고리즘 설계 질문 때 DP와 메모이제이션에 대한 질문을 하면 개념을 모르는 사람이 많다고 하셨다. 

그래서 블로그에 정리해가며 공부해보려고 한다.

동적 계획법(DP, Dynamic Programming)이 대체 뭐야?

주어진 큰 문제를 여러 개의 작은 문제 단위로 나누어 풀려고 하위 작은 문제들의 해결 방법을 결합하여 주어진 큰 문제를 해결하는 방식인데 이것도 정의에 대해서 검색하다 보니 어떤 부분에 의해 동적으로 프로그래밍이 되는 방식이 아니고 이걸 정의한 사람이 동적 프로그래밍이란 말이 멋있어서 정한 이름이라고 한다. (나도 언젠간 guard programming을 정의...;;;;)

 

어? 그러고 보니 분할 정복(Divide and Conquer)과 비슷하게 느껴졌다. 일반적으로 재귀 함수로 많이 사용했던 방식이었는데 뭐가 다른 거지? 좀 더 찾아보자.

dynamic programming

동적 계획법과 분할 정복 모두 재귀 함수 호출을 통해 구현하는 방법이 동일하지만

동적 계획법은 빨간색 원으로 표시한 것과 같은 중복되는 부분을 제거하며 연산하는 방법이다. 참고로 중복되는 부분을 제거하기 위해 HashSet을 사용하는데 이처럼 정보를 저장하고 중복을 걸러내기 위한 것을 메모이제이션(Memoization)이라고 부른다.

피보나치수열의 공식으로 테스트를 수행해 보고자 한다. 

 

일반적인 피보나치수열의 코드와 수행능력을 살펴보자.

int count = 0;
@Test
public void fibonacci() {
	int input = 40;
	long start = System.currentTimeMillis();
	int result = fib(input);
	long end = System.currentTimeMillis();
	System.out.println(String.format("fibonacci %d 대한 값 %d, 재귀호출 수 : %d, 수행시간은 : %d", input, result, count, (end - start)));
}

public int fib(int index) {
	count++;
	if(index == 0) {
		return 0;
	} else if( index == 1) {
		return 1;
	} else {
		return fib(index - 1) + fib(index - 2);
	}
}

fibonacci 40 대한 값 102334155, 재귀호출 수 : 331160281, 수행시간은 : 605ms

일반적인 피보나치 40을 구하는 방법이다 fib 함수 호출 수는 331160281번 수행 시간은 605ms가 걸렸다.

 

DP를 이용한 피보나치수열의 코드와 수행능력을 살펴보자.

@Test
public void fibonacci_with_dp() {
	HashMap<Integer, Integer> dp = new HashMap<>();
	int input = 40;
	long start = System.currentTimeMillis();
	int result = fib_with_dp(dp, input);
	long end = System.currentTimeMillis();
	System.out.println(String.format("fibonacci_with_dp %d 대한 값 %d, 재귀호출 수 : %d, 수행시간은 : %d", input, result, count, (end - start)));
}

public int fib_with_dp(HashMap<Integer, Integer> dp, int index) {
	count++;
	if(dp.containsKey(index)) {
		return dp.get(index);
	}
	if(index == 0) {
		return 0;
	} else if( index == 1) {
		return 1;
	} else {
		int result = fib_with_dp(dp, index - 1) + fib_with_dp(dp, index - 2);
		dp.put(index, result);
		return result;
	}
}

fibonacci_with_dp 40 대한 값 102334155, 재귀호출 수 : 79, 수행시간은 : 0ms

DP를 이용한 피보나치 40을 구하는 방법은  fib_with_dp 함수 호출 수는 79번 수행 시간은 0ms이다.

두 방식을 비교하면 함수 호출 수는 331,160,202 차이를 보였으며 수행 시간은 605ms으로 많은 차이를 보였으며 index수가 커지면 커질수록 두 방식의 차이는 더욱더 커질 것이다.

 

자! 좀 더 깊게 파고들자!

위에 dp를 이용한 방식의 코드가 무적인가?? 아니다.

큰 수를 수행하기 위해 index를 10000으로 늘려보았다.

stackoverflow

아.. StackOverFlowError가 발생했다. 이 에러가 발생한 이유는

stack limit

함수를 호출할 때마다 Stack에 하나씩 쌓이게 되는데 재귀를 이용해 함수를 계속 호출하다 보면 10000부터 9999 -> 9998 순서대로 쌓일 것이다. 이때 stack limit을 넘게 되면 발생하는 에러이다. 아무튼 저 방식으로는 10000에 대한 값을 구할 수 없다!

위의 방식처럼 최초 주어진 문제부터 풀려고 시도를 했기 때문에 Top Down 방식의 Dynamic Progamming Solution이라고도 말을 한다. 

이를 해결하기 위해 Bottom Up 방식의 Dynamic Progamming Solution을 이용해야 한다.

가장 작은 문제부터 0 -> 1 -> 2 -> .... 이런 식으로 풀어나가야 한다. 이를 코드화 하려면 재귀 방식이 아닌 Loop를 통해 저장 객체 값을 채워 나가야 한다.

 

Bottom Up 방식

@Test
public void fibonacci_bottom_up() {
	int input = 10000;
	long start = System.currentTimeMillis();
	int result = fib_bottom_up(input);
	long end = System.currentTimeMillis();
	System.out.println(String.format("fibonacci_bottom_up %d 대한 값 %d, 수행시간은 : %d", input, result, (end - start)));
}

public int fib_bottom_up(int index) {
	List<Integer> array = new ArrayList<>();
	if (index == 0) {
		return 0;
	} else if (index == 1) {
		return 1;
	}
	array.add(0);
	array.add(1);

	for(int i = array.size(); i < index + 1; i++) {
		int num = array.get(i - 1) + array.get(i - 2);
		array.add(num);
	}
	return array.get(index);
}

fibonacci_bottom_up 40 대한 값 102334155, 수행시간은 : 0
fibonacci_bottom_up 10000 대한 값 1242044891, 수행시간은 : 1

Top Down과 동일하게 40을 구했을 경우 동일한 값과 동일한 수행 시간을 보여줬으며 Top Down의 Stack Limit 문제가 되었던 큰 수도 Bottom Up에서는 1ms의 수행 시간으로 결과를 낼 수 있었다.

Bottom Up 시간 복잡도는 O(n), 공간 복잡도도 O(n)이 되는데 F3을 구하기 위해서는 F2 + F1의 숫자만 필요하게 되므로 피보나치 솔루션 값을 제외 한 나머지는 삭제를 할 수 있기 때문에 O(1)의 공간 복잡도로 줄일 수 있다.