알고리즘 - 동적 계획법이란?

동적 계획법

• 부분 문제들의 답을 어딘가에 저장해 놓고 필요할 때 다시 꺼내서 사용하는 전략
• 같은 부분 문제를 다시 풀지 않도록 하는 전략

메모이제이션을 이용한 피보나치 수열

• 메모이제이션: 함수의 결과를 저장할 메모리를 미리 준비해서 한번 계산한 값을 저장해 두었다가 재활용하는 방법

def fib_dp_mem(n) :
    if mem[n] == None :		    # 풀리지 않은 경우-> 계산하고 저장
        if n < 2 :
            mem[n] = n			# 기반 상황: n<=1
        else: 					# 일반 상황: otherwise
            mem[n] = fib_dp_mem(n-1) + fib_dp_mem(n-2)	
    return mem[n]

• 시간 복잡도는 $O(n)$으로 분할 정복의 $O(2^n)$과 비교하면 매우 효율적인 알고리즘
• 공간복잡도도 $O(n)$

테이블화를 이용한 피보나치 수열

• 부분 문제의 해를 메모리에 저장한다는 점은 메모이제이션과 같지만, 테이블 항목들을 순서대로 채워나가는 것에 초점을 맞춘다
• 상향식(bottom-up)으로 문제를 해결
• 가장 작은 부분 문제부터 순서대로 해를 구해 테이블을 채워서 올라간다

def fib_dp_tab(n) :
    f = [None] * (n+1)			# 테이블을 만들고
    f[0] = 0					# 기반 상황 처리
    f[1] = 1					# 기반 상황 처리
    for i in range(2, n + 1):	# 상향식으로: 2, 3, ... n
        f[i] = f[i-1] + f[i-2]	# 부분 문제들을 해결하고 저장함
    return f[n]					# 결과 반환

• 시간 복잡도 $O(n)$, 공간 복잡도 $O(n)$

동적계획법을 이요한 문제 해결 전략

• 분할 정복 전략을 적용할 수 있어야 함
• 피보나치 수열처럼 중복된 문제를 반복해서 해결하는 경우여야 함
• 최적 부분 구조 특성이 있어야 함
• 최적 부분 구조 특성: 부분 문제의 최적해를 이용하면 전체 문제를 해결할 수 있는 구조를 의미