Algorithms-[Dynamic_Programming]

동적프로그래밍을 단순하게 설명하면 큰 문제를 작은문제로 나누어 푸는 방법이다. 단 작은문제들이 계속 반복되어야 한다. 바뀌면 안된다. 동적프로그래밍에서는 메모이제이션(Memoiztion)이라는 방법을 쓰는데 이름에서도 유추할 수 있듯이 메모를 하듯 작은문제들의 답을 기억하여 사용하는 것이다. 동적프로그래밍의 가장 쉬운 예시 피보나치 수를 예로 들어보자. 피보나치 수의 공식은 아래와 같다.

위 처럼 F2를 구하기 위해서는 F1,F0이 필요하고, F3을 구하기 위해서는 F2, F1이 필요하다. 위의 저 공식처럼 계속해서 반복이 일어나며 공식을 찾기만하면 구할 때 마다 정답이 같다. 이렇듯 점화식같이 이전항과 다음항과의 관계를 알아내서 값을 기억하면서 다음 값을 찾아내는 것이 동적프로그래밍이다. 동적프로그래밍을 구현하는 방법에는 두 가지 방법이 있다. 첫번째는 BOTTOM-UP, 두번째는 TOP-DOWN이다.

BOTTOM-UP

BOTTOM-UP방법은 작은문제->큰문제로 풀어나가는 방법이다. 즉 맨첫항부터 시작해서 반복을 통해서 최종적인 문제를 풀어내는 것이다. 아래 피보나치 코드처럼 첫 예외항 F0과 F1을 구해놓은 뒤부터는 반복문을 통해서 최종적인 피보나치수들을 구해낸다. 

def fibonacci(n):
	p=[1,1]
	for i in range(2,n+1): 
		p.append(p[-1]+p[-2]) 
		print(p)
	return(p[-1])

TOP-DOWN

TOP-DOWN은 작은문제에 대해서 이미 이 문제를 해결했는지 확인하면서 문제를 풀어나가는 방법이다. 아래 코드와 같이 맨처음항부터 시작하는 것이 아니라 최종적으로 구하고자하는 값부터 확인하여 구해져있지 않으면 그 이전으로 돌아가고 메모하면서 푸는 재귀를 이용한 풀이법이다. 

dp=[0]*11
dp[0]=1
dp[1]=1

def fibonacci(n):
      
    if dp[n]==0:
        dp[n] = fibonacci(n-1)+fibonacci(n-2) 
    return dp[n]

두 상향식,하향식 풀이법중 어느것이 더 좋다는 것은 없으니 자기가 편한방법으로 풀면된다. 다만 파이썬은 재귀로 구현할 경우 메모리오류가 뜨는 경우가 많아서 bottom-up방식으로 문제푸는 것이 나는 개인적으로 편하고 이해하기 쉬웠던 것 같다.