- JavaScript Algorithms and Data Structures Masterclass(Udemy Course)

• 동적 프로그래밍은 문제를 더 작은 단위로 쪼갠 뒤, 각각을 해결한 결과를 저장하여 같은 부분 문제를 마주했을 때 다시 연산하지 않고 저장된 결과를 불러와 복잡도를 줄이는 방법이다.

• 다시 정리하자면, 동적 프로그래밍은 아래의 두 조건을 충족하는 문제에만 적용이 가능하다.

  • 중복 부분 문제(overlapping subproblems)

  • 최적 부분 구조(optimal substructures)

중복 부분 문제

• 그림에서 보이듯이 여러번 계산되는 부분 문제들이 있는데, 이를 두고 중복 부분 문제라 한다.

최적 부분 구조

• 위의 예시처럼 어떤 문제의 해결책을, 그 문제의 부분 문제들의 해결책을 사용하여 찾을 수 있을 때 해당 문제는 최적 부분 구조를 가진다고 한다.

피보나치 수열

피보나치 수열1 (일반적인 재귀)

function fibo(n) {
  if (n < 0) {
    throw Error("유효하지 않은 숫자입니다");
  }
  if (n <= 1) {
    return n;
  }
  return fibo(n - 2) + fibo(n - 1);
}

• 앞서 중복 부분 문제의 예시로 든 피보나치 수열의 풀이 방법으로, 시간복잡도가 2의 n승에 해당한다.

• 이미 계산을 한 값일지라도 다시 반복해서 계산하는 것이 문제이므로, 다시 마주칠 계산에 대해서 '기억'하면 중복된 계산을 줄일 수 있다.

• 이러한 작업을 '메모이제이션'이라고 한다.

피보나치 수열2 (메모이제이션)

function fibo(n, memo = {}) {
  debugger;
  if (n <= 1) {
    return n;
  }
  if (memo.hasOwnProperty(n)) {
    return memo[n];
  }
  const result = fibo(n - 2, memo) + fibo(n - 1, memo);
  memo[n] = result;
  return result;
}

• 이전의 일반 재귀문이 모든 재귀 함수 호출에 대하여 계산을 수행해야 한 반면,

• 메모이제이션에서는 표시된 부분의 계산만 수행하면 나머지 함수 호출에 대해서는 그저 메모에서 불러오기만 하면 된다.

• 따라서 시간 복잡도는 n이다.

• 앞서 메모이제이션은 top-down방식이었다.

• 이와 반대로 bottom-up에 해당하는 타뷸레이션 방식도 있다.

피보나치 수열3 (타뷸레이션)

function fibo(n) {
  if (n <= 1) {
    return n;
  }
  const fiboNums = [0, 1];
  for (let i = 2; i <= n; i++) {
    debugger;
    fiboNums[i] = fiboNums[i - 2] + fiboNums[i - 1];
  }
  return fiboNums[n];
}

• 타뷸레이션 방식 역시 시간 복잡도는 n이다.

• 앞서의 메모이제이션 방식은 재귀를 이용한 방식이므로 n이 일정 수를 넘어가면 Stack Overflow를 발생시킨다.

• 반면, 타뷸레이션의 방식은 하나의 콜스택 안에서 이루어지므로 적어도 n의 크기가 함수의 실행에 영향을 미칠 일은 없다.

피보나치 수열4 (꼬리재귀)

function fibo(n, former = 0, latter = 1) {
  if (n < 0) {
    throw Error("유효하지 않은 숫자입니다");
  }
  if (n == 0) {
    return former;
  }
  if (n == 1) {
    return latter;
  }
  return fibo(n - 1, latter, former + latter);
} 

• 아마 동적 프로그래밍과는 관련이 없는 것 같은데 피보나치 수열을 푸는 또 하나의 방법이라 추가했다.

• 앞서 1, 2번의 피보나치 수열 풀이법이 함수의 반환부에서 재귀 함수를 양방향으로 호출했던 반면,

• 이 피보나치 수열은 재귀 함수의 호출 자체를 n번 하게끔 설계되어있다.
  (시간 복잡도 = n)