동적 프로그래밍(Dynamic Programming)이란?
동적 프로그래밍은 복잡한 문제를 작은 문제로 분해하여 해결하는 알고리즘 디자인 기법 중 하나입니다. 분할 정복(Divide and Conquer)과 유사하며, 분할 정복과의 차이점은 동적 프로그래밍은 중복되는 부분 문제가 발생할 때, 그것을 한 번만 계산하고 그 결과를 메모이제이션(Memoization)하여 다른 비슷한 부분 문제들이 다시 발생할 때, 메모이제이션된 결과를 가져와 재활용한다는 것입니다.
동적 프로그래밍을 적용하기 위해서는 다음의 두 가지 조건을 만족해야 합니다.
- 최적 부분 구조(Optimal Substructure): 전체 문제의 최적해가 부분 문제의 최적해로부터 구해질 수 있어야 합니다.
- 중복되는 부분 문제(Overlapping Subproblems): 부분 문제가 중복되어 여러번 반복 계산되어야 합니다.
메모이제이션 (Memoization)
메모이제이션(memoization)은 동적 프로그래밍(Dynamic Programming) 기법 중 하나로, 함수의 실행 결과를 저장하여 이후 같은 입력이 들어올 때 다시 계산하지 않고 저장된 값을 불러와서 재활용하는 최적화 기법입니다.
메모이제이션은 함수의 결과 값을 저장하는 캐시(Cache)를 이용하여 동작합니다. 함수를 호출할 때마다 입력 값에 대한 결과 값을 캐시에 저장합니다. 이후 같은 입력이 들어올 때는 함수를 실행하지 않고 저장된 값을 바로 반환합니다. 이렇게 하면 함수를 반복해서 호출할 때마다 계산하는 시간을 절약할 수 있으며, 함수의 실행 속도를 대폭 향상시킬 수 있습니다.
메모이제이션을 사용하기 위해서는 다음과 같은 조건이 필요합니다.
- 문제는 부분 문제로 나눌 수 있어야 합니다.
- 부분 문제는 중복되어야 합니다.
- 부분 문제의 해결 결과를 저장하고 재사용할 수 있어야 합니다.
메모이제이션은 대부분의 동적 프로그래밍 문제에서 사용되며, 재귀 함수를 이용한 Top-Down 방식으로 구현하는 경우가 많습니다.
하지만 Bottom-Up 방식으로도 구현할 수 있으며, 이 경우에도 부분 문제의 해결 결과를 배열 또는 리스트에 저장하여 재활용합니다.
동적 프로그래밍의 구현 방법
➰Top-Down
Top-Down은 분할 정복과 비슷한 구조를 가지고 있습니다. 전체 문제를 작은 부분 문제로 나누고, 그 부분 문제들을 해결하기 위해 재귀적으로 동작합니다. 이 때, 중복되는 부분 문제들을 해결하기 위해 메모이제이션(Memoization)이라는 기법을 사용합니다. 이는 부분 문제의 결과를 캐시하여 재활용하는 것을 말합니다.
Top-Down 방식은 일반적으로 재귀함수를 이용하여 구현합니다. 따라서 코드의 가독성이 높아지지만, 많은 스택 메모리를 사용할 수 있으며, 메모이제이션의 처리 오버헤드가 존재할 수 있습니다.
➰Bottom-Up
Bottom-Up은 재귀적인 호출 없이, 작은 부분 문제들을 먼저 해결하고, 그 결과를 이용해 전체 문제의 최적해를 구하는 방식입니다. 이 때, 이전에 계산한 결과를 배열 또는 리스트 등의 자료구조에 저장하고, 그 결과를 이용해 다음 계산을 수행합니다.
Bottom-Up 방식은 일반적으로 반복문을 이용하여 구현합니다. 따라서 코드의 가독성은 낮아질 수 있지만, 많은 반복문을 이용하기 때문에 스택 메모리를 사용하지 않아 메모리 절약 효과가 있으며, 메모이제이션의 처리 오버헤드가 없습니다.
동적 프로그래밍의 예시
피보나치 수열(Fibonacci Sequence)
피보나치 수열은 이전 두 항의 합을 다음 항으로 정의하는 수열로, 다음과 같이 정의됩니다.
fib(0) = 0
fib(1) = 1
fib(n) = fib(n-1) + fib(n-2), (n >= 2)
피보나치 수열을 계산하는 가장 간단한 방법은 재귀함수를 이용하는 것입니다. 그러나 위 그림과 같이 반복 계산 되는 부분 문제가 생깁니다. 그래서 이 방법은 n이 커질수록 지수적인 시간 복잡도를 가지기 때문에 비효율적입니다.
동적 프로그래밍을 이용하면 중복되는 계산을 피할 수 있습니다. Top-Down 방식에서는 각 부분 문제의 결과를 캐시하여 재활용하고, Bottom-Up 방식에서는 각 부분 문제의 결과를 이용해 다음 부분 문제를 계산합니다.
def fib_top_down(n, memo):
if n in memo:
return memo[n]
if n < 2:
memo[n] = n
else:
memo[n] = fib_top_down(n-1, memo) + fib_top_down(n-2, memo)
return memo[n]
n = 10
memo = {}
result = fib_top_down(n, memo)
print(result)def fib_bottom_up(n):
if n < 2:
return n
memo = [0] * (n+1)
memo[0] = 0
memo[1] = 1
for i in range(2, n+1):
memo[i] = memo[i-1] + memo[i-2]
return memo[n]
n = 10
result = fib_bottom_up(n)
print(result)Top-Down 방식에서는 memo 딕셔너리를 이용하여 이미 계산된 값을 저장하고, 이를 활용하여 재귀 호출 시 중복 계산을 피합니다. Bottom-Up 방식에서는 반복문을 사용하여 작은 부분 문제부터 차례대로 계산하며, 그 결과를 테이블에 저장하여 재활용합니다.
두 방식 중에서는 문제의 특성에 따라 더 나은 방법이 달라질 수 있습니다. 일반적으로는 두 방식 모두 성능이 비슷하며, 상황에 따라 더 효율적인 방법을 선택하는 것이 중요합니다.
Bottom-Up VS Top-Down
Dynamic Programming에서 Bottom-Up 방식과 Top-Down 방식은 모두 메모이제이션을 사용하여 중복 계산을 피합니다.
Bottom-Up 방식은 큰 문제를 작은 문제들로 쪼개어 해결해 나가는 방식으로, 이전의 작은 문제의 결과를 재활용하여 큰 문제를 해결합니다. 이 때, 작은 문제의 결과를 저장하는 배열이 필요하며, 이 배열의 크기는 입력의 크기에 비례합니다. 따라서, Bottom-Up 방법은 입력 크기가 커질수록 더 많은 메모리를 필요로 하지만, 계산을 수행하는 데 있어서 효율적이며, 재귀 함수 호출을 하지 않기 때문에 함수 호출 스택의 크기를 초과하는 문제를 방지할 수 있습니다.
Top-Down 방식은 큰 문제를 해결하기 위해 작은 문제를 재귀적으로 해결하는 방식으로, 재귀 함수 호출을 사용합니다. 이 때, 작은 문제의 결과를 저장하기 위해 배열이 필요하지 않고, 필요한 부분 문제만을 계산하기 때문에 Bottom-Up 방법보다 적은 메모리를 사용합니다. 또한, 모든 부분 문제를 해결하지 않아도 되기 때문에, 필요한 부분 문제만을 빠르게 해결할 수 있습니다. 하지만, 재귀 함수 호출을 반복적으로 수행하면서 함수 호출 스택의 크기가 커져 스택 오버플로우가 발생할 가능성이 있습니다.
Top-Down 방식은 메모이제이션(Memoization)을 사용하여 이전에 계산한 값을 캐시합니다. 이 때, 캐시에 사용되는 배열의 크기는 입력 크기와 같거나 작기 때문에 메모리 사용량이 상대적으로 적습니다. 그러나 재귀 함수 호출에 따른 스택 메모리 사용량이 증가할 수 있으며, 이는 메모리 사용량을 증가시킬 수 있습니다.
반면, Bottom-Up 방식은 입력 크기에 비례하여 배열 또는 리스트를 생성하여 계산 결과를 저장합니다. 이 때, 메모리 사용량은 입력 크기와 동일합니다. 그러나 스택 메모리를 사용하지 않기 때문에 메모리 사용량이 크게 증가하지 않습니다.
따라서, 입력 값이 큰 경우 Bottom-Up 방식이 더 효율적이며, 입력 값이 작은 경우 Top-Down 방식이 가독성이 높고 구현이 간단하기 때문에 더 선호될 수 있습니다. 또한, 메모이제이션에 의한 처리 오버헤드가 크게 영향을 미치지 않는 경우에도 Top-Down 방식을 사용할 수 있습니다.
결국에는 각 문제의 특성에 맞는 최적의 방법을 선택해야 합니다.
