알고리즘 - 동적계획법(다이나믹 프로그래밍 / DP)

*참고저서 <이것이 취업을 위한 코딩테스트다>

 

동적 계획법은 일반적으로 해결한 문제에 비해 수행시간을 비약적으로 줄일 수 있는 방법으로 알려져있다.

동적계획법의 핵심은 '중복된 연산을 줄이는 것' 이다.

 

def fibo(x) ：
	if x == 1 or x == 2： 
		return 1
	return fibo(x - 1) + fibo(x - 2)

잘 알려진 수열인 피보나치 수열의 경우 재귀적으로 손쉽게 구현할 수 있지만 이는 상당히 비효율적인 방법이라,

실제로 데이터가 커지면 수행시간이 기하급수적으로 증가하게 된다.

그 이유는 낮은 숫자에 대한 fibo()값들이 수도 없이 다시 계산되기 때문이다. 실제로 이러한 풀이는 지수시간, 즉 O(2^n)의 수행시간을 가진다.

 

따라 이미 계산한 부분해(fibo(x)의 경우 x 이하 모든 수들에 대한 fibo())을 저장해두어 다시 계산하는 일이 없게 하는 것이다.

 

동적계획법은 크게 두 가지 방법으로 나눌 수 있는데, 탑다운(Top-down)방식과 바텀업(Bottom-up)방식이 그것이다.

 

1. 탑다운

 

말그대로 위에서 아래로, 즉 더욱 큰 해를 해결하기 위해 작은 문제들을 계속 호출하는 방식이다.

solution(x)를 해결한다면 x -> 0 (혹은 base case)의 방향으로 해결하는 방식이다.

d = [0] * 100 

def pibo(x) ：
  if x == 1 or x == 2： 
  	return 1 
  if d[x] != 0： 
  	return d[x]
  d[x] = pibo(x - 1) + pibo(x - 2)
  return d[x]

print(pibo(99))

 

2. 바텀업

 

조금 더 범용적으로 사용되는 동적계획법의 방법이다. 반복문을 이용해 가장 작은 문제부터 하나씩 해결하며

최종해에 다가가는 방식이다. 아래 코드에서는 d[3]부터 차근차근히 d[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]
    
print(d[n])