[Python]동적계획법

동적계획법

• 다이나믹 프로그래밍(Dynamic Programming,DP)라고도 불리며, 하나의 큰 문제를 여러 개의 공통되는 작은 문제로 나누어서 작은 문제의 정답들을 결합하여 알고리즘을 푸는 과정

동적계획법 접근방법

• Bottom Up 방법 : 작은 문제에서 큰 문제로 반복문 호출
• Top Down 방법 : 큰 문제에서 작은 문제로 재귀 호출

동적계획법 활용

피보나치 수열

• Bottom Up

def fib(n):
	fibList=[1,1]
    for i in range(2,n+1):
    	fibList.append(fibList[i-2]+fibList[i-1)
    return fbList[-1]

• Top Down

def fib(n):
	if n==0 or n==1:
    	return 1
   	else:
    	return fib(n-1)+fib(n-2)

메모이제이션(memoization)

• 앞에서 한 계산을 어딘가에 저장해두고 필요한 경우 불러와서 사용할 수 있도록하여 중복된 계산이 발생 하는것을 방지하는 기법
• 배열 혹은 해시를 활용하는 것이 핵심

memo={0:1,1:1}
def fib(n):
	if n in memo:
    	return memo[n]
    else:
    	result=fib(n-1)+fib(n-2)
        memo[n]=result
        return reslt

동적계획법 예시

data[3,4,5,6,1,2,5]
이웃하지 않는 숫자들의 합의 최댓값은?

def solution(data):
	if len(data)==1:
    	return data[0]
   	result= [data[0],max(data[0],data[1]) #메모이제이션할 배열 선언 
    for i in range(2,len(data)):
    	result.append(max(result[i-1],result[i-2]+data[i])
    return result[-1]