동적 계획법 (Dynamic Programming)
동적 계획법은 반복되는 작은 문제의 결과 값을 통해서 큰 문제를 해결하는 방식을 말한다.
동적 계획법의 조건
어떤 문제를 동적 계획법으로 풀기 위해서 해당 문제가 다음과 같은 경우인지 확인해봐야한다.
- 문제를 더 작은 간단한 문제로 나눌 수 있는 경우
- 작은 문제가 반복되는 경우
- 최적의 하위 구조 → 전체의 최적 해가 하위 문제의 최적해로 구성되는 경우
vs 분할 정복(Dvide and Conquer)
분할 정복은 작은 문제가 중복이 되는지 여부의 차이가 있다.
분할 정복은 단순히 문제를 작은 단위로 나누어 푸는 방식이고,
동적 계획법의 경우 작은 단위의 문제들이 반복되어 이전에 해결한 작은 문제의 결과를 통해서 큰 문제의 해답을 찾는 방식이다.
Memoziation
Memoziation은 동적 계획법에 필요한 중요한 개념이다.
동적 계획법의 경우 작은 문제들을 반복해서 계산하는 비효율적성을 개선하기 위해서, 앞서 계산한 작은 문제를 저장(Memo)해두고 다시 사용하게 된다. 이를 Memoziation이라고 한다.
동적 계획법의 접근 방법 - Top-Down / Bottom-Up
문제를 해결하는 방향에 따라서 Top-Down, Bottom-Up의 차이가 있다.
Top-Down (Memorization)
def fivo_top_down(n):
if n == 1 or n == 2 : return 1
return fivo(n - 1) + fivo(n - 2)
fivo_top_down(5)피보나치 문제를 재귀로 푸는 경우 fivo(5) → fivo(4) → … → fivo(1)로 큰 문제에서 작은 문제로 해결할 수 있다. 하위 문제를 해결하는 함수의 결과 값이 cache에 저장되고 동일한 입력으로 함수가 다시 호출되는 경우 캐시된 결과를 반환하게 된다.
Bottom-Up (Tabulation)
def fivo_bottom_up(n):
arr = [0] * (n + 1)
arr[1] = 1
arr[2] = 1
for i in range(2, n + 1): arr[i] = arr[i-1] + arr[i-2]
return arr[n]
fivo_bottom_up(5)같은 피보나치 문제를 반복문을 통해 이전 값을 저장하고 다음 문제 해결에 사용하는 방식을 사용한다면 fivo(1),fivo(2) → fivo(3) → … → fivo(n)으로 작은 문제에서 큰 문제 방향으로 문제를 해결할 수 있다. 상향식의 경우 하위 결과를 직접 테이블에 저장해서 이후 큰 문제를 해결하는 과정에서 사용하게 된다.
Top-Down 방식은 연산에 사용되는 시간, 메모리를 더 사용하는 방식으로 바라볼 수 있고,
Bottom-Up 방식은 물리적 메모리를 더 사용해서 연산에 사용되는 시간을 절약하는 방식으로 볼 수 있다는 생각을 했다.
직접 해보기
하노이의 탑은 DP라고 볼 수 있나?
DP를 공부하면서 분할 정복에 대한 개념을 다시 한 번 보게 되었고, 분할 정복의 예로 함께 봤었던 하노이의 탑 문제가 떠올랐다. 그러면서 하노이의 탑은 왜 DP로 정의 하지 못하는지에 대한 의문이 생겼다.
하노이의 탑 문제의 경우도 작은 문제를 통해서 큰 문제를 해결하는 방식이라 DP의 범위 포함될 수 있지 않을까 하는 생각을 했었다.
왜냐하면 예를 들어 4장의 판을 옮기는 하노이의 탑 문제를 생각해보았을 때,
- 1 ~ 3번 판을 가운데 탑 2번으로 옮기기
- 4번 판을 오른쪽 탑 3번으로 옮기기
- 1 ~ 3번 판을 오른쪽 탑 3번으로 옮기기
과정으로 나누어 볼 수 있다.
그리고 1~3번 판을 움직이는 과정도 위 과정의 반복이 되기 때문에 작은 문제들이 반복되는 것 처럼 보인다.
어쩌면...
하노이의 탑의 이동횟수를 구하는 문제라고 본다면 어쩌면 DP로 볼 수 있다.
위에서 설명한 하노이의 탑 이동 메커니즘을 간략하게 도식화 해보면, H(n) = H(n-1) + 1 + H(n-1)로 볼 수 있다. 이렇다면 DP의 조건인 하위 문제로 분리가 가능하고, 이전의 값을 저장해서 사용하는 구조가 되기 때문에 DP로 볼 수 있을 것 같다.
근데 왜 하노이의 탑은 DP가 아닐까...
하노이의 탑은 문제 해결을 위해서 최적의 선택, 최적의 값을 구하는 문제가 아니다. 하노이는 각 단계에서 어떠한 최적의 방식을 선택하는 것이 아닌 규칙에 의해서 움직이기 때문에, 작은 문제의 최적의 값을 통해 큰 문제를 해결한다는 틀의 DP에는 맞지 않는 부분이 있다. 그리고 같은 이유로 각 단계에서 이전 결과 값을 통해 이후 문제를 해결하는 과정이 아니기 때문에 DP라고 보기 힘들다고 생각한다.
