알고리즘, Dynamic Programming

 

동적 프로그래밍(Dynamic Programming, DP)은 복잡한 문제를 더 작은 하위 문제로 나누어 해결하는 알고리즘 설계 기법입니다. 이 기법은 하위 문제의 해를 재사용하여 전체 문제의 해를 구하는 데 사용됩니다. 동적 프로그래밍은 주로 최적화 문제를 해결하는 데 사용되며, 두 가지 중요한 속성을 가집니다: 최적 부분 구조(Optimal Substructure)와 중복 부분 문제(Overlapping Subproblems).

동적 프로그래밍의 개념

1. 최적 부분 구조(Optimal Substructure):
   • 큰 문제의 최적 해가 그 부분 문제의 최적 해로부터 유도될 수 있는 속성을 의미합니다.
   • 예를 들어, 최단 경로 문제에서 전체 경로의 최적 해는 그 경로를 구성하는 부분 경로들의 최적 해로 구성될 수 있습니다.
2. 중복 부분 문제(Overlapping Subproblems):
   • 동일한 부분 문제가 여러 번 반복하여 계산되는 속성을 의미합니다.
   • 동적 프로그래밍은 이러한 중복 계산을 피하기 위해 이미 계산된 값을 저장하고 재사용합니다.

동적 프로그래밍의 접근 방식

1. 탑다운(메모이제이션, Memoization):
   • 재귀적 접근 방식으로, 문제를 재귀적으로 나누고, 각 하위 문제의 결과를 저장하여 필요할 때 다시 사용합니다.
   • 필요할 때 계산하므로, 처음에는 계산하지 않고 요청 시 계산하여 캐시에 저장합니다.
2. 바텀업(테이블링, Tabulation):
   • 반복적 접근 방식으로, 작은 하위 문제부터 차례로 해결하면서 상위 문제를 해결합니다.
   • 모든 하위 문제를 미리 계산하여 테이블에 저장하고, 이를 사용해 상위 문제를 해결합니다.

동적 프로그래밍 예제

피보나치 수열

피보나치 수열은 동적 프로그래밍의 대표적인 예입니다. 피보나치 수 \(F(n)\)은 다음과 같이 정의됩니다:

피보나치 수열을 최적화 없이 사용할 경우 시간 복잡도는 O(2^n) 입니다.

 

출처 [https://cs.slides.com/colt_steele/dynamic-programming#/29]

 

function fib(n) {
  if (n <= 2) return 1;

  return fib(n - 1) + fib(n - 2);
}

console.log(fib(2)); // 13

메모이제이션을 사용한 피보나치 수열 (탑다운 방식)

function fib_memo(n, memo = []) {
  if (memo[n] !== undefined) return memo[n];
  if (n <= 2) return 1;

  const res = fib(n - 1, memo) + fib(n - 2, memo);
  memo[n] = res;

  console.log('memo:', memo);

  return res;
}

console.log(fib_memo(10));

/**
 * memo: [ <3 empty items>, 2 ]
 * memo: [ <3 empty items>, 2, 3 ]
 * memo: [ <3 empty items>, 2, 3, 5 ]
 * memo: [ <3 empty items>, 2, 3, 5, 8 ]
 * memo: [ <3 empty items>, 2, 3, 5, 8, 13 ]
 * memo: [ <3 empty items>, 2, 3, 5, 8, 13, 21 ]
 * memo: [ <3 empty items>, 2, 3, 5, 8, 13, 21, 34 ]
 * memo: [ <3 empty items>, 2, 3, 5, 8, 13, 21, 34, 55 ]
55
 */

테이블링을 사용한 피보나치 수열 (바텀업 방식)

function fib_tabulation(n) {
  if (n <= 2) return 1;
  let fibNums = [0, 1, 1];
  for (let i = 3; i <= n; i++) {
    fibNums[i] = fibNums[i - 1] + fibNums[i - 2];
  }

  console.log('fibNums:', fibNums);

  return fibNums[n];
}

console.log(fib_tabulation(10));

/**
 * fibNums: [
   0, 1,  1,  2,  3,
   5, 8, 13, 21, 34,
  55
]
 */

동적 프로그래밍의 특징

1. 시간 복잡도 개선: 중복 계산을 피하고, 각 하위 문제를 한 번만 계산하므로 시간 복잡도가 크게 개선됩니다.
2. 공간 복잡도: 메모이제이션이나 테이블을 저장하는 데 필요한 추가 공간이 필요하지만, 시간 복잡도 개선에 비해 큰 이점이 있습니다.
3. 적용 범위: 최적화 문제, 경로 찾기 문제, 부분 집합 문제 등 다양한 문제에 적용할 수 있습니다.