<PART 2> 다이나믹 프로그래밍

다이나믹 프로그래밍, 동적 계획법: 연산속도와 메모리공간 최대한 활용하는 방법

이는 중복되는 연산을 줄일 수 있습니다.
다이나믹 프로그래밍의 기본적인 아이디어를 먼저 소개한 후에 2가지 방식인 탑다운, 바텀업을 설명할 것입니다.

여기서의 다이나믹의 뜻은 '프로그램이 실행되는 도중에'라는 의미입니다.
다이나믹 프로그래밍으로 해결할 수 있는 대표적인 예시로 피보나치 수열이 있습니다.  

우선 피보나치 수열을 코드로 간단한게 표현하면 다음과 같습니다.

이처럼 단순히 재귀함수를 사용하여서 해결할 수 있습니다. 그러나 여기서 n이 기하급수적으로 커지면 시간 표기법이 O(2^N)정도로 올라가서 심각한 문제가 생길 수 있습니다.

항상 다이나믹 프로그래밍을 사용할 수 없으며, 다음 조건을 만족할 때 사용할 수 있습니다.

1. 큰 문제를 작은 문제로 나눌 수 있다.
2. 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일하다.

이때 사용할 수 있는 것이 메모이제이션(Memoization) 기법입니다.
메모이제이션은 다이나믹 프로그래밍을 구현하는 방법 중 한 종류로, 한 번 구한 결과를 메모리 공간에 메모해두고 같은 식을 다시 호출하면 메모한 결과를 그대로 가져오는 기법을 의미합니다. 메모이제[이션은 값을 저장하는 방법이므로 캐싱(Cashing)이라고도 합니다.
구현방법은 매우 단순합니다. 한 번 구한 정보를 리스트에 저장하면 됩니다. 다이나믹 프로그래밍은 재귀적으로 수행하다가 같은 정보가 필요할 때는 이미 구한 정답을 그대로 리스트에서 가져오면 됩니다.

#한번 계산된 결과를 메모이제이션하기 위한 리스트 초기화
d = [0]*100
 
#피보나치 함수(Fibonacci Function)를 재귀함수로 구현(탑다운 다이나믹 프로그래밍)
def fibo(x):
    #종료 조건(1 혹은 2일 때 1을 반환)
    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]
print(fibo(99))

위와 같이 재귀 함수를 이용하여 다이나믹 프로그래밍 소스코드를 작성하는 방법을, 큰 문제를 해결하기 위해 작은 문제를 호출한다고 하여 탑다운 방식이라고 말합니다.

위의 소스코드의 실행과정은 위의 그림과 같다. 맨 왼쪽부터 진행된 다음 남은 fibo들이 실행된다.

- 바텀업 방식
반대로 단순히 반복문을 이용하여 소스코드를 작성하는 경우 작은 문제부터 차근차근 답을 도출한다고 하여 바텀업 방식이라고 말한다.

다이나믹 프로그램의 전형적인 형식은 바텀업 방식입니다. 바텀업 방식에서 사용되는 결과 저장용 리스트는 'DP 테이블'이라고 부르며 메모이 제이션은 탑 다운 방식에 국한되어 사용되는 표현입니다.
다이나믹 프로그래밍 과 메모이제이션의 개념을 혼용해서 사용하는 경우도 있는데, 엄밀히 말하면 메모이제이션은 이전에 계산된 결과를 일시적으로 기록해 놓는 넓은 개념을 의미하므로, 다이나맥 프로그래밍과는 별도의 개념입니다. 한번 계산된 결과를 어딘가에 담아 놓기만 하고 다이나믹 프로그래밍을 위해 활용하지 않을 수도 있습니다.

문제를 푸는 첫 번째 단계는 주어진 문제가 다이나믹 프로그래밍 유형임을 파악하는 것입니다.
특정한 문제를 완전 탐색 알고리즘으로 접근 했을 때 시간이 매우 오래 걸리면 다이나믹 프로그래밍을 적용할 수 있는지 해결하고자 하는 부분 문제들의 중복 여부를 확인해봅니다.
가능하다면 탑다운보다는 바텀업 방식으로 구현하는 것을 권장한다. 시스템 상 재귀함수의 스택크기가 한정되어 있을 수 있기 떄문이다.