다이나믹 프로그래밍(DP)이란? 개념 잡기

본 글은 나동빈님의 "이것이 코딩테스트다"를 참고해서 제 공부 차원에서 기록한 것입니다.

다이나믹 프로그래밍(Dynamic Programming)이란 메모리 공간을 약간 더 사용하여 연산 속도를 비약적으로 증가시키는 대표적인 방법이다. 다이나믹 프로그래밍에는 top-down과 bottom-up 2가지 방식이 있다.

다이나믹 프로그래밍을 본격적으로 알아보기 전 피보나치 수열에 대해 살펴보자. 아래는 재귀 함수로 피보나치 수열을 구현한 것이다.

def fibo(x):
    if x == 1 or x == 2:
        return 1
    return fibo(x-1) + fibo(x-2)
    
print(fibo(4))

위와 같은 코드는 $f(n)$ 함수에서 n이 커지면 커질수록 수행 시간이 기하급수적으로 늘어난다. 시간 복잡도가 $O(2^N)$이기 때문이다. 이때 다이나믹 프로그래밍을 사용하면 효율적으로 해결할 수 있다. 다만 아래의 조건을 만족할 때 사용 가능하다.

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

메모이제이션(Memoization)은 다이나믹 프로그래밍을 구현하는 방법 중 한 종류로, 한 번 구한 결과를 메모리 공간에 저장하고 같은 식을 다시 호출하면 저장한 결과를 그대로 가져오는 것이다. 값을 저장하는 방식이기 때문에 캐싱(Caching)이라고도 한다.

d = [0] * 100 # 메모이제이션 리스트 초기화

# Top-down 다이나믹 프로그래밍
def fibo(x):
  # 종료 조건(1 or 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))

이미 해결된 부분 문제에 대한 답을 저장해 놓고, 이 문제는 이미 해결된 것이니 다시 해결할 필요가 없다고 반환하는 것이다. 이때 시간 복잡도는 $O(N)$인데, 이유는 한 번 구한 결과는 다시 구하지 않기 때문이다. 즉 f(1)을 구한 다음 이것이 f(2)를 푸는 데 사용되고, f(2) 값은 f(3)을 푸는 데 사용된다.

함수가 종료될 때 어떤 함수를 호출했는지, 현재 피보나치 수를 출력하는 코드를 참고하기 바란다.

d = [0] * 100

def fibo(x):
  print('f('+str(x)+')', end=' ')
  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(6))

이와 같이 재귀 함수 기반의 다이나믹 프로그래밍은 top-down 방식이다. 큰 문제를 해결하기 위해 작은 문제를 호출하기 때문이다. 반면, 단순히 반복문을 이용하여 코드를 작성하는 경우 작은 문제부터 차근차근 답을 도출한다고 하여 bottom-up 방식이라고 한다.

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

d[1] = 1
d[2] = 1
n = 99

# Bottom-up 다이나믹 프로그래밍
for i in range(3, n+1):
  d[i] = d[i-1] + d[i-2]

print(d[n])