다이나믹 프로그래밍

어떤 문제를 해결하는데 시간이 매우 많이 필요하거나 메모리 공간이 매우 많이 필요한 문제는 컴퓨터로도 해결하기 어렵다. 그래서 연산 속도와 메모리 공간을 최대한 활용할 수 있는 효율적인 알고리즘을 작성해야 한다.

다만, 어떤 문제는 메모리 공간을 약간 더 사용하면 연산 속도를 비약적으로 증가시킬 수 있는 방법이 있다. 대표적인 방법이 바로 다이나믹 프로그래밍이다. 

 

여기 일반적인 피보나치 수열 코드가 있다.

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

그런데 피보나치 수열의 소스코드를 이렇게 작성하면 심각한 문제가 생길 수 있다. 바로 n이 커질수록 수행 시간이 기하급수적으로 늘어나기 때문이다. 이 소스코드의 시간 복잡도는 O(2^n)의 지수 시간이 소요된다. n=30이면 약 10억 가량의 연산을 수행해야 하고 n=100이면 수백억 년을 넘어가는 시간이 나온다.

 

이러한 문제는 다이나믹 프로그래밍을 사용하면 효율적으로 해결할 수 있는데, 다음 조건을 만족해야 한다.

1. 큰 문제를 작은 문제로 나눌 수 있다.
2. 동일한 작은 문제를 반복적으로 해결한다.

피보나치 수열은 두 조건을 만족하는 대표 문제이다.

 

탑다운 vs 보텀업

다이나믹 프로그래밍의 방식은 두 가지가 있다. 바로 탑다운, 보텀업 방식이다.

 

탑다운 방식은 하향식이라고도 하며 메모이제이션이라고 부른다. 메모이제이션은 한 번 구한 결과를 메모리 공간에 메모해두고 같은 식을 다시 호출하면 메모한 결과를 그대로 가져오는 기법을 의미한다. 메모이제이션은 값을 저장하는 방법이므로 캐싱이라고도 한다. 주로 재귀함수를 사용한다. 엄밀히 말하면 메모이제이션은 이전의 계산된 결과를 일시적으로 기록해 놓는 넓은 개념을 의미한다. 따라서 메모이제이션은 다이나믹 프로그래밍에 국한된 개념은 아니다.

 

보텀업 방식은 상향식이라고도 하며 반복문을 이용하여 작은 문제부터 차근차근 답을 도출한다. 다이나믹 프로그래밍의 전형적인 형태는 보텀업 방식이다. 이 때, 결과 저장용 리스트를 DP테이블이라고 부른다.

 

<하향식 - 재귀 함수>

# 한 번 계산된 결과를 메모이제이션(Memoization)하기 위한 리스트 초기화
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))

 

<상향식 - 반복문>

# 앞서 계산된 결과를 저장하기 위한 DP 테이블 초기화
d = [0] * 100

# 첫 번째 피보나치 수와 두 번째 피보나치 수는 1
d[1] = 1
d[2] = 1
n = 99

# 피보나치 함수(Fibonacci Function) 반복문으로 구현(보텀업 다이나믹 프로그래밍)
for i in range(3, n + 1):
    d[i] = d[i - 1] + d[i - 2]

print(d[n])

 

다이나믹 프로그래밍을 통한 피보나치 수열 문제는 O(n)이다.

 

다이나믹 프로그래밍 문제에 접근하는 방법

다이나믹 프로그래밍과 분할 정복은 모두 큰 문제를 작은 문제로 나눌 수 있으며 작은 문제의 답을 모아서 큰 문제를 해결할 수 있는 상황에서 사용할 수 있다.

 

다이나믹 프로그래밍과 분할 정복의 차이점은 부분 문제의 중복이다.

다이나믹 프로그래밍에서는 각 부분 문제들이 서로 영향을 미치며 부분 문제가 중복된다.

분할 정복 문제(ex. 퀵 정렬)에서는 동일한 부분 문제가 반복적으로 계산되지 않는다.

 

일반적인 코딩 테스트 수준에서는 다이나믹 프로그래밍 문제는 대체로 간단한 형태로 출제된다. 그렇다면 어떻게 다이나믹 프로그래밍 문제 유형임을 알 수 있을까?

 

가장 먼저 그리디, 구현, 완전 탐색 등의 아이디어로 문제를 해결할 수 있는지 검토한다. 예를 들어, 완전 탐색을 통해 문제에 접근하는데 시간 복잡도가 매우 크게 나온다면 다이나믹 프로그래밍을 고려할 수 있다.(부분 문제들의 중복 여부를 확인해본다.)

 

일단 재귀 함수로 비효율적인 완전 탐색 프로그램을 작성한 뒤에(탑다운) 작은 문제에서 구한 답이 큰 문제에서 그대로 사용될 수 있으면, 메모제이션을 통해 코드를 개선하는 방법을 사용할 수 있다.

 

또한 가능하다면 재귀 함수를 이용하는 탑다운 방식보다는 보텀업 방식으로 구현하는 것을 권장한다. 시스템상 재귀 하수의 스택 크기가 한정되어 있을 수 있기 때문이다.

 

+) 만약 다이나믹 프로그래밍 유형으로 푼다면 점화식을 생각해보자.