[Python] 다이나믹 프로그래밍 (DP)

다이나믹 프로그래밍이란?

복잡한 문제를 간단한 여러 개의 문제로 나누어 푸는 방법을 의미한다^[각주:1].

 

문제를 여러 개의 하위 문제로 나누어 푼 다음, 그 결과들을 결합하여 답을 구한다. 특정 범위까지의 값을 구하기 위해서 그것과 다른 범위까지의 값을 이용하여 효율적으로 값을 구하는, 메모리 공간을 조금 더 사용함으로 연산 속도를 늘릴 수 있는 알고리즘 설계 기법이다.

 

예시

이렇게 글로만 보면 확 와닿지 않는다. 그럼 예시를 한 번 보도록 하자.

 

다이나믹 프로그래밍(이하 DP)으로 해결할 수 있는 대표적인 문제 예시로 피보나치 수열이 있다. n번째 피보나치 수는 n-1번째 수 더하기 n-2번째 수이다. 이걸 정리하면 f(n) = f(n-1) + f(n-2)이다. 

 

def fibo(n):
    if n == 0:
        return 0
    elif n <= 2:
        return 1
    return fibo(n-1) + fibo(n-2)

 

 

 

일반적인 재귀함수를 사용하여 5번째 피보나치 수를 찾으려 한다. 코드 실행 순서를 정리하면 위와 같이 되는데, 5번째 수를 구하기 위해서 총 15번의 호출을 해야 하는 것이다. 그런데 그림을 잘 보면 fibo(3)이나 fibo(2) 같이 동일한 함수가 반복적으로 호출되는 것을 알 수 있다. 이미 계산되었음에도 불구하고 호출이 있을 때마다 계속 계산하는 것이다. 

 

이 문제를 해결하기 위해 메모이제이션(Memoization) 기법을 사용하는 것이다. 이 기법은 DP를 구현하는 방법 중 하나로, 이미 구한 함수의 값을 저장하고 그 함수가 호출될 때마다 계산 없이 그 값을 반환하는 기법이다. 

 

ans = [0] * (n+1)
ans[1] = 1
ans[2] = 1

def fibo(n):
    for i in range(3, n+1):
        ans[i] = ans[i-1] + ans[i-2]
    return ans[n]

 

ans라는 정답 배열(DP 테이블)을 만든 뒤, 인덱스를 n이라 가정한 뒤, for문으로 n번째 수까지 피보나치 수를 저장해 둔다. 이처럼 반복문을 사용하는 경우는 작은 문제부터 답을 구한다 하여 보텀업(Bottom-up), 상향식 방식이라고 한다. 

 

ans = [0] * (n + 1)  

def fibo(n):
    if n <= 2 and n > 0:
        ans[n] = 1
    if ans[n] != 0:
        return ans[n]
    ans[n] = fibo(n-1) + fibo(n-2)
    return ans[n]

 

이처럼 재귀 함수를 사용하여 큰 문제를 해결하기 위해 작은 문제를 호출한다고 하여 탑다운(Top-Down), 하향식 방식이라고 한다. 

 

DP의 전형적인 형태는 보텀업 방식이다. 보텀업 방식에서 사용되는 결과 저장용 리스트는 DP 테이블이라고 부르며, 메모이제이션은 탑다운 방식에 국한되어 사용되는 표현이다. DP와 메모이제이션의 개념을 혼용해서 사용하는 경우도 있는데, 엄밀히 말하면 메모이제이션은 이전에 계산된 결과를 일시적으로 기록해 놓는 넓은 개념을 의미하므로, DP와는 별도의 개념이다. 
- <이것이 취업을 위한 코딩 테스트다 with 파이썬> 나동빈 저 p.215

 

메모이제이션과 DP의 개념을 헷갈렸는데 혼동하지 않도록 하자. 

 

메모이제이션: 이전에 계산된 결과를 저장하는 기법

DP: 복잡한 문제를 간단한 여러 개의 문제로 나누어 푸는 알고리즘 설계 기법

활용

이처럼 DP는 효율적이나, 아래의 조건들을 충족하는 상황일 때만 사용할 수 있다.

 

문제를 작은 문제들로 나눌 수 있으며, 작은 문제의 정답을 구하는 방법과 큰 문제의 정답을 구하는 방식이 동일할 때 사용할 수 있다.

---

 

1. https://ko.wikipedia.org/wiki/%EB%8F%99%EC%A0%81_%EA%B3%84%ED%9A%8D%EB%B2%95 [본문으로]