TIL. 알고리즘 Case - Dynamic Programming

DP의 조건

1) 하나의 Problem을 Sub-Problem으로 구분할 수 있는가
2) Sub-Problem의 값으로 Problem을 구할 수 있는가
3) Sub-Problem이 중복이 되는가

전에 공부한 재귀를 살펴보자

Fibonacci

우리는 재귀를 사용해서 fibonacci 문제를 해결할 수 있었다.

const fib = (n) => {
  if (n < 2) {
    return n
  }
  else {
    return fib(n-2) + fib(n-1)
  }
}

재귀는 아래와 같은 단점이 있다.
1) n이 커질 수록 call stack에 누적되는 식이 기하 급수적으로 많아진다.
2) 시간 복잡도가 커진다.

DP로 재귀의 단점을 보안할 수 있다

전에 한번 다뤄본 적이 있는 memoization이 바로 DP를 사용한 방식이다.

let memo = [0, 1];

const fib_memo = (n) => {
  if (memo[n]=== undefined) {
    memo[n] = fib_memo(n-2) + fib_memo(n-1)
  }
  return memo[n]
}

재귀로 호출되는 횟수를 많이 줄였지만 (O(n^2) -> O(n)), 여전히 단점이 존재한다.
재귀를 쓰고 있기 때문에, n이 커지면 호출 횟수가 커지기 때문이다.
Top-Down 방식의 DP의 단점이 바로 여기에 있다.

Bottom-Up 방식의 DP를 사용해보자

아래 방식은 수가 커지더라도, 재귀로 call stack을 쌓는 단점이 발생하지 않는다.

const fib_btu = (n) => {
  let bottomUp = [0, 1]
  
  for (let i = 2; i <= n; i++) {
    bottomUp[i] = bottomUp[i-1] + bottomUp[i-2];
  }

  return bottomUp[n]
}

다른 문제를 풀어보자 (DP - 금고를 털어라)

문제 - $50 을 훔칠 때 $10, $20, $50이 있다면 다음과 같이 4 가지 방법으로 $50을 훔칠 수 있습니다.

• $50 한 장을 훔친다
• $20 두 장, $10 한 장을 훔친다
• $20 한 장, $10 세 장을 훔친다
• $10 다섯 장을 훔친다

훔치고 싶은 target 금액과 금고에 있는 돈의 종류 type 을 입력받아, 조지가 target 을 훔칠 수 있는 방법의 수를 리턴하세요.

DP의 조건을 상기해보자.
1) 문제를 sub-문제로 나눌 수 있어야 하고, 그 값으로 문제의 값을 구할 수 있어야 한다.
=> $50을 훔치는 경우, $10를 뺀 나머지 $40을 훔치는 경우의 수를 확인해 봐야한다.
2) sub-문제가 중복되어, 여기 저기에서 활용할 수 있어야 한다.
=> $10로 만들 수 있는 가치는 $10, $20, $30.. 등이 있다. $20 두 장을 훔치고, 나머지 $10를 훔치는 경우의 수는 이미 1개로 계산이 되어 있어서 그걸 활용하면 된다.

function ocean(target, type) {
  // 동전이 하나 밖에 없는 경우, 그 수로 만들 수 있는 어떤 수든지 그 경우의 수는 항상 1이다.
  // 10원으로 10원을 만드는 경우의 수 = 1, 20원을 만드는 경우의 수 = 1.....
  let bag = [1];

  // 만들고자 하는 수까지의 모든 idx에 0을 넣어 경우의 수를 늘리는 배열을 만들어 준다. (memoization으로 활용)
  for (let i = 1; i <= target; i++) {
    bag[i] = 0;
  }
  
  for (let i = 0; i < type.length; i++) {
    for (let j = 1; j <= target; j++) {
      if (j >= type[i])
      // 10원으로 10원 만드는 경우의 수???
      // 10원 - 10원 === 0 -> 미리 위에서 심어 놓은 bag[0]의 값 활용한다. 1이다.
      // 10원으로 20원 만드는 건??
      // 10원 쓰고 나머지 10원은 아까 1개의 경우의 수 밖에 없다고 계산해 놨네?? 이것도 1이다.
      // 각 화폐의 단위를, 훔치고자 하는 금액까지 계속 점화식으로 풀다보면, 50원을 훔칠 수 있는 모든 경우의 수를 구할 수 있다.
      bag[j] = bag[j] + bag[j - type[i]]
    }
  }
  return bag[target]
}

대표적인 DP 문제 - 배낭 채우기는 다음 시간에...