동적 계획법

의미

• "어떤 문제를 풀기 위해 그 문제를 더 작은 문제의 연장선으로 생각하고, 과거에 구한 해를 활용하는" 방식의 알고리즘을 의미함

의사코드

• 문제를 더 작은 문제로 나누되, 작은 문제를 최대한 많이 이용하도록 한다.
• 작은 문제의 답을 한 번만 연산하고 따로 저장해둔다.
• 다시 한 번 작은 문제를 연산할 때 저장해둔 답을 바로 산출하여 이용함
  👉🏼 불필요한 연산을 줄임으로써 연산 속도를 높임

예시

피보나치 수열을 구하는 문제를 동적 계획법으로 구현해보자.

의사코드

1. 재귀함수를 활용해서 풀기
2. 단, 이미 연산한 결과는 prevalue라는 배열에 n 인덱스 자리에 저장하기

코드 작성해보기

function fibonacci(n, prevalue = []) {
  //이미 수행한 연산이면 저장된 값 불러오기
  if(prevalue[n] !== undefined) return prevalue[n]
  
  let result;
  
  if(n <= 1) {
    result = n;
  }else {
    result =  fibonacci(n-2, prevalue) + fibonacci(n-1, prevalue);
  }
  
  //수행한 연산은 배열 prevalue에 n 인덱스 자리에 저장
  prevalue[n] = result;
  
  return result
}

참고자료
동적계획법, 나무위키