• 최적화 문제를 해결하기 위한 알고리즘 설계 기법
• 문제를 여러 하위 문제로 나누어 해결하고, 중복되는 하위 문제들을 한 번만 계산하여 중복 계산을 피하는 방법을 사용한다.
  * 큰 규모의 문제를 해결할 때 용이

핵심 아이디어

• 작은 크기의 하위 문제들을 해결한 결과를 저장해두었다가, 이를 이용하여 더 큰 크기의 문제들을 해결하는 것.
• 하위 문제들을 푸는 과정에서 발생하는 중복 계산을 피할 수 있다 => 시간 복잡도 GOOD

충족 요건

1. 최적 부분 구조(Optimal Substructure): 큰 문제의 최적해는 작은 문제의 최적해로부터 구할 수 있어야 함.
2. 중복되는 하위 문제(Overlapping Subproblems): 문제를 반복적으로 해결하는 과정에서 동일한 작은 문제가 여러 번 발생해야 함.

접근법

상향식 접근법 (Top-Down)

큰 문제를 작은 하위 문제로 쪼개면서 문제를 해결하는 방식.

재귀 함수 혹은 메모이제이션을 통해 구현된다.

메모이제이션

계산한 값을 저장해두었다가 필요할 때 재사용하는 기법 -> 동일한 하위 문제의 반복적인 호출 x.

하향식 접근법 (Bottom-Up)

작은 하위 문제부터 시작하여 점진적으로 큰 문제를 해결하는 방식.

작은 문제들의 해를 계산하여 더 큰 문제들의 해를 구하는 방식.

반복문.

어떤 문제에 적용할 수 있나?

1. 중복 계산이 발생하는 문제
   • 동일한 계산이 반복적으로 수행되는 문제 (예: 피보나치: f(n-1) + f(n + 2) )
2. 작은 부분 문제로 분할될 수 있는 문제
   • 큰 문제를 작은 부분 문제를 나눌 수 있는 문제 (예: 피보나치: f(n-1) + f(n-2) )
3. 부분 문제의 최적해가 전체 문제의 최적해에 영양을 미치는 문제
   • 부분 문제의 해답을 이용하여 전체 문제의 최적해를 구할 수 있는 문제 (예: 배낭 문제)

위와 같은 특징을 가진 문제인지 먼저 살펴봐야한다.

문제를 작은 부분 문제로 분할하고, 부분 문제의 해답을 메모이제이션하거나 재귀적으로 계산하여 저장하는 방식으로 구현해야 한다.

기존의 중복 계산을 피하고 문제를 효율적으로 해결할 수 있다.

대표적인 적용 문제

피보나치 수열

// 0 1 1 2 3 5 8 13 21 34 55 89 144 . . .

function fibo1(n) {
  if (n === 1 || n === 2) {
    return 1;
  } else {
    return fibo1(n - 1) + fibo1(n - 2);
  }
}

function fibo2(n) {
  const fiboArray = [0, 1, 1];
  
  for (let i = 3; i <= n; i++) {
    fiboArray[i] = fiboArray[i - 1] + fiboArray[i - 2];
  }

  return fiboArray[n];
}

let fiboMemo = {};

function fibo3(n) {
  if (n === 1 || n === 2) {
    return 1;
  }
  if (fiboMemo[n]) {
    return fiboMemo[n];
  }

  fiboMemo[n] = fibo3(n - 1) + fibo3(n - 2);

  return fiboMemo[n];
}

  

// fibo 함수의 실행 시간 측정
performance.mark("startFibo");
console.log(fibo1(20));
performance.mark("endFibo");
performance.measure("executionTimeFibo", "startFibo", "endFibo");
const measureFibo = performance.getEntriesByName("executionTimeFibo")[0];
console.log(`fibo Execution time: ${measureFibo.duration}ms`);

// fibo2 함수의 실행 시간 측정
performance.mark("startFibo2");
console.log(fibo2(20));
performance.mark("endFibo2");
performance.measure("executionTimeFibo2", "startFibo2", "endFibo2");
const measureFibo2 = performance.getEntriesByName("executionTimeFibo2")[0];
console.log(`fibo2 Execution time: ${measureFibo2.duration}ms`);

// fibo3 함수의 실행 시간 측정
performance.mark("startFibo3");
console.log(fibo3(20));
performance.mark("endFibo3");
performance.measure("executionTimeFibo3", "startFibo3", "endFibo3");
const measureFibo3 = performance.getEntriesByName("executionTimeFibo3")[0];
console.log(`fibo3 Execution time: ${measureFibo2.duration}ms`);