Dynamic Programming (동적 계획법)

• 다이나믹 프로그래밍 알고리즘은 문제를 각각의 작은 문제로 나누어 해결한 결과를 저장해뒀다가 나중에 큰 문제의 결과와 합하여 풀이하는 알고리즘이다.

• 다이나믹 프로그래밍은 이미 진행이 되었던 연산이 반복되는 결점을 보완하기 위해 고안되었다.

• 동일한 작은 문제들이 반복적으로 계산될 때 매번 문제를 재계산하지 않고 값을 저장했다가 재사용하는 기법이 다이나믹 프로그래밍이다.

• 다이나믹 프로그래밍은 큰 문제를 작은 문제로 나누어 해결하는 방법론 중 하나이다.

• 메모리 공간을 약간 더 사용하여 연산 시간을 획기적으로 줄일 수 있다는 장점이 있다.

• 다이나믹 프로그래밍은 다음과 같은 조건을 만족할때 사용할 수 있다.

  1. 최적 부분 구조

  : 큰 문제를 작은 문제를 나눌 수 있다. 이러한 작은 문제의 답을 모아 큰 문제를 해결할 수 있다.

  • 만약 서울에서 부산까지 가는 최단 경로를 찾는다고 생각해보자
  • 서울에서 부산까지 가는 길에 대구가 있고 서울에서 대구까지 가는 경로는 3가지, 대구에서 부산까지 가는 경로는 3가지가 있다.
  • 서울에서 부산까지 가는 최단 경로는 서울에서 대구까지 가는 최단 경로 + 대구에서 부산까지 가는 최단 경로가 될 것이다.

  2. 중복된 하위 문제

  : 동일한 작은 문제를 반복적으로 해결해야 한다.

  • 아래 피보나치 수열에서 설명

• 최적 부분 구조를 푸는 알고리즘으로는 그리디 알고리즘도 있다. 그리디 알고리즘은 항상 그 순간 최적이라고 생각되는 것을 선택하면서 풀이하는 것이고 다이나믹 프로그래밍은 중복된 하위 문제들의 결과를 저장해뒀다가 풀어나간다는 차이가 있다.

다이나믹 프로그래밍 방법론

• 다이나믹 프로그래밍의 방법론은 크게 상향식(Bottom-up)과 하향식(Top-Down)으로 나뉜다. 일반적으로 상향식을 Tabulation, 하향식을 memoizetion이라고 부른다.

상향식(Bottom-Up)

• 상향식은 더 작은 하위 문제부터 살펴본 다음 작은 문제의 정답을 이용하여 큰 문제의 정답을 풀어나간다.
• 예시 코드

def fib(n):
		dp[0] = 0
		dp[1] = 1

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

• 이와 같이 작은 하위 문제부터 차례로 정답을 풀어나가며 큰 문제의 정답을 만든다.

하향식(Top-Down)

• 하위 문제에 대한 정답을 계산했는지 확인해가며 문제를 자연스러운 방식으로 풀어나간다.
• 예시 코드

def fib(n):
		if n <= 1:
				return n

		if dp[n]:
				return dp[n]
		dp[n] = fib(n-1) + fib(n-2)
		return dp[n]

• 이와 같이 하위 문제에 대한 정답을 계산했는지 확인해가며 재귀로 풀어나간다. 기존 재귀 풀이와 거의 동일하면서도 이미 풀어봤는지 확인하여 재활용하는 효율적인 방식이다.