다이나믹 프로그래밍(DP)

→ Open in Slid

• 본 글은 이전에 사용하던 영상 강의 필기 앱인 'Slid'에서 필기 했던 내용을 Velog로 옮긴 내용입니다.

---

다이나믹 프로그래밍이란, 하나의 문제를 단 한번만 풀도록 하는 알고리즘이다.

분할 기법(퀵 정렬, 병합 정렬 이진검색)의 단점 극복을 위해 사용하는 알고리즘.

• 분할 기법의 단점은 동일한 문제를 반복해서 푼다는 것이다.
• ex) 피보나치 수열

const fibonacci = (n) => {
  if (n === 1) return 1;
  if (n === 2) return 1;
  return fibonacci(n - 2) + fibonacci(n - 1);
};

• 1) 처음에 50을 입력받으면, 어느 길이든 간에 종착지는 n이 2 또는 1일 때이다. 그리고 50번째까지 계속 더해지고 더해져서 최종 결과를 출력할 것이다.
• 2) 그래서 시간복잡도가 2^n이 되게 된다. (너무 오래 걸림)
• 3) 그래서 이를 해결하기 위해 다이나믹 프로그래밍을 이용해야 하는데, 이를 위해 메모이제이션(저장장치)이 필요하다.
• * 계산한 값을 미리 저장한다면? 계산할 필요 없이 그냥 꺼내쓰기만 하면 된다!

const memory = [0];

const fibonacci = (n) => {
    if(n === 1) return 1;
    if(n === 2) return 1;
    if(memory[n] !== null) return memory[n];
    
return memory[n] = fibonacci(n-1) + fibonacci(n-2)
}

• 이미 계산된 결과는 배열 d에 저장된다.