[알고리즘] 다이나믹 프로그래밍(JS)

c_yj·2023년 2월 16일
0

알고리즘

목록 보기
4/4

다이나믹 프로그래밍이란?(Dynamic Programming) ⁉

다이나믹 프로그래밍(Dynamic Programming)은 복잡한 문제를 해결하기 위한 알고리즘 기법 중 하나로, 작은 문제들을 풀어나가면서 전체 문제를 해결하는 방식입니다. 다이나믹 프로그래밍은 주로 반복적인 작업이 발생하는 문제에 사용됩니다.
다이나믹 프로그래밍의 핵심 개념은 "메모이제이션(Memoization)"입니다. 메모이제이션은 이전에 계산한 결과를 저장하고 재사용하는 것을 의미합니다. 이를 통해 중복 계산을 줄일 수 있어, 프로그램 실행 속도를 빠르게 할 수 있습니다.

  • 문제를 부분 문제로 분할합니다.
  • 부분 문제를 풀고, 이를 메모이제이션 합니다.
  • 저장된 부분 문제들을 결합하여 원래 문제를 풉니다.

메모이제이션과 상향식 계산법

메모이제이션(Memoization)과 상향식 계산법(Top-down and Bottom-up) 모두 다이나믹 프로그래밍에서 사용되는 방법 중 하나다. 이 두 방법은 모두 중복 계산을 피하고 실행 속도를 빠르게 하는데 도움이 되는데. 어떨 떄 사용하는게 좋을지 알아보자

메모이제이션은 상향식 계산법(Top-down)의 일종으로, 재귀적인 방식으로 문제를 해결하는 방법입니다. 이전에 계산한 결과를 저장하고 재사용함으로써 중복 계산을 피합니다. 메모이제이션은 필요한 부분만 계산하므로, 실행 시간이 매우 빠르고, 코드 작성이 쉽습니다. 하지만, 스택 메모리를 많이 사용하여 스택 오버플로우 문제가 발생할 수 있습니다.

반면에, 상향식 계산법(Top-down)은 문제를 작은 문제부터 해결해 나가는 방법입니다. 작은 문제를 해결하면서 그 결과를 저장하여, 큰 문제를 해결할 때 재사용합니다. 이 방법은 메모리를 효율적으로 사용하며, 스택 오버플로우 문제를 방지할 수 있습니다. 그러나 코드 작성이 복잡하고, 실행 시간이 좀 더 오래 걸릴 수 있습니다.

❗ 따라서 메모리 사용량이 적은 상황이라면 메모이제이션이 유리하며, 스택 오버플로우 문제가 예상되는 상황이라면 상향식 계산법이 더 적합하다

예시

피보나치 수열

피보나치 수열은 이전 두 개의 항을 더한 값을 다음 항으로 하는 수열입니다. 예를 들어, 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ... 순서로 증가합니다.

재귀적으로 해결하면 다음과 같이 사용한다

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

하지만 이 함수는 n이 커질수록 계산 시간이 기하급수적으로 증가하게 됩니다.
이럴 때 다이나믹 프로그래밍을 사용하면 좋다.

function fibonacci(n) {
  const memo = [0, 1];
  for (let i = 2; i <= n; i++) {
    memo[i] = memo[i - 1] + memo[i - 2];
  }
  return memo[n];
}

위에 코드에서는 memo 배열을 생성하여 이전에 계산한 값을 저장 이를 통해 중복 계산을 피하고, 실행 속도를 빠르게 할 수 있습니다.

두 코드의 시간 복잡도를 계산해보면

재귀 함수를 사용한 피보나치 수열 계산의 시간 복잡도는 n에 대해 O(2^n)의 계산 복잡도 가진다
반면에 다이나믹 프로그래밍을 사용한 피보나치 수열 계산의 시간 복잡도 n에 대해 O(n)의 계산 복잡도를 가진다

profile
FrontEnd Developer

0개의 댓글