[알고리즘] 다이나믹 프로그래밍 (Dynamic Programming)

ungnam·2025년 3월 20일

어떤 문제의 경우 메모리 공간을 약간 더 사용하면 연산 속도를 비약적으로 증가시킬 수 있는 방법이 있다. 대표적인 방법이 바로 다이나믹 프로그래밍(Dynamic Programming, DP) 기법으로, 동적 계획법이라고도 한다.

피보나치 수열과 다이나믹 프로그래밍

다이나믹 프로그래밍을 활용할 수 있는 대표적인 예시로 피보나치 수열이 있다. 피보나치 수열은 이전 두 항의 합을 현재의 항으로 설정하는 특징이 있으며, 점화식(인접한 항들 사이의 관계식)은 다음과 같다.

F(n) = F(n-1) + F(n-2) (n ≥ 3, F(1) = 1, F(2) = 1)

프로그래밍에서는 이러한 수열을 배열이나 리스트로 표현할 수 있다. 점화식을 재귀 함수로 구현하면 다음과 같다.

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

print(fibo(4)) # 3

그러나 위 코드에는 심각한 문제가 있다. n이 커질수록 수행 시간이 기하급수적으로 증가하기 때문이다. 시간 복잡도는 O(2^N)으로, 예를 들어 N = 30이면 약 10억 번의 연산이 필요하다.

중복 연산 문제

fibo(4)를 호출하면 fibo(2)가 2번 반복 호출된다. n이 커질수록 같은 값을 여러 번 중복 계산해야 하는 비효율의 발생 횟수가 증가한다.

이를 해결하기 위해 다이나믹 프로그래밍을 적용할 수 있다.

다이나믹 프로그래밍 적용 조건

다이나믹 프로그래밍을 사용할 수 있는 조건은 다음과 같다.

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

피보나치 수열은 이 조건을 만족하는 대표적인 문제로, 메모이제이션(Memoization) 기법을 활용하면 효율적으로 해결할 수 있다.

메모이제이션 (Memoization)

메모이제이션은 다이나믹 프로그래밍을 구현하는 방법 중 하나로, 한 번 계산한 결과를 저장하여 중복 계산을 방지하는 기법이다. 이를 캐싱(Caching)이라고도 한다.

d = [0] * 100  # 메모이제이션을 위한 리스트

def fibo(x):
  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)) # 218922995834555169026

이제 시간 복잡도는 O(N)으로 줄어든다. 한 번 구한 값은 다시 계산하지 않기 때문이다.

보텀업 vs 탑다운

다이나믹 프로그래밍에는 두 가지 접근법이 있다.

1. 탑다운(Top-Down, 하향식)

큰 문제를 해결하기 위해 작은 문제를 호출하는 방식
재귀 함수를 사용하며, 메모이제이션 기법과 함께 사용됨

2. 보텀업(Bottom-Up, 상향식)

작은 문제부터 차근차근 답을 도출하는 방식
보통 반복문을 이용하여 구현함

일반적으로 보텀업 방식이 성능이 더 좋다. 재귀를 사용할 경우 스택 오버플로우(Stack Overflow) 위험이 있기 때문이다.

보텀업 방식 구현 (DP 테이블 활용)

d = [0] * 100

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

for i in range(3, n + 1):
  d[i] = d[i - 1] + d[i - 2]

print(d[n]) # 218922995834555169026

보텀업 방식에서는 DP 테이블을 활용해 결과를 저장한다. 이 방식의 시간 복잡도는 역시 O(N)이다.

다이나믹 프로그래밍과 분할 정복의 차이

다이나믹 프로그래밍은 분할 정복(Divide & Conquer)과 유사하지만, 차이점이 있다.

개념	특징
분할 정복	문제를 작은 문제로 나누고, 나눈 문제를 각각 해결한 후 합치는 방식 (예: 퀵 정렬)
다이나믹 프로그래밍	작은 문제들이 서로 영향을 미치므로, 한 번 해결한 문제를 다시 풀지 않도록 저장함

분할 정복의 대표적 예시인 퀵 정렬의 경우 피벗을 기준으로 분할하면 피벗의 위치는 더 이상 바뀌지 않고 그 피벗값을 다시 처리하는 부분 문제는 존재하지 않는다. 그러나 다이나믹 프로그래밍 문제들은 한 번 해결했던 문제를 다시금 해결한다는 점이 특징이므로, 해결된 값을 저장하는 것이 핵심이다.

다이나믹 프로그래밍을 적용하는 방법

주어진 문제가 다이나믹 프로그래밍 유형인지 파악한다.
- 완전 탐색으로 접근했을 때 시간이 오래 걸린다면 DP를 고려해본다.
- 해결하려는 부분 문제들이 중복되는지 확인한다.
재귀 함수(탑다운)로 비효율적인 프로그램을 작성한다.
- 메모이제이션을 적용하여 개선할 수 있으면 DP 가능성이 높다.
가능하면 보텀업 방식으로 구현한다.
- 재귀 함수의 스택 크기 제한 때문에 sys.setrecursionlimit()을 설정해야 할 수도 있다.
- 반복문을 사용한 보텀업 방식이 일반적으로 더 효율적이다.