Dynamic Programming

Dynamic Programming은 전체Dynamic Programming은 전체 문제를 여러 개의 하위 문제로 나누어 풀고,
하위 문제들의 해결 방법들을 결합하여 최종 문제를 해결하는 문제 해결 방식이다.

최종 문제를 해결하는 많은 방법들을 모두 탐색하게 된다.
하위 문제들 각각의 해결 방법들을 모두 탐색하기 때문이다.
하지만, 반복되는 하위 문제를 찾아 간단히 해결하도록 만드는 것으로 계산 횟수를 줄일 수 있다.

피보나치 수열을 예로 들어보면,

// 피보나치 수열 : 수열의 n번째 위치에서 앞의 두 수를 더한 값이 위치하는 수열
// (첫번째와 두번째는 0과 1이다.)
// [1, 1, 2, 3, 5, 8 .....]

function fiboFunc(n) {
    if (n === 0) {
        return 0;
    } else if (n===1) {
        return 1;
    } else {
        return fiboFunc(n-2) + fiboFunc(n-1)
    }
}

위처럼 표현할 수 있다. 하지만, 모두 0 또는 1이 될 때까지
계속 결과를 구하는 과정이 반복된다. (recursive call for calculate)
만약 이전의 결과를 구해서 저장해놓을 수 있다면 다음 연산시 저장된 값을 불러와서 쓰기만 하면되니
조금 일일히 다 구하는 것보다 좋을 것이다.

let memoryObj = {
  0:0,
  1:1
}

const fibo = (n) => {
  if (!memoryObj[n] && memoryObj[n] !== 0 && memoryObj[n] !== 1) {
    memoryObj[n] = fibo(n-2) + fibo(n-1)
  }
  return memoryObj[n]
}

함수의 결과 값을 저장하면서 최종 결과물을 찾는 함수이다.
이러한 방식으로 계산 횟수를 줄이면서 전체 값을 모두 탐색할 수 있다.
이처럼 계산 횟수를 줄이면서 모든 방법들을 검토하여 최적의 해결 방법을 나름 효율적으로 찾을 수 있다.