알고리즘 N 다이나믹프로그래밍 | DP | JS

기존 재귀의 문제점

이미지 출처

• ex) 피보나치 수열
• 일반적인 재귀를 사용하면 동일한 연산이 반복되어 비효율적임

DP를 통한 개선

function solution(n) {
  const table = []

  function fibonacci(n) {
    if (n == 0) {
      return 0;
    } else if (n == 1) {
      return 1;
    } else if (table[n]) {
      return table[n]
    } else {
      return table[n] = fibonacci(n - 1) + fibonacci(n - 2)
    }
  }
  return fibonacci(n)
}

다이나믹프로그래밍 | DP

• DP, 즉 다이나믹 프로그래밍(또는 동적 계획법)은 기본적인 아이디어로 하나의 큰 문제를 여러 개의 작은 문제로 나누어서 그 결과를 저장하여 다시 큰 문제를 해결할 때 사용하는 것으로 특정한 알고리즘이 아닌 하나의 문제해결 패러다임으로 볼 수 있다.

DP 조건

1) Overlapping Subproblems(겹치는 부분 문제)

DP는 기본적으로 문제를 나누고 그 문제의 결과 값을 재활용해서 전체 답을 구한다. 그래서 동일한 작은 문제들이 반복하여 나타나는 경우에 사용이 가능하다.

즉, DP는 부분 문제의 결과를 저장하여 재 계산하지 않을 수 있어야 하는데, 해당 부분 문제가 반복적으로 나타나지 않는다면 재사용이 불가능하니 부분 문제가 중복되지 않는 경우에는 사용할 수 없다.

2) Optimal Substructure(최적 부분 구조)

부분 문제의 최적 결과 값을 사용해 전체 문제의 최적 결과를 낼 수 있는 경우를 의미한다. 그래서 특정 문제의 정답은 문제의 크기에 상관없이 항상 동일하다!

만약, A - B까지의 가장 짧은 경로를 찾고자 하는 경우를 예시로 할 때, 중간에 X가 있을 때, A - X / X - B가 많은 경로 중 가장 짧은 경로라면 전체 최적 경로도 A - X - B가 정답이 된다.

📚 참고

YOUTUBE | 2015 봄학기 알고리즘 | 권오흠
알고리즘 - Dynamic Programming(동적 계획법)

Photo by Michael Dziedzic on Unsplash