DP

Dynamic Programming, 다이나믹 프로그래밍 : 복잡한 문제를 간단한 여러 개의 문제로 나누어 푸는 방식의 알고리즘

• 메모리를 적절하게 사용하여 수행시간 효율성을 비약적으로 향상시킨다.
• 이미 계산된 결과(작은 문제)는 별도의 메모리 영역에 저장하여 다시 계산하지 않도록 한다.
• 구현은 일반적으로 탑다운과 바텀업 방식으로 나뉜다.

 

---

 

 

DP의 조건

1. 최적 부분 구조 Optimal Substructure : 큰 문제를 작은 문제로 나눌 수 있으며 작은 문제의 답을 모아서 큰 문제를 해결할 수 있다.

2. 중복되는 부분 문제 Overlapping Subproblem : 동일한 작은 문제를 반복적으로 해결해야 한다.

 

---

 

메모이제이션

한 번 계산한 결과를 메모리 공간에 기록해두고 다시 계산하지 않는 방법

• 같은 문제를 다시 호출하면 메모했던 결과를 그대로 가져온다.
• 값을 기록해 놓는다는 점에서 캐싱 caching 이라고도 한다.

코드에서는 배열을 이용해 구현한다.

 

---

 

바텀업 DP

피보나치 수열 문제에서 수열은 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ... 로 현재 항은 이전 두 항의 합으로 결정된다.

점화식으로 표현하면 

• a(1) = 1, a(2) = 1
• a(n) = a(n-1) + a(n-2)

바텀업 방식으로 DP를 구현하기 위해서 먼저 일정 크기의 배열로 메모리 공간을 확보한 뒤, 반복문을 통해 n 이 작은 수부터 차례대로 현재 항의 값을 배열에 저장해두며, 다음 항의 계산에 이용한다.

d = [0] * 100

d[1] = 1
d[2] = 1
n = 99

for i in range(3, n + 1):
	d[i] = d[i - 1] + d[i - 2]

메모이제이션을 활용하면 시간복잡도는 O(n) 이 된다.

 

---

 

탑다운 DP

피보나치 수열 문제를 탑다운으로 구현하면 아래와 같다. 

fibo(5) 를 호출하면 fibo(4), fibo(3), fibo(3), fibo(2), ... 같은 문제를 중복 호출하므로 시간복잡도는 O(2ⁿ) 이 된다.

따라서 메모이제이션으로 공간에 값이 들어있는지 판별하여 이미 계산한 문제라면 다시 계산하지 않도록 재귀 탈출 조건을 걸어준다.

d = [0] * 100

def fibo(x):
	if x == 1 or x == 2:
		return 1
	
	if d[x] != 0:
		return d[x]

	d[x] = fibo(x - 1) + fibo(x - 2)
	return d[x]

 

---

 

DP문제에 접근하는 방법

• 주어진 문제가 DP 유형임을 파악하는 것이 중요하다.
• 그리디, 구현, 완전 탐색 등의 아이디어로 문제를 해결할 수 있는지 검토한 뒤, DP를 고려한다.
• 재귀 함수로 비효율적인 완전 탐색을 구현한 뒤 (탑다운) 작은 문제에서 구한 답이 큰 문제에서 그대로 사용될 수 있으면, 바텀업 DP 방식으로 코드를 개선한다.
• DP vs 분할 정복
  • DP와 분할 정복 모두 최적 부분 구조를 가질 때 사용할 수 있다.
  • DP와 분할 정복의 차이점은 부분 문제의 중복이다. DP 문제는 각 부분 문제들이 서로 영향을 미치며 부분 문제가 중복되지만 분할 정복 문제는 동일한 문제가 반복적으로 계산되지 않는다.