다이나믹 프로그래밍

다이나믹 프로그래밍을 사용할 수 있는 조건

• 중첩되는 하위 문제
  - 조각들 중 일부가 재활용될 수 있어야함
  - 피보나치 수열을 생각해보면 f(5) = f(4) + f(3)이고 이는 계속해서 반복됨. : 중첩되는 하위 문제가 있음.
  - merge Sort와는 다름, merge Sort는 비슷한 방법을 계속하지만, 반복되지는 않음. : 중첩되는 하위 문제가 없음.
• 최적 부분 구조
  - 하위 문제의 최적 해답을 통해서 더 큰 범주의 문제 해답을 구할 수 있는 경우
  - 하위 문제들로, 더 큰 범주의 해답을 구할 수 없다면 다이나믹프로그래밍을 사용할 수 없음.

피보나치 수열

• 피보나치 수열을 원래 하던 것 처럼 재귀로 호출하면,

let recur = 0;

function fib(n) {
    recur++;
    if(n <= 2) return 1;
    return fib(n-1) + fib(n-2);
}

// fib(5) 9번 호출
// fib(6) 15번 호출
// fib(7) 25번

• 엄청 좋지 못한 시간복잡도를 가짐.
• 이는 Big O가 O(2^N)인데 O(N^2)보다 훨씬안좋음. 가파르게 상승하기 때문.
• 피보나치 자체는 (2^N)이 아니지만, 엄청 안좋다는 이야기.
• fib(100)했을때 나오지도 않음.

피보나치 수열의 문제

• 가장 큰 문제는 똑같은 계산을 계속한다는 것.
  - fib(5)를 구하기 위해 fib(4)를 구하고, fib(3)을 구해야 하는데,
  - fib(4)를 구할때 fib(3)을 이미 구해놨음에도 재사용하지 않고 또! 똑같은 반복을 계속함.
  - 이 부분에서 우리는 피보나치가 DP에 적용할 수 있는 케이스라는 것을 인지해야 함.

-> 이미 구해놨던 부분을 다시 사용하면, 반복을 줄일 수 있다.

Memoization: top-down

• 배열이나 객체인 데이터를 저장할 구조를 만든다.
• 반복되는 값을 미리 저장해 둔다.
• 다음에 그 값을 꺼내 사용한다.

function fib(n, memo = []) {
    if(memo[n] !== undefined) return memo[n];
    if(n <= 2) return 1;
    let res = fib(n-1, memo) + fib(n-2, memo);
    memo[n] = res;
    // console.log(memo);
    return res;
}

// console.log(fib(5))
// [ <3 empty items>, 2 ]
// [ <3 empty items>, 2, 3 ]
// [ <3 empty items>, 2, 3, 5 ]

• memo 배열을 만들어, 이미 만들어두었던 값을 memo안에 저장한다.
• memo안에 필요한 값이 있다면 하위 문제를 반복하지 않고 메모에서 값을 꺼내온다.
• 예를 들어, fib(5)를 구하고자 한다면,
  - fib(5) = fib(4) + fib(3)으로 구할 수 있는데,
  - fib(4) = fib(3) + fib(2) 이다.
  - fib(4)를 구할때, 이미 fib(3)은 구해져서 메모에 저장해 놓았으므로,
  - fib(3)을 구하는 반복적인 호출을 하지 않고 메모에서 꺼내온다.
  - 하위에 반복되는 로직에서도 이러한 메모를 이용한 방법이 반복된다.
• memoization을 사용한 방법의 BIG O는 O(N)이 된다.

Tabulation: bottom-up

• 보통 루프와 같이 순환 작업을 한다.
• 무엇이든 간에 가장 아래에서 시작하고, 하위 문제를 배열등에 저장한다.
• 루프를 돌면서 앞으로 가면서 더한다.(피보나치의 경우에는)
• 우리가 얻고자 하는 답을 얻을때까지 반복한다.

function fib(n) {
    if(n <= 2) return 1;
    const fibNums = [0, 1, 1];
    for(let i=3; i<=n; i++) {
        fibNums[i] = fibNums[i-1] + fibNums[i-2];
    }
  	// console.log(fibNums);
    return fibNums[n];
}
// fib(5)
// [ 0, 1, 1, 2, 3, 5 ]
// fib(6)
// [ 0, 1, 1, 2, 3, 5, 8 ]

• 가장 아래에서 시작해서 원 문제까지 올라가는 상향식 방법.
• 공간복잡도 측면에서 유리하다.
  <-> memoization방식은 n개만큼 계속해서 배열이 증가하게 된다.
• 시간복잡도는 O(N)이다.