최적화 - 동적 알고리즘(Dynamic programming)

이번에는 동적 알고리즘과 이것을 통해 0-1 knapsack problem (배낭 채우기)를 다루려고 합니다. 우선적으로 동적 알고리즘에 대해 알아보자면 사전적 의미로서 복잡한 문제를 간단한 여러 개의 문제로 나누어 푸는 방법이라고 되어 있습니다. 그리고 그 대표적인 예로 재귀 함수 형태의 피보나치 수열이 떠오를 텐데요. 

 

예를 들어 f(1)을 넣게 되면 1, f(2)를 넣게 되면 f(1) + f(0) = 2, f(3) = f(1) + f(2) = 3, f(4) = f(3) + f(2) =5...... 이렇게 됩니다. 하지만 이 함수를 메모리 관리적인 차원에서 본다면 매우 비효율적이라고 할 수 있습니다. 

 

f(7)을 컴퓨터에서 컴파일했을때 f(7)을 구하기 위해서 

f(7) = f(6) + f(5) 를 호출하게 됩니다. 이때 f(6)과 f(5)를 알아내기 위해 

f(6) = f(5) + f(4) 를 호출하고 다시 f(5)와 f(4)를 알아내기 위해

f(5) = f(4) + f(3) 을

f(4) = f(3) + f(2)을

f(3) = f(2) + f(1)을

f(2) = f(1) + f(0)을

f(1) = 1

f(0) = 1 

 

위와 같은 수많은 연산과정이 필요하고 메모리의 스택에는 f(0)~~~ f(7)의 값이 저장되게 됩니다. 메모리의 스택 영역이란 함수의 호출과 관계되는 지역 변수와 매개변수가 저장되는 영역이라고 언급되어 있습니다. 이 지역변수가 매개변수란 함수 호출 과정에서 발생한 변수들로서 최종적으로 함수 호출이 완료되면 사라지게 됩니다. 

 

f(2)을 구할 때는 메모리의 스택 영역 안에 매개변수 2와 f(1)과 f(0)을 호출하면서 다시 매개변수 1, 0 그리고 f(1)= 1, f(0)= 0 총 매개변수 2,1,0과 지역변수 f(1)= 1, f(0) =0 이 생긴 후 f(2) = 1라는 결론을 내고 난 뒤 메모리 영역에서 사라지게 됩니다. f(2)를 구하는데도 5개 이상의 변수들이 스택에 쌓이게 되는데 f(7)을 호출하게 되면 더 많은 변수들이 스택에 쌓이게 됩니다. f(7)이 별거 아니라고 생각된다면 만약 f(564)는 얼마나 될까요? 즉 재귀 함수의 경우 메모리에 너무 많은 부담을 주게 됩니다. 

 

그렇다면 f(8)을 계산해보도록 하겠습니다. 이전에 f(7)을 구할 때 알게 된 값들을 이용한다면 f(8) = f(7) + f(6) = 13 + 8 = 21를 쉽게 구할 수 있습니다. 

 

f(0)	f(1)	f(2)	(f3)	f(4)	f(5)	f(6)	f(7)	f(8)
0	1	1	2	3	5	8	13	21

 

하지만 안타깝게도 위의 값들은 메모리 스택 안에 있던 변수들로서 f(7)의 호출이 완료되는 순간 사라지게 됩니다. 즉 f(8)을 구하기 위해 다시 한번 f(0)~f(7)까지 구해야 한다는 말입니다.

 

이렇게 이전에 했던 것을 다시 한번 또 하는 허튼짓(?)을 막기 위해 전역 변수로 배열을 하나 선언해 이전에 계산된 값들을 저장하는 방법인 Top-down과 Bottom-up 이 있습니다. 

 

Top-down 방식이란 문자 그대로 위에서 아래로, 큰 문제에서 작은 문제로 분할해 가며 푸는 방식입니다. 우선 memo [100]라는 배열은 

 

memo[]	0	1	2	3	4	5	6	7	8
	0	0	0	0	0	0	0	0	0

 

으로 초기화되어있습니다. 이 비어있는 배열을 채워놓고 다음에 활용하면 됩니다. 일단 fibonacci(8)을 호출하겠습니다. memo[8] 값이 = 0 이기 때문에 memo[8] = fibonacci(7) + fibonacci(6)을 호출하면서 차례대로 fibonacci(7)~~~ fibonacci(0)의 값들을 함수 f(n)처럼 호출하게 됩니다. 

 

memo[]	0	1	2	3	4	5	6	7	8
	0	1	1	2	3	5	8	13	21

 

fibonacci(8) 이 호출된 후 전역 변수 배열 memo[100] 값들이 저장되게 됩니다. 다시 한번 fibonacci(9)를 호출한다면 이미 저장된 배열의 값들을 이용해 fibonacci(9) = fibonacci(8) + fibonacci(7) = 13+ 21 = 34의 값을 쉽게 얻을 수 있습니다. 

 

마무리하자면 동적 알고리즘이란 반복적으로 큰 문제를 작게 쪼개며 해결해 나가는 것이지만 자칫하면 메모리 스택 영역에 과부하를 줄 수 있기에 배열등을 이용해 값을 저장해 효율적으로 메모리 관리를 할 수 있습니다. 

 

% 원래는 동적 알고리즘을 간단히 언급한 뒤 0-1 knapsack problem (배낭 채우기)에 대해 다루려 했지만 분량 조절로 인해 다음 글에서 다 두도록 하겠습니다. 저 역시 이 글을 포스팅하면서 동적 알고리즘이란 그저 재귀적 방법이라고만 알고 있었는데 메모리 관리 이슈가 있다는 것을 알게 되었습니다. 다음에는 메모리 구조에 대해서도 글을 다뤄보로록 하겠습니다. 

 

나무 위키를 참조했습니다.