[알고리즘] 다이나믹 프로그래밍(동적 계획법) - javascript

✅ 다이나믹 프로그래밍이란?

큰 문제를 작은 문제로 쪼개 결과값을 저장해서 점차 큰 문제를 해결하는 방식

💡 사용 조건

1. Overlapping Subproblems (겹치는 부분 문제)
   동일한 작은 부분이 반복하여 나타나야 함

2. Optimal Substructure (최적 부분 구조)
   작은 문제의 최적 결과 값을 사용해 큰 문제의 최적 결과값을 낼 수 있는 경우

💡 다른 알고리즘과의 차이점

1. 재귀
   재귀는 단순히 작은 문제들을 반복적으로 불러내어 비효율적임.
   다이나믹 프로그래밍은 문제를 해결한 값을 저장해서 다시 호출하지 않음.

2. 분할 정복
   분할 정복도 큰 문제를 작은 문제로 쪼개 해결하지만, 작은 문제들이 중복되지 않고 독립적

📌 예시 - 피보나치 수열

피보나치 수열은 F(0) = 0, F(1) = 1일 때, 1 이상의 n에 대하여 F(n) = F(n-1) + F(n-2) 가 적용되는 수

• F(2) = F(0) + F(1) = 0 + 1 = 1
• F(3) = F(1) + F(2) = 1 + 1 = 2
• F(4) = F(2) + F(3) = 1 + 2 = 3
• F(5) = F(3) + F(4) = 2 + 3 = 5

💡 재귀만 사용한 구현

코드는 단순하지만, 스택오버플로우가 발생할 확률이 큼

• 시간 복잡도: O(2^n)

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

💡 다이나믹 프로그래밍을 사용한 풀이

1. Memoization(메모이제이션) - Bottom-up 방식 (👍)
   문제의 아래부터 위로 값을 쌓아올리며 최종값에 도달함 => 루프로 순회함

   • 시간 복잡도: O(N)

   function fib(n) {
     let arr = [0, 1];
     for (let i = 2; i <= n; i++) {
         arr.push(arr[i-1] + arr[i-2]);
     }
     return arr[n] ;
   }

2. Tabulation(타뷸레이션) - Top-down 방식
   문제의 상단부터 시작하여, 아래의 값을 호출하며 내려오며 값을 저장
   => 재귀를 사용하기 때문에 스택 오버 플로우 발생함

   • 시간 복잡도: O(N)

function fib(n, memo=[undefined,1,1]) {
  if(memo[n] !== undefined) return memo[n];
  memo[n] = fib(n-1, memo) + fib(n-2, memo);
  return memo[n];
}

보너스

알고리즘 문제에서 결과값이 특정 숫자로 나눈 나머지로 설정되있다면?

=> 숫자가 엄청나게 커져서 메모리를 차지하게 되므로 int 자료형의 범위 내에 항상 값이 있을 수 있도록 한 배려임

자세한 설명

피보나치 수는 f(50)만 되도 수가 엄청나게 커져 메모리에 저장할 수 없기 때문에, 스택오버플로우가 발생한다.

그래서 문제에 리턴값이 어떤 숫자 n으로 나눈 나머지 값으로 나와있는 경우가 많다.

속 뜻은 수가 너무 커서 메모리가 감당 못할테니 나눠서 저장해라~ 라는 말과 같다.

위 과정은 저장된 수를 다시 꺼내 활용하고, 또 저장하는 방식이기 때문에 ( f(3)은 저장된 f(1)과 f(2)를 호출한다 )

원 값이 아닌 나눈 나머지를 저장해도 되는 것인가? 하는 의문이 들 수 있다.

(A + B) % C ≡ ( ( A % C ) + ( B % C) ) % C

이 식은 그래도 된다는 것을 말해준다.

나눠서 저장한 뒤, 호출해서 다시 더하고 나눠도 그 값이 같다는 것이다.

• 참고
  프로그래머스 질문글
  onlydev.tistory.com