다이나믹 프로그래밍 2
다이나믹 프로그래밍(Dynamic Programming, 동적 계획법)은 하나의 문제(상위 문제)를 보다 작은 문제(하위 문제)들로 나누어 해결하는 알고리즘입니다. 이름에서는 프로그래밍 방법론의 종류처럼 보이지만 그것이 아닌 알고리즘의 이름입니다. 굉장히 간단하지만 문제를 아주 효율적으로 풀수 있는 방법입니다. 그렇다고해서 모든 문제를 다이나믹 프로그래밍을 이용해서 해결할 수 있는것은 아닙니다. 다이나믹 프로그래밍을 적용하기 위해서는 하위 문제로 분할 될 수 있는 문제이어야 합니다.
다이나믹 프로그래밍의 장점을 이해하기 위해선 재귀와 메모이제이션을 먼저 이해하는 것이 바람직합니다. 여기서는 피보나치(fibonacci) 수열을 사용해 각 방법에 대해 이해하고 다이나믹 프로그래밍에 대해 살펴보겠습니다.
피보나치 수열
피보나치 수열은 ƒ(1) = 1, ƒ(2) = 1, ƒ(n) = ƒ(n-2) + ƒ(n-1) 로 계산되는 수열입니다. 즉 첫 번째 수열값 1, 두 번째 수열값 1을 시작으로 바로앞의 두 수열값의 합이 현재 순서의 수열 값이 되는 것입니다. 예로들면 3번째 값(ƒ(3))을 구하고 싶으면 ƒ(1)=1과 ƒ(2)=1의 값을 합한 2가 되는것이죠. 수열을 나열해보면 다음과 같습니다.
1,1,2,3,5,8,13,21…
위에서 다이나믹 프로그래밍을 적용하기 위해서는 하위 문제들로 분할 될수 있는 문제이어야 한다고 했습니다. 피보나치의 경우 ƒ(n) = ƒ(n-2) + ƒ(n-1) 처럼 두 개의 하위 문제로 분할될 수 있는 문제입니다. 참고로 어떤 문제가 주어졌을때 다이나믹 프로그래밍으로 해결 될 수 있는지 없는지 판단을 잘하는것은 매우 중요한 능력입니다. 주어진 문제에 따라 대가들에 의해 이미 만들어진 알고리즘을 대입하는것은 개발 시간을 매우 단축시켜주기 때문입니다!(물론 성능과 품질도 개선, 또한 코딩인터뷰에서 빠른 시간안에 정확하게 문제를 푸는것은 높은 연봉을…)
재귀
재귀(recursion)란 수학에서 말하는 귀납적 정의로써 컴퓨터 과학, 프로그래밍에서는 재귀를 재귀함수로 표현(코딩)할 수 있는데 특정 함수 f가 존재할때 해당 함수 안에서 같은 함수f를 호출하는 것을 의미합니다. 프로그래밍 입문자들이 어려워 하기도 하지만 코드의 표현보다는 이러한 귀납적 정의에 대한 논리적 표현이 잘 안되서 어려워 합니다. 피보나치 수열을 생각해 봅시다. F(n) = F(n-2) + F(n-1)로 함수 F안에서 F를 다시 호출하는 재귀함수라고 말할 수 있습니다.
재귀 표현에는 중요한 조건이 존재합니다. 바로 종료에 대한 조건(terminating condition)이 정의되어야 한다는 것입니다. 피보나치에서는 결국 숫자가 작아저서 0 또는 1로 분해가 되었을때 다시 함수를 호출하는 것이 아닌 0또는 1을 반환해야 한다는 것이죠. 만약 종료 조건이 정의되어 있지않거나 잘못된 조건이 정의되어 있으면 무한루프를 타거나 잘못된 값을 반환합니다. 파이썬 코드로 재귀를 사용해 피보나치를 표현하면 다음과 같습니다.
def fibonacci(n):
if n == 0 or n == 1:
return n
return fibonacci(n-2) + fibonacci(n-1)
print(fibonacci(6))
위 코드를 보면 알수 있듯이 피보나치 수열을 계산할때 재귀를 사용하면 매우 직관적입니다. 이것은 프로그래밍 관습에 대한 관점에서 매우 중요한데 코드는 항상 알아보기 쉽게 작성되어야 하기 때문입니다. 그렇다면 재귀만 사용하면 피보나치수열을 계산하는데 문제가 없을까요?
재귀의 단점 1 - 메모리사용
재귀는 코드를 직관적으로 작성할 수 있다는 장점이 있습니다. 하지만 아주 심각한 단점을 가지고 있는데 메모리 구조에서 Stack을 매우 많이 사용할 수 있다는 점입니다. 재귀는 함수가 계속해서 호출되는 동작방식을 의미합니다. 프로그램에서 새로운 함수가 호출될 경우 새로운 함수의 실행이 완료되고 기존의 실행흐름으로 복귀하기 위해 복귀할 코드가 존재하는, 즉 복귀할 코드의 명령어가 존재하는 메모리 주소를 스택(Stack) 이라는 영역에 저장을 합니다.
위 그림에서 맨 위에 스택이 존재하는데 재귀를 사용해서 함수가 여러번 호출될 경우 스택에 계속해서 데이터가 쌓인다고 할 수 있습니다. 문제는 이 스택의 용량이 제한된다는 것입니다. 이는 프로그래밍 언어나 컴파일러 종류 등에 따라 다르지만 우리가 해결할려고하는 문제에 따라서 100번, 1000번, 10000번의 함수 호출이 발생할 수 있다는 점입니다. 피보나치의 경우 두 번의 재귀호출이 발생하기 때문에 10000번째 피보나치수열을 계산하고 싶으면 스택에 2^10000개의 메모리주소가 저장되어야 합니다.
재귀의 단점 2 - 중복연산
또 다른 문제는 많은 중복연산이 발생한다는 점입니다. 특히 재귀를 사용해서 피보나치 수열을 계산하는 경우 이 문제는 더욱 심각하게 나타납니다. 다음은 여섯 번째 피보나치 수열을 재귀로 계산하는 경우 함수가 호출되는 순서입니다.
처음 fib(6)이 호출되면 fib(4)와 fib(5)를 호출합니다. 근데 이때 fib(4)와 fib(5)는 fib(3)을 중복해서 계산해야합니다. fib(5)는 fib(6)이 계산한 fib(4)를 또 계산하고 있습니다! 만약 100번째 피보나치수열을 계산하는 경우 어떻게 될까요? 아주 많은 중복 계산이 발생하게 됩니다!
메모이제이션
메모 전략(memoization, 메모이제이션)은 이름처럼 메모를 해가면서 문제를 해결하는 방법입니다(참고로 memoization은 컴퓨터 과학에서만 사용되는 용어입니다). 여기서 메모란 주어진 하위문제에 대한 답을 변수에 저장해두어 재귀에서 발생하는 중복 계산을 방지하는 것입니다.
fibo = {}
def fibonacci(n):
if n in fibo:
return fibo[n]
if n == 0 or n == 1:
return fibo[n] = n
fibo[n] = fibonacci(n-2) + fibonacci(n-1)
return fibo[n]
print(fibonacci(6))
코드를 살펴보면 fibo라는 딕셔너리를 이용하여 계산된 결과값을 메모하고있습니다. 그리고 이미 계산된 문제의 경우 바로 리턴을 합니다. 재귀와 아주 작은 차이를 보이지만 이는 성능에 매우큰 영향을 미칩니다. 특히 n이 커지면 커질수록 그 영향은 매우 효과적입니다(재귀에서는 n이 커질수록 지수적으로 반복회수가 늘어남).
메모이제이션을 살펴보면 재귀처럼 여전히 작은 하위 문제들로 접근하며 계산을 합니다. 중복계산 측면에서는 개선이 있었지만 메모리사용, 즉 재귀 호출시 스택에 메모리가 쌓이는 문제는 해결하지 못했습니다.
재귀와 메모이제이션을 다른말로 하향식 접근법이라 합니다. 왜냐하면 가장 큰 문제를 접근하고 거기서 발생하는 하위 문제를 접근, 다시 거기서 하위 문제를 접근하기 때문입니다.
다이나믹 프로그래밍
다이나믹 프로그래밍은 재귀나 메모이제이션과는 다르게 상향식 접근법입니다. 처음부터 가장 작은 문제, 피보나치에서는 ƒ(1)부터 차례대로 계산하여 ƒ(n)까지 계산합니다. 코드를 살펴보겠습니다.
def fibonacci(n):
fibo = [1, 1]
if n == 1 or n == 2:
return fibo[n-1]
for i in range(2,n):
fibo.append(fibo[i-2] + fibo[i-1])
return fibo[n-1]
print(fibonacci(6))
어떤가요? 보다 우아(로직측면에서)하지 않나요? 기존의 재귀나 메모이제이션의 접근법들과 비교해보면 일단 재귀가 없습니다. 즉 함수호출에 대한 스택을 사용하지 않는 구조입니다. 그리고 바로이전에 언급한것과 같이 ƒ(n)에서 하위문제로 접근하는 것이 아닌 처음부터 ƒ(1)부터 순차적으로 n번째 수열값까지 계산을 합니다(감탄).
코딩스타일에 따라 작은부분이지만 여러형태로 표현가능합니다(즉 fibo[1, 1] 을 미리 정의할지 아니면 n이 1 그리고 2가 아닐경우에 정의 할지등의 문제는 다이나믹 프로그래밍과는 관계가 없습니다).