다이나믹 프로그래밍 (DP)
다이나믹 프로그래밍은 어떤 큰 문제를 반복되는 작은 문제로 나누거나, 작은 문제에서 구한 정답이 그것을 포함하는 큰 문제에서도 동일할 때 사용하는 알고리즘이다. 예를 들어 피보나치 수열을 고려해보자.
피보나치 수열이란 아래의 그림과 같이 두 수의 합이 다음 수가 되어 지속적으로 앞선 두 값을 더해나가는 수열이다.
일반적으로 피보나치 수열에서는 처음 두 값이 주어지고 그 뒤로 계속해서 마지막 두 값을 더해나간다. 즉, f(n) = f(n-1) + f(n-2)로 나타낼 수 있다.
예를들어 첫번째 값과 두번째 값이 1, 1이라고 해보자. 이때 100번째 값을 구하기 위해서는 f(100) = f(99) + f(98)일 것이다. 그리고 이 식은f(100) = (f(98) + f(97)) + (f(97) + f(96))으로 나타낼 수 있다.
이 것을 코드로 나타내면 아래와 같이 나타낼 수 있다.
def fibonacci_sequence(first, second, target):
if target == 1:
return first
if target == 2:
return second
return fibonacci_sequence(first, second, target - 1) + fibonacci_sequence(first, second, target - 2)
구해야 하는 값이 100,000번째, 1,000,0000번째로 커진다면 메모리에 상당한 부담이 가해질 것이다. 그리고 하위 번째의 값으로 갈수록 반복이 매우 커질 것이다.
이 부담을 줄이고 효율적으로 결과를 구하기 위해서는 어떻게 해야할까?
Top-Down vs Bottom-Up
이 부담을 줄이는 방법은 크게 두가지가 있다.
첫번째로, 반복되는 계산을 저장해두고 해당 계산이 필요할때 캐싱된 값을 꺼내오면 될 것이다.
f(100)을 계산한다면 100칸짜리 배열을 만들어 두고, f(99)가 완료된 시점에 해당 값을 배열의 99번째 칸에 넣는다. 이를 위해서 f(98)과 f(97)이 실행되면 해당 값도 마찬가지로 배열에 넣는다.
이 방식으로 접근하면 반복된 연산을 할 필요가 없어 훨씬 효율적일 것이다.
이렇게 최상위에서 부터 하위로 전개하는 방법을 Top-Down 방식, 또는 값을 메모해둔다고 해서 메모이제이션(Memoization) 방식이라고 한다.
두번째 방식은 100번째 값을 찾을때 까지 하위에서부터 점점 계산해나가는 방식이다.
첫번째 값과 두번째 값이 각각 1, 1일 때, 이것을 배열로 나태면 [1, 1, 2, 3, 5, 7, ...]로 나타낼 수 있을 것이다.
이 때 배열의 0번째 값은 피보나치 수열의 첫번째 값이고, 1번째 값은 두번째 값이다. 즉, 배열의 n번째 값이 피보나치 수열의 n+1번째 값이다.
그렇다면 배열의 길이가 100이 될 때까지 계속 배열을 늘려나가면 결과를 찾을 수 있을 것이다.
이것을 코드로 나타내면 다음과 같다.
def fibonacci_sequence(first, second, target):
array = [first, second]
while len(array) < target:
array.append(array[-1], array[-2])
return array[-1]한눈에 보기에도 훨씬 간단하게 구현된 것을 볼 수 있다.
이렇게 하위에서 부터 답을 찾을 때까지 상위로 전개해 나가는 방식을 Bottom-Up 방식이라고 한다.
피보나치 수열과 같은 문제는 전형적인 Bottom-Up으로 풀 수 있는 문제 유형이다.
하지만 문제 유형에 따라 필요한 접근 방식을 취하는 것이 중요하다.
특히, DP 문제는 문제를 DP 방식으로 풀어야한다는 것을 캐치하기 어려운 경우가 많고 BFS/DFS 등 다른 접근방식을 취했다가 메모리 폭탄을 맞는 경우도 빈번하다.
또한, f(100) = f(99) + f(98)이라는 발화식을 찾기도 어려운 경우가 많으니, 다양한 문제를 풀어보는 것이 중요하다.
