[알고리즘] 다이나믹 프로그래밍

다이나믹 프로그래밍

다이나믹 프로그래밍(Dynamic Programming)기법은 동적계획법이라고도 하는데, 메모리공간으 더 사용해서 연산속도를 증가시킬 수 있는 알고리즘이다.

 

• 탑다운 방식
• 보텀업

두가지 방식이 있다.

 

다이나믹 프로그래밍을 사용할 수 있는 조건

• 큰 문제를 작은 문제로 나눌 수 있을때
• 작은 문제에서 구한 답이 작은 문제를 포함하는 큰 문제에서도 답이 동일할 때

 

대표적인 예시로 피보나치 수열로 설명을 할 수 있다.

 

피보나치 수열은 이전 두항의 합이 현재의 항이 되는 수열이다.

1 1 2 3 5 8 13 21 34 55 ...

이런식으로 말이다.

 

이를 점화식으로 표현하면

an=an-1+an-2, a1=1, a2=1

 

단순히 코드로 표현하면 

def fibo(a)i :
	if a==1 or a==2: 
    	return 1
    return fibo(a-2)+fibo(a-1)

이런식이 될 것이다. 근데 이때 문제점은 숫자가 커질수록 기하급수적으로 연산량이 커진다는 것이다. 

시간복잡도는 O(2의N승)이 되는데 반복된 연산량이 많아 비효율적이다.

fibo(5)를 계산하기 위해서 f(3)이 두번 호출되는것과 같이 말이다.

이렇게 반복적인 계산을 줄이기 위해 사용하는 것이 바로 다이나믹 프로그래밍이다.

 

메모제이션(memozations) : 한번 구한 결과를 메모리 공간에 저장해서 다시 호출하면 가져오는 기법. 캐싱(caching)이라고도 불림

-탑다운 방식에서 사용되는 표현

 

메모제이션기법을 사용해서 해결해보자!

 

 

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]

이렇게 d라는 리스트에 한번 계산된 결과를 메모제이션하는 것이다!

이렇게 하면 시간복잡도는 O(N)이 되어 훨씬 효율적으로 문제를 해결할 수 있다

 

위와 같이 재귀함수를 사용해서 푸는 방식이 탑다운 방식이라고 한다!

->큰 문제를 해결하기 위해 작은 문제를 호출하기 때문

 

d=[0]*100

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

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

단순 반복문을 사용한 위 같은 방식을 보텀업 방식이라고 한다

보텀업에서 사용되는 결과 저장용 리스트는 dp 테이블이라고한다. 

 

재귀함수의 스택크기가 제한되어있을 수 있기 때문에 탑다운보단 보텀업 방식을 이용하도록 노력하자

 

 

※해당 포스팅은 <이것이 취업을 위한 코딩테스트다 (나동빈 저)>를 참고하여 작성되었습니다.