동적 계획법(Dynamic Programming)

동적 계획법이란?

동적 계획법은 여러 개의 하위 문제를 풀고 그 결과를 기록하고 이용해서 문제를 해결하는 알고리즘이다. 

 

왜 써야할까?

동적 계획법을 왜 써야하는지에 대해 말하기전에 먼저 

피보나치 수 구하는 법에 대해 알아보자.

 

피보나치 수열

* 피보나치 수: 첫째 및 둘째 항이 1이며 그 뒤의 모든 항은 바로 앞 두 항의 합인 수열.

ex) 1, 1, 2, 3, 5, 8, ...

 

n번째 피보나치 수를 Fibo(n)으로 표현한다면

일단 Fibo(1)과 Fibo(2)는 1이다. 

Fibo(3)부터는 이전 값과 이전 이전 값의 합이 된다.

Fibo(3) = Fibo(1) + Fibo(2) = 1 + 1 + 2

그러면 

Fibo(4) = Fibo(3) + Fibo(2) = 2 + 1 = 3
Fibo(5) = Fibo(4) + Fibo(3) = 3 + 2 = 5
Fibo(6) = Fibo(5) + Fibo(4) = 5 + 3 = 8 ...

결국 n번째 피보나치 수는 이렇게 표현할 수 있다.

Fibo(n) = Fibo(n-1) + Fibo(n-2)

이런 비슷한 구조의 반복은 재귀 함수로 풀 수 있는데

코드로 풀어보면 다음과 같다. 

input = 20

def fibo_recursion(n):
    if n == 1 or n == 2:
        return 1
    return fibo_recursion(n-1) + fibo_recursion(n-2)

print(fibo_recursion(input))  # 6765

매우 간단해 보이지만 input의 값을 100으로 늘리면 연산이 너무 오래걸려 값이 나오질 않는걸 볼 수 있다.

무슨 이유일까?

Fibo(5)에 대한 예시인데, 이 그림만 봐도 아래에서 Fibo(2)에 대한 재귀 함수 연산이 반복되는걸 볼 수 있다.

이처럼 시켰던 일을 계속 반복 시키기 때문에 연산량이 늘어나게 되는 것이다.

그럼 했던 일은 따로 기록해서 같은 일이 반복될 때 다시 할 필요없이 값만 불러오는 방법을 쓰면 어떨까?

이게 바로 동적 계획법이다. 

 

동적 계획법

동적 계획법 용어 정리

메모이제이션(Memoization): 결과를 기록하는 것

겹치는 부분 문제(Overlapping Subproblem): 문제를 쪼갤 수 있는 구조

 

구현 방법

1. 메모용 데이터를 만든다. 처음 값인 Fibo(1), Fibo(2)는 각각 1씩 넣어서 저장해둔다.
2. Fibo(n)을 구할 때 만약 메모에 그 값이 있다면 바로 반환한다.
3. Fibo(n)을 처음 구했다면 메모에 그 값을 기록한다.

 

코드 구현

input = 50

# memo 라는 변수에 Fibo(1)과 Fibo(2) 값을 저장해놓음
memo = {
    1: 1,
    2: 1
}
# 1. 만약 메모에 있으면 그 값을 바로 반환
# 2. 없으면 f(n) = f(n-1) + f(n-2) 수식대로 구한다.
# 3. 그 값을 다시 메모에 기록한다.

def fibo_dynamic_programming(n, fibo_memo):
    if n not in fibo_memo.keys():
        fibo_memo[n] = fibo_dynamic_programming(n-1, fibo_memo) + fibo_dynamic_programming(n-2, fibo_memo)

    return fibo_memo[n]

print(fibo_dynamic_programming(input, memo))

 

정리

1. 반복되는 형태로 문제가 계속 파생 되는게 있다면 동적 계획법 쓸 생각을 하자.
2. 동적 계획법 쓸거면 메모이제이션을 하자

추가로, 위 코드처럼 f(100) -> f(99) -> f(98) -> ...  이런 위에서 아래로 내려가는 방식은 말 그대로

Top Down 방식이라고 부른다. 

반대로 f(1) -> f(2) -> ... 방식은 

Bottom Up 방식이라고 한다.