동적 계획법과 냅색 알고리즘

동적 계획법이란 

하나의 큰 문제를 아주 작은 단위의 문제로 해결하는 것으로 직관적으로 쪼개야 한다.  

답을 기록해놓고 구해놨던 답을 사용하면서 문제를 조금씩 넓힌다

 

특징으로는 점화식의 관계가 있기때문에 점화식을 파악하는게 중요하다고 한다

다이나믹 테이블 dy를 선언한 뒤 dy를 통해 구하는데 직관적으로 볼 수 있는 부분은 dy에 넣어서 구현을 했다

 

DP는 두가지 조건을 만족해야 사용할 수 있다고 한다

1. 겹치는 부분 문제

2. 최적 부분 구조

 

겹치는 부분 문제

동일한 작은 문제들이 반복적으로 나타나야한다. 예시로써 DFS로 구현한 코드를 보면 이미 구해놓았던 작은 계산들이 계속 반복된다.

 

최적 부분 구조

부분 문제의 최적 결과 값을 사용해 전체 문제의 최적 결과를 낼 수 있는 경우를 말한다

예시로 피보나치 수열의 경우 현재 위치 값을 구하는 경우는 자기 자신 인덱스 - 1과 -2의 합으로써 결과를 확인할 수 있게 된다.

 

function solution(n) {
  let answer = 0;
  
  // --------------------------------
  function DFS(level) {
    if (level <= 0) {
      if (level === 0) answer += 1;
    } else {
      for (let i = 1; i <= 2; i++) {
        DFS(level - i);
      }
    }
  }
  DFS(n);
  // --------------------------------
  
  
  const dy = Array.from({ length: n + 1 }, () => 0);
  dy[1] = 1;
  dy[2] = 2;
  for (let i = 3; i <= 45; i++) {
    dy[i] = dy[i - 2] + dy[i - 1];
  }

  answer = dy[n];

  return answer;
}

console.log(solution(45));

계단을 한번에 한칸~두칸 이동할 수 있다고 할때 n으로 주어지는 계단을 올라가는 방법의 갯수를 구하는 문제이다

 

이 문제를 DFS로 풀게됐을 때는 45 -> 44 , 43으로 시작해서 계속 나아가 0까지 가게 된다. 엄청나게 많은 계산들이 중복되게 되고 따로 계산값을 저장해놓지 않는 이상 꽤 오래 걸린다.

 

하지만 DP로 풀게되면 i 번째 계단을 올라가는 방법은 dy[i - 1] + dy[i - 2]라는 것을 알게되고 이미 구해놨던 답을 계속해서 사용하면서 최종 정답을 구할 수 있다.

 

지금 사용한 구현 방법으로 바텀-업 방식이라고 하기도 하며 반대로 탑-다운 방식을 가질 수도 있다.

 

 

냅색 알고리즘

0-1 배낭문제라고도 불리며 DP에서 자주 사용되는 예시이다

그리디 방식과 비교되기도 하지만 조건을 타는 그리디와는 달리 DP는 냅색 알고리즘을 최적의 해를 구할 수 있다

아래 문제는 배낭문제와 비슷한 최소 동전 교환 문제인데 주어진 동전을 모두 사용해서 구해보면 되는 문제이다

 

참고한 글에서 표를 살펴보면

[Inflearn] 동전교환(DP, 냅색 알고리즘, knapsack algorithm)

처음 초기화하는 dy는 각 금액의 최소값을 가질 수 있도록 만들어주고 동전 1부터 1원의 위치에 금액을 맞출 수 있도록 값을 넣는다.

이후 동전 2는 2원부터 초기화 할 수 있으니 2원의 위치부터 값을 넣게 되는데 이때 3원의 위치일 때 현재 동전의 2원을 뺀 최소 갯수를 현재 저장해놓은 값과 현재 동전만큼 뺀 금액의 최소갯수 + 1로 비교해본다. ( 표를 이해하면 쉽다)

 

이렇게 계속 돌려보면 값이 나오게 된다

function solution(m, coin) {
  let answer = Number.MAX_SAFE_INTEGER;
  const dy = Array.from({ length: m + 1 }, () => 10000);
  dy[0] = 0;

  for (let i = 0; i < coin.length; i++) {
    for (let k = coin[i]; k < dy.length; k++) {
      // 마지막에 코인하나를 무조건 더해주니 해당 코인 값만큼 뺴고
      // 뺀값의 인덱스로 가서 그곳의 코인최솟값에 1을 더헤준다
      // 이후 이미 있던 값과 새로 들어오는 값을 비교해서 넣는다
      dy[k] = Math.min(dy[k], dy[k - coin[i]] + 1);
    }
  }

  answer = dy[m];
  return answer;
}

let arr = [1, 2, 5];
console.log(solution(15, arr));