🙋‍♀️동적계획법(Dynamic programming)

동적 계획법이란 하나의 복잡한 문제를 여러 개의 간단한 하위 문제로 나누어 푼 다음, 이를 결합하여 답을 도출해내는 방법이다. 나누어진 하위 문제들의 결과를 따로 저장해두었다가 이후 동일한 문제가 나왔을 시 저장해둔 결과를 가져다가 쓰면 같은 문제를 반복해서 풀지 않아도 되기 때문에 문제를 해결하는데 시간을 절약할 수 있다. 즉 한번 푼 하위 문제는 중복해서 풀지 않는다.
⭐️동적 계획법 문제 풀이방식 : dynamic table이 꼭 필요하다. (dy) 👉 0~n까지 각각의 값을 기록해둔다. 점점 확대해간다.

1. 계단오르기

철수는 계단을 오를 때 한 번에 한 계단 또는 두 계단씩 올라간다. 총 N계단일 때 철수가 올라갈 수 있는 방법의 수는 몇 가지인가?

  function solution(n) {
    let answer = 0;
    let dy = Array.from({ length: n + 1 }, () => 0);
    dy[1] = 1;
    dy[2] = 2;

    for (let i = 3; i <= n; i++) {
      dy[i] = dy[i - 2] + dy[i - 1];
    }

    answer = dy[n];

    return answer
  }
  console.log(solution(7)); //21

2. 돌다리 건너기

철수는 학교에 가는데 개울을 만났습니다. 개울은 N개의 돌로 다리를 만들어 놓았습니다. 돌다리를 건널 때 한 번에 한 칸 또는 두 칸씩 건너뛰면서 돌다리를 건널 수 있습니다. 개울을 건너는 방법은 몇 가지인가?

  function solution(n) {
    let answer = 0;
    let dy = Array.from({ length: n + 1 }, () => 0);
    dy[0] = 1;
    dy[1] = 2;
    for (let i = 2; i <= n; i++) {
      dy[i] = dy[i - 2] + dy[i - 1];
    }

    answer = dy[n];

    return answer;
  }
  console.log(solution(7)); //34

3. 최대 부분 증가수열

N개의 자연수로 이루어진 수열이 주어졌을 때, 그 중에서 가장 길게 증가하는(작은 수에서 큰 수로) 원소들의 집합을 찾는 프로그램을 작성하라. 예를 들어, 원소가 2, 7, 5, 8, 6, 4, 7, 12, 3 이면 가장 길게 증가하도록 원소들을 차례대로 뽑아내면 2, 5, 6, 7, 12를 뽑아내어 길 이가 5인 최대 부분 증가수열을 만들 수 있다.

✔️ dy[i]의 의미 : arr의 i번째 숫자가 증가수열의 마지막 숫자일 경우 최대 증가수열의 길이값

  function solution(arr) {
    let answer = 0;
    let dy = Array.from({ length: arr.length }, () => 0);
    dy[0] = 1;
    for (let i = 1; i < arr.length; i++) {
      let max = 0;
      for (let j = i - 1; j >= 0; j--) {
        if (arr[j] < arr[i] && dy[j] > max) {
          max = dy[j];
        }
      }
      dy[i] = max + 1;
      answer = Math.max(answer, dy[i]);
    }

    return answer;
  }
  let arr = [5, 3, 7, 8, 6, 2, 9, 4];
  console.log(solution(arr)); //4

4. 동전교환(냅색 알고리즘)

여러 단위의 동전들이 주어져 있을때 거스름돈을 가장 적은 수의 동전으로 교환 해주려면 어떻게 주면 되는가? 각 단위의 동전은 무한정 쓸 수 있다.

✔️ 냅색 알고리즘 : 배낭 문제 라고도 부른다.
✔️ dy : 거슬러줄 금액을 인덱스 번호로 만든다 0~15. 큰 숫자로 초기화. i금액을 거슬러주는데 필요한 최소 동전의 갯수가 dy의 값(dy[i])이 된다.
✔️ 동전 1을 포함했을 경우 2를 포함했을경우~~ coin의 모든 동전 경우의 수로 for 문을 돈다.

  function solution(m, coin) {
    let answer = 0;
    let dy = Array.from({ length: m + 1 }, () => 1000);
    dy[0] = 0;
    for (let i = 0; i < coin.length; i++) {
      for (let j = coin[i]; j <= m; j++) {
        dy[j] = Math.min(dy[j], dy[j - coin[i]] + 1); //coin[i]를 빼주는 이유 : 확실하게 그 동전은 포함하므로. 그리고 갯수에 1을 더해주는 이유 또한 그 동전이 포함이 되었기 때문.
      }
    }
    answer = dy[m];

    return answer;
  }
  let arr = [1, 2, 5];
  console.log(solution(15, arr)); //3

5. 최대점수 구하기(냅색을 이용한 조합)

현수는 선생님이 주신 N개의 문제를 풀려고 한다. 각 문제는 그것을 풀었을 때 얻는 점수와 푸는데 걸리는 시간이 주어지게 된다. 제한시간 M안에 N개의 문제 중 최대점수를 얻을 수 있도록 해야 한다. (해당문제는 해당시간이 걸리면 푸는 걸로 간주한다, 한 유형당 한개만 풀 수 있다.)

✔️ j의 범위 : m~ pt[i] (중복을 막기 위해 dy 뒤에서부터 for문을 돌려야 한다.)

  function solution(m, arr) {
    let answer = 0;
    let dy = Array.from({ length: m + 1 }, () => 0);
    for (let i = 0; i < arr.length; i++) {
      let ps = arr[i][0]; // 점수
      let pt = arr[i][1]; // 걸리는 시간
      for (let j = m; j >= pt; j--) {
        dy[j] = Math.max(dy[j], dy[j - pt] + ps);
      }
    }
    answer = dy[m];

    return answer;
  }


  let arr = [
    [10, 5],
    [25, 12],
    [15, 8],
    [6, 3],
    [7, 4],
  ];
  console.log(solution(20, arr)); //41