동적 프로그래밍 (Dynamic Programming)

같은 계산을 반복하는 것은 비효율적이다. 예를 들어 피보나치 수열에서 fib(5)를 계산할 때, fib(3)을 여러 번 중복 계산한다.
한 번 계산한 결과를 저장해두면 훨씬 빠를 것이다.

이것이 바로 동적 프로그래밍(Dynamic Programming)의 핵심 개념이다.

 

동적 프로그래밍 (Dynamic Programming)

동적 프로그래밍은 복잡한 문제를 작은 부분 문제로 나누어 해결하고, 그 결과를 저장하여 중복 계산을 방지하는 알고리즘 기법이다.

동적 프로그래밍은 크게 두 가지 방식으로 구현할 수 있다.

	메모이제이션	타뷸레이션
방식	하향식 (Top-down)	상향식 (Bottom-up)
구현	재귀 + 캐싱	반복문 + 테이블
계산	필요한 값만 계산	모든 값을 미리 계산
메모리	스택 + 캐시 공간	테이블 공간만

문제: 피보나치 수열

피보나치 수열을 예시로 두 방식을 비교해보자.
피보나치 수열: 0, 1, 1, 2, 3, 5, 8, 13, 21, ...

• fib(0) = 0
• fib(1) = 1
• fib(n) = fib(n-1) + fib(n-2)

 

일반적인 재귀 (비효율적)

먼저 동적 프로그래밍 없이 단순 재귀로 구현해보자.

function fibonacci1(n) {
  if (n == 0 || n == 1) {
  return fibonacci1(n - 2) + fibonacci1(n - 1);
  }

  let start = new Date();
  console.log(fibonacci1(40));  // 102334155

  let end = new Date();
  console.log(`실행시간: ${end - start}ms`);  //  실행시간: 980ms
}

 

문제점은 fib(5)를 계산할 때:

fib(5)
= fib(4) + fib(3)
= (fib(3) + fib(2)) + (fib(2) + fib(1))
= ((fib(2) + fib(1)) + (fib(1) + fib(0))) + ((fib(1) + fib(0)) + fib(1))

fib(3)이 2번, fib(2)가 3번 중복 계산된다. 시간복잡도는 O(2^n) 으로 매우 비효율적이다.

 

메모이제이션 (Memoization)

계산 결과를 저장해서 여러 번 계산하지 않도록 하는 기법이다.
하향식(Top-down) 방식으로, 큰 문제를 작은 문제로 나누며 필요한 값만 계산한다.

구현 코드

function fibonacci2(n, memo) {
  if (n == 0 || n == 1) return n;

  // 이미 계산한 값이 있으면 재사용
  if (memo[n] == null) {
    memo[n] = fibonacci2(n - 2, memo) + fibonacci2(n - 1, memo);
  }

  return memo[n];
}

let start = new Date();
console.log(fibonacci2(40, {}));  // 102334155
let end = new Date();
console.log(`실행시간: ${end - start}ms`);  // 실행시간: 1ms

980ms → 1ms로 엄청난 성능 향상을 확인할 수 있다.

 

장점

• 재귀 덕분에 하향식 계산 방식으로 어려운 문제를 간단하게 해결할 수 있음
• 중복 계산을 하지 않아서 속도가 빠름
• 필요한 값만 계산하므로 불필요한 계산을 하지 않음

단점

• 재귀 호출로 인한 스택 메모리 사용
• 메모이제이션을 위한 추가 메모리(해시 테이블) 필요

 

타뷸레이션 (Tabulation)

작은 문제부터 시작해 점진적으로 큰 문제를 해결하는 상향식(Bottom-up) 계산 방식이다.
재귀 없이 반복문으로 구현하며, 모든 값을 미리 계산해 테이블에 저장한다.

구현 코드

function fibonacci3(n) {
  if (n == 0 || n == 1) return n;

  let table = [0, 1];  // 초기값 설정

  // 작은 문제부터 순서대로 계산
  for (let i = 2; i <= n; i++) {
    table[i] = table[i - 2] + table[i - 1];
  }

  return table[n];
}

let start = new Date();
console.log(fibonacci3(40));  // 102334155
let end = new Date();
console.log(`실행시간: ${end - start}ms`);  // 실행시간: 0ms

1ms → 0ms으로 메모이제이션보다도 빠르다.

 

동작 과정

fib(%)를 계산한다고 가정해보자.

 

초기: table = [0, 1]

 

i = 2:

table[2] = table[0] + table[1] = 0 + 1 = 1
table = [0, 1, 1]

i = 3:

table[3] = table[1] + table[2] = 1 + 1 = 2
table = [0, 1, 1, 2]

i = 4:

table[4] = table[2] + table[3] = 1 + 2 = 3
table = [0, 1, 1, 2, 3]

i = 5:

table[5] = table[3] + table[4] = 2 + 3 = 5
table = [0, 1, 1, 2, 3, 5]

 

결과: 5

 

장점

• 상향식 계산 방식으로 모든 값을 전부 계산 후 테이블에 저장
• 재귀 호출 없이 반복문을 사용해 스택 오버플로우 위험이 없음
• 메모리 사용량이 적고 실행 속도가 빠름

단점

• 필요 없는 값까지 모두 계산할 수 있음
• 재귀에 비해 직관적이지 않을 수 있음

 

메모이제이션 vs 타뷸레이션

성능 비교

	실행 시간	메모리 사용
일반 재귀	980ms	적음 (스택만)
메모이제이션	1ms	많음 (스택 + 해시 테이블)
타뷸레이션	0ms	보통 (테이블만)

 

어느 것을 선택해야 할까?

상황에 따라 적합한 방식이 다르다.

메모이제이션이 유리한 경우

• 복잡한 문제를 직관적으로 해결할 수 있는 재귀적 구조가 명확할 때
• 하향식 접근이 문제 해결에 더 자연스러울 때
• 모든 부분 문제를 계산할 필요 없이 필요한 값만 계산하면 되는 경우

메모이제이션은 재귀의 직관성을 유지하면서 중복 계산을 제거해 성능을 크게 개선한다. 더 많은 메모리를 사용하지만, 복잡한 문제를 쉽게 해결할 수 있다는 장점이 있다.

 

타뷸레이션이 유리한 경우

• 재귀적 접근이 직관적이지 않거나 불필요할 때
• 모든 부분 문제의 해가 필요한 경우
• 메모리 효율과 실행 속도 모두 중요한 경우
• 스택 오버플로우 위험을 피하고 싶을 때

타뷸레이션은 상향식으로 필요한 모든 값을 미리 계산해 테이블에 저장하므로, 적은 메모리로 더 빠른 성능을 낼 수 있다.

 

결론적으로, 분할 정복 문제에서 재귀가 직관적이라면 메모이제이션을, 그렇지 않다면 타뷸레이션을 선택하는 것이 좋다.

 

동적 프로그래밍의 활용 사례

동적 프로그래밍은 다음과 같은 문제에서 자주 사용된다.

1. 피보나치 수열: 가장 기본적인 예제
2. 최단 경로 문제: 다익스트라, 플로이드-워셜 알고리즘
3. 배낭 문제(Knapsack): 제한된 용량에서 최대 가치 찾기
4. 최장 공통 부분 수열(LCS): 두 문자열의 공통 부분 찾기
5. 동전 교환 문제: 최소 동전 개수로 거스름돈 만들기

 

동적 프로그래밍은 복잡한 문제를 작은 부분 문제로 나누어 해결하는 강력한 기법이다.

메모이제이션(하향식)과 타뷸레이션(상향식) 두 가지 방식이 있으며, 문제의 특성에 따라 적합한 방식을 선택해야 한다. 중복 계산을 제거하여 O(2^n)의 지수 시간을 O(n)으로 줄일 수 있어, 최적화 문제 해결에 필수적인 알고리즘이다.