Dynamic Programming(동적계획법)이란?

하나의 문제를 단 한 번만 풀도록 하는 알고리즘

일반적으로 상당 수의 분할 정복 기법은 동일한 문제를 다시 푸는 단점이 있습니다. 이는 단순 분할 정복 으로 풀게 되면 심각한 비효율성을 낳습니다.

Dynamic Programming 방법과 조건

• 방법: 모든 작은 문제들을 한번만 풀어야하므로, 정답을 구한 작은 문제를 어딘가에 메모하고 다른 큰 문제가 생길 때, 작은 문제가 나타나면 앞서 메모한 작은 문제의 결과값을 이용합니다.
• 조건: 큰 문제를 작은 문제로 나눌 수 있습니다.
  작은문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일합니다.

메모이제이션(Memoization)을 사용하여 이미 계산된 결과는 배열에 저장하여 나중에 동일한 계산을 해야 할 때는 저장된 값을 단순히 반환하여 문제를 해결합니다.

---

피보나치 수열

피보나치 수열을 예를 들어서 보면 피보나치는 1,1,2,3,5, ...의 수를 이루게 됩니다. 즉 다음수열값 = 이전 수열 + 두단계 전 수열의 합입니다.

조건 1. 작은 문제들이 반복합니다.

피보나치 수열의 5번째를 구하기 위해서는 3번째와 4번째의 값이 필요합니다. 그리고 4번째 값을 구하기 위해서는 2번째, 3번째 값이 필요합니다. 이와 같은 경우에 5번째 값을 구하기 위해서 3번째 값이 필요하고 4번째의 값을 구하기 위해서도 3번째 값이 필요한 것을 알 수 있습니다

조건 2. 같은 문제는 구할때 마다 정답이 같다.

피보나치 수열의 경우 첫번째, 두번째 수열은 1로 고정이기때문에 3번째 수열의 값은 언제나 3입니다. 또 4번째 수열은 2번째, 3번째 값을 구하므로 정답이 같다는 사실을 알 수 있습니다.

피보나치 수열 구현 (Memoization X)

하기와 같이 출력하여도 문제는 없으나, 피보나치 수가 늘어날수록 컴퓨터에서 함수를 호출하는 횟수가 2의 n제곱이 되므로 메모이제이션이 사용되어야합니다.

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

console.log(getFibonacci(5))

피보나치 수열 구현 (Memoization O)

하기와 같이 코드 구현시 이미 계산된 결과의 경우 배열 arr에 저장되기 때문에 한 번 구한 값을 다시 구하는 일이 없습니다.

let arr = [0];
function getFibonacci(n){
  if (n<=2){
    return 1;
  }
  if(!arr[n]){ // 내가 저장한 값 중에 없다면...
    arr[n] = getFibonacci(n-1) + getFibonacci(n-2);
  }
  return arr[n];
}

console.log(getFibonacci(5));