[알고리즘] Dynamic Programming

✅ 동적계획법 (Dynamic Programming)

❕ 기본 개념 

- 복잡한 문제를 간단한 여러 개의 문제로 나누어 푸는 방법

- 일반적인 재귀 방식과 매우 유사하지만, 작은 문제들이 여러번 반복되는 비효율적인 계산을 피할 수 있음

 

해당 알고리즘이 필요한 문제의 조건은 아래와 같다.

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

: DP는 문제를 작은 문제들로 나누고 그 결과값들을 재활용해서 전체 답을 구한다. 따라서 동일한 부분 문제들이 반복하여 나타나고, 부분 문제가 중복되는 경우에 사용 가능하다.

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

: 부분 문제의 최적 결과 값을 사용해 전체 문제의 최적해를 낼 수 있는 경우를 의미한다.

 

 

❕ 작동 방식 

 

피보나치 수열 구현: 재귀 vs. DP

DP를 통해 시간복잡도는 O(n²)  → O(f(n))으로 개선됨

 

 

✔ 활용 예시 

- 최장 공통 부분 수열: 두 개 이상의 수열의 공통 부분수열 중 가장 긴 수열을 찾는 알고리즘

- 배낭 문제: 조합 최적화

- 벨먼-포드 알고리즘

- 다익스트라 알고리즘: 시작점과 다른 점들 사이의 최단경로를 찾아내는 알고리즘

 

✔ 문제 예시 

- 피보나치 수열

- 최단 경로 문제

 

 

✔ 구현 방법 (JS) 

1. Top-down with Memoization

const fibWithMemo = (n) => {
  let memo = {}; // we will store("memoize") our values here
 
  const fib = (n) => {
    let value;
 
    if (n in memo) {
      // if the n is already in our memo object, we look it up and store it in value
      value = memo[n];
    } else {
      // otherwise, we calculate it and store it in value
      if (n === 1 || n === 2) {
        value = 1;
      } else {
        value = fib(n - 1) + fib(n - 2);
      }
      // store the value for current n to our memo object
      memo[n] = value;
    }
    console.log(memo);
    return value;
  };
  return fib(n);
};

 

2. Bottom-up with Tabulation

const fibWithTab = (n) => {
  if (n === 1 || n === 2) return 1;
  // initialize an array and store the values we already know
  let fibNums = [0, 1, 1];
  // loop starting at index 3 (first value we do not know) until n
  for (let i = 3; i <= n; i++) {
    // store values in the array at Nth index
    fibNums[i] = fibNums[i - 1] + fibNums[i - 2];
  }
  return fibNums[n];
};

 

 

참고자료

https://ko.wikipedia.org/wiki/동적_계획법

https://hongjw1938.tistory.com/47

https://www.geeksforgeeks.org/dynamic-programming/

https://medium.com/swlh/demystifying-dynamic-programming-b22d65095866