[알고리즘] 동적 프로그래밍(Dynamic Programming)

동적 프로그래밍(Dynamic Programming)이란?

동적 프로그래밍이란 큰 문제를 작은 문제로 나누어 푸는 문제를 말하며, 작은 부분문제들이 반복되는 것을 이용해 풀어나가는 방법이다. 모든 작은 문제들은 한번만 풀어야 한다. 그보다 큰 문제를 풀어나갈 때 똑같은 작은 문제가 나타나면 미리 구해놓은 작은 문제의 결과값을 이용한다.

 

동적 프로그래밍과 일반적인 재귀방식은 매우 비슷하다. 큰 차이점은 일반적인 재귀를 단순하게 사용했을 경우 작은 문제들이 여러 번 반복되어 비효율적인 계산이 될 수 있다는 것이다. 이 차이점이 바로 동적 프로그래밍을 사용하는 이유이다. 동적 프로그래밍을 사용하면 앞서 계산된 값을 다시 반복할 필요가 없어 매우 효율적으로 문제를 해결할 수 있게 된다.

 

동적 프로그래밍의 조건은 다음과 같다.

  - 작은 문제가 반복이 일어나는 경우

  - 작은 문제들의 답이 바뀌지 않는 경우

 

동적 프로그래밍 사용 과정

동적 프로그래밍의 일반적인 사용 과정은 다음과 같다.

 

1) 동적 프로그래밍의 조건을 만족하는지 확인 -> DP로 풀 수 있는 문제인지 확인

2) 변수 간 관계식(점화식) 만들기

3) 변수의 값에 따른 결과 저장하기(Memoization)

4) 기저 상태 파악하기 -> 미리 배열에 저장해두는 등

5) 구현하기 -> Bottom-up / Top-down

 

메모이제이션(Memoization)

동적 프로그래밍은 앞서 말했든 작은 문제들이 반복되고 이 작은 문제들의 결과값이 바뀌지 않는다. 이을 이용해 한 번 계산한 작은 문제들을 저장해놓고 그보다 큰 문제를 풀 때 다시 사용하는데 이를 메모이제이션(Memoization)이라 한다.

 

구현 방법

구현 방법은 진행 방향에 따라 크게 두 가지로 나눌 수 있다. 

 

1. Bottom-up

Bottom-up 방식은 작은 문제부터 차근차근 구해나가는 방법이다.

주로 반복문을 사용해 구현하며 Tabulation 방식이라 불리기도 한다.

 

2. Top-down

Top-down 방식은 큰 문제를 풀다가 아직 해결되지 않은 작은 문제를 만났을 경우 그제서야 작은 문제를 해결하는 방법이다. 재귀함수로 구현하는 경우가 대부분 Top-down 방식이며 Memoization 방식이라 불리기도 한다. 

 

대표적인 예제로는 피보나치 수열이 있다.

d = [0] * 50
def fibo(n):
    if n == 1 or n == 2:
        return 1
    if d[n] != 0:
        return d[n]
    d[n] = fibo[n-1] + fibo[n-2]
    return d[n]