[파이썬/python] 동적계획법 (Dynamic Programming)

동적계획법, Dynamic Programming은 아래 두 조건을 만족할 때 사용한다.

1. 최적 부분 구조 : 큰 문제를 작은 문제로 나눌 수 있으며 작은 문제의 답을 모아 큰 문제를 해결
2. 중복 부분 구조 : 동일한 작은 문제를 반복적으로 해결

다이나믹 프로그래밍은 그리디 알고리즘과 같이 최적화 문제를 해결하는 알고리즘으로

상향식 접근이며 메모이제이션을 핵심 기술로 사용한다.

 

메모이제이션(Memoization)이란, 동일한 계산을 반복해야 할 때 이전에 계산한 값을 메모리에 저장함으로써

동일한 계산을 반복하지 않도록하여 실행속도를 빠르게 하는 기술이다.

 

피보나치 수열이나 재귀함수에서 유용하게 쓰이며 점화식을 찾는게 중요하다.

문제의 순환적인 성질을 이용하기 때문에 점화식을 이용하여 재귀적으로 정의해야 한다.

가장 작은 부분 문제부터 해를 구한 뒤 저장하고 그 해를 이용하여 더 큰 문제의 해를 구하는 방식이다.

 

 

파이썬으로 구현하기

# 메모이제이션 : 작은 문제의 해를 저장할 리스트
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]

피보나치 수를 찾는 방법을 다이나믹 프로그래밍을 이용하여 구현해보았다.

1. 점화식을 찾아 재귀적으로 정의한다.

fibo(x - 1) + fibo(x - 2)

피보나치 수의 점화식은 위와 같으므로 fibo함수를 이용해 재귀적으로 정의하였다.

 

2. 작은 부분 문제의 해를 메모이제이션을 이용하여 저장한다.

d = [0] * 100

d[x] = fibo(x - 1) + fibo(x - 2)

저장할 공간인 d를 만들고 x값에 대한 피보나치 수의 값을 d에 저장한다.

 

3. 원하는 값의 해가 저장되어 있다면, 값을 계산하지않고 저장된 값을 return한다.

if d[x] != 0:
        return d[x]

종료조건에 해당하지 않는 수 x에 대하여 d에 x에 대한 값이 저장되어 있는지 확인한 후,

저장되어 있다면 d[x]를 return 한다.