[Algorithm] DP (Dynamic Programming)

동적 계획 (DP; Dynamic Programming)

• 그리디 알고리즘과 같이 최적화 문제를 해결하는 알고리즘
• 입력 크기가 작은 부분 문제들을 모두 해결한 후에 그 해들을 이용하여 보다 큰 크기의 부분 문제들을 해결

 

Memoization

• 피보나치 수열을 재귀함수로 구현하는 경우 '엄청난 중복 호출이 존재한다'는 문제점이 있음

def fibo(n): 
    if n < 2: 
        return 2 
    else: 
    	return fibo(n-1) + fibo(n-2)

• 메모이제이션 (Memoization)
  • 컴퓨터 프로그램을 실행할 때 이전에 계산한 값을 메모리에 저장해서 매번 다시 계산하지 않도록 하여 전체적인 실행 속도를 빠르게 하는 기술
  • 동적 계획법의 핵심이 되는 기술
  • 앞의 예에서 fibo(n)의 값을 계산하자마자 저장하면(memoization) 실행시간을 Θ(n)으로 줄일 수 있음

def fibo(n):
    f = [0, 1]

    for i in range(2, n-1):
        f.append(f[i-1] + f[i-2])

    return f[n]