다이나믹 프로그래밍

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

 

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

중복되지 않은 문제들은 분할 정복 알고리즘으로 해결한다(대표적으로 퀵 정렬, 병합 정렬)

 

알고리즘	특징
다이나믹 프로그래밍	최적 부분 구조 중복된 하위 문제들
그리디 알고리즘	최적 부분 구조 탐욕 선택 속성
분할 정복	최적 부분 구조

 

최적 부분 구조는 어떤 것인가?

 

아래 그림에서 집1에서 집2로 가는 최단 경로를 찾는다고 가정하자.

집1에서 빌딩까지 가는 경로는 3가지, 빌딩에서 집2까지 가는 경로도 3가지가 있다.

집1에서 집2까지의 최단 경로는 집1에서 빌딩까지 가는 최단경로(5km) + 빌딩에서 집2까지 가는 최단경로(14km)이다.

즉, 집1-집2 최단경로는 각각의 부분문제인 집1-빌딩 최단경로 문제와 빌딩-집2 최단경로 문제에 대한 최적 해결 방법으로 구성된다.

 

이러한 구조를 최적 부분 구조라고 한다.

보통 최적 부분 유형은 분할 정복으로 풀 수 있으며, 다이나믹 프로그래밍, 그리디 일고리즘으로도 접근할 수 있다.

집1-빌딩-집2

 

중복된 하위 문제들이란?

 

다이나믹 프로그래밍과 그리디/분할 정복 알고리즘의 차이는 중복된 하위 문제들의 여부이다.

피보나치 수열이 다이나믹 프로그래밍 알고리즘으로 해결하는 이유가 중복된 하위 문제라는 특성이 존재하기 때문이다.

f(3)=f(2)+f(1)이고 f(4)=f(3)+f(2)이다. 이렇게 재귀로 풀면 반복적으로 동일한 하위 문제들이 발생한다.

피보나치 수열

 

 

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

• 상향식(Tabulation): 더 작은 하위 문제부터 살펴본 다음, 작은 문제의 정답을 이용해 큰 문제의 정답을 해결한다.
• 하향식(Memoization): 하위 문제에 대한 정답을 계산했는지 확인해가며 문제를 자연스러운 방식으로 풀어나간다.

 

피보나치 수열 상향식 풀이

: 데이터를 테이블 형태로 만들면서 문제를 풀이한다고 해서 Tabulation이라고 부른다.

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]

 

피보나치 수열 하향식 풀이

: 재귀 풀이와 동일하면서도 이미 풀어봤는지 확인하여 재활용하는 방식이다.

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]