Dynamic Programming

DP란

다이나믹 프로그래밍이란 복잡한 하나의 문제를 여러 하위 문제들로 나누고, 각각의 결과를 저장한 후에 해당 문제에 대한 중복 컴퓨팅을 제거하여 효율성을 제거하는 문제 해결 방법이다. 즉, 같은 input에 대한 반복되는 호출을 하는 솔루션을 만났을 때, 우리는 그것을 Dynamic Programming으로 최적화 시킬 수 있다.

 

그리고 DP를 구현하는 방법에는 2가지가 있는데, 하나는 Tabulation이고, 하나는 Memoization이다.

 

Tabluation ( bottom up )

tabulation을 사전에서 찾아보면, 표, 목록 등의 결과를 확인할 수 있다. 이러한 tabulation 방식은 순서대로 차근차근 값을 구하고 구한 값을 토대로 다음 값을 빠르게 구해나가는 bottom up 형태를 취한다.

dp = []

dp[0] = 1

for i in range(1, N):
	dp[i] = dp[i-1] * i

 

Memoization ( top down )

memoization은 부분 문제를 메모하면서 푸는 방식이다. 다만 top-down 방식으로 tabulation 방식과는 달리 먼저 결과값에 접근하려는 시도를 하고, 해당 값에 가까운 값을 DP에서 찾아나가며 중복된 값을 사용하거나 메모하는 형태를 띈다.

 

예를 들어서, 팩토리얼 9를 구한다면 tabulation 방식은 dp[0]에서 dp[9]까지 차근차근 올라가지만, memoization은 do[9]에서부터 dp[8]...dp[1]의 값들을 확인하고 재귀적인 호출 과정을 거친 이후에 최종적인 값을 구합니다.

dp = []

def factorial(n):
	if (n == 0):
    	return 1
    
    return dp[x] = x * factorial(x-1)

 

Memoization vs Tabulation

Memoization과 Tabulation의 공통점은 둘 다 중복된 부분 문제의 비효율을 없애준다는 것이다.

다만 가장 핵심적인 차이점이 있다면 Memoization은 재귀 함수를 사용하고, Tabulation은 반복문을 사용한다는 것이다.

 

즉, Memoization을 사용하면 재귀 함수를 써야하고, 재귀 호출이 너무 많이 일어나면 스택이 계속 쌓이고, 결국에 스택 오버플로우가 발생할 수 있다.

 

 

dp를 사용하기 위한 2가지 필요 조건

dp를 사용하기 위해서 필요한 조건이 2가지 있다. 하나는 최적 부분 구조이고, 하나는 중복되는 부분 문제이다.

최적 부분 구조는 영어로 Optimus Substructure이고, 중복되는 부분 문제는 영어로 Overlapping Subproblems이다.

 

그럼 먼저 최적 부분 구조부터 찾아보자.

 

최적 부분 구조 ( Optimus Substructure )

최적 부분 구조가 있다는 것은 부분 문제들의 최적의 답을 이용해서 현존 문제의 최적의 답을 구할 수 있다는 뜻이다.

 

이렇게만 설명하면 잘 이해가 안 갈 수도 있으니 피보나치 문제를 예시로 살펴보자.

피보나치 문제에서 5번째 피보나치 수를 구하기 위해서는 4번째 피보나치 수를 구하는 부분 문제와 3번째 피보나치 수를 구하는 부분 문제를 먼저 해결해야 한다. 그리고 이 두 부분 문제의 최적의 답을 구하면 그걸 이용해서 기존 문제의 최적의 답을 구할 수 있다.

 

즉, 피보나치 문제는 최적 부분 구조를 갖고 있는 것이다.

 

또 다른 예시로는 다음과 같이 서울에서 부산으로 갈 수 있는 다양한 경로 중에 최단거리를 갈 수 있는 경로를 찾고 싶다고 하자.

이때, 부산으로 가기 위해서는 서울에서 각각 H, I, J로 가는 최단 경로를 구해서 비교하면 서울에서 부산까지의 최단 경로를 알 수 있다. 이렇게 부분 문제들의 최적의 답을 이용해서 기존 문제의 최적의 답을 구할 수 있다.

 

그래서 이중에서 최단 경로는 빨간색 경로가 되는 것이다.

 

중복되는 부분 문제 ( Overlapping Subproblems )

중복되는 부분 문제를 해결하기 위해서는 재귀 함수를 기준으로 생각해봐야 한다. 그럼 피보나치 예시를 다시한번 살펴보자.

fibo(5)를 해결하기 위해서는 fibo(4)라는 부분 문제와 fibo(3)이라는 부분 문제를 해결해야 한다. 그리고 또 fibo(4)를 해결하기 위해서는 fibo(3)이라는 부분 문제와 fibo(2)라는 부분 문제를 해결해야 한다. 그리고 마지막에서 나오는 fibo(2)와 fibo(1)은 기본 케이스이므로 그냥 값 자체를 반환해주면 된다.

 

 

그런데 위 그림을 보면 fibo(3), fibo(2) 등 중복되는 문제가 있다. 이런 걸 중복되는 부분 문제로 영어로는 Overlapping Subproblem이라고 한다. 이렇게 중복되는 부분 문제를 여러 번 계산하면 비효율적이게 된다.

 

그래서 DP는 이 문제를 해결할 수 있다.

 

그런데 여기서 간과하지 말아야 할 점은 문제를 부분 문제로 나눈다고 해서 항상 중복되는 부분 문제가 있는 것은 아니다.

즉, Divide & Conquer를 살펴보아야 한다는 것이다. 예를 들어, merge sort의 경우에는 왼쪽 반과 오른쪽 반을 나눠서 각각 해결하는 과정은 완전히 독립적이다. 따라서 서로 겹치는게 없다는 의미이고, 그렇기 때문에 merge sort의 두 부분 문제는 Non-overlapping Subproblem이다.

 

정리

정리하면 다이나믹 프로그래밍은 똑같은 문제를 여러 번 풀어야한다는 비효율을 해결하는 알고리즘 패러다임이다. 그리고 이러한 다이나믹 프로그래밍으로 해결할 수 있는 문제는 다음과 같은 조건을 충족해야 한다.

1. 최적 부분 구조가 있다.
2. 중복되는 부분 문제들이 있다.

그리고 이러한 다이나믹 프로그래밍을 구현하는 방법은 2가지로 나뉜다.

1. Memoization
2. Tabulation

 

 

 

인용

https://velog.io/@nninnnin7/Dynamic-programming-1

DP의 종류 - Tabulation과 Memoization

https://nulls.co.kr/codeit/386

2. [Dynamic Programming] 중복되는 부분 문제 (Overlapping Subproblems)