Skip to main content

10. Dynamic programming(동적계획법)

개념 정리​

동적계획법 (Dynamic Programming)​

기본적인 아이디어로 하나의 큰 문제를 여러 개의 작은 문제로 나누어서 그 결과를 저장하여 다시 큰 문제를 해결할 때 사용

문제 풀이​

Ch.10 - 01. 계단오르기​

const solution = (n: number): number => {
  const 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];
  }

  return dy[n];
};

Ch.10 - 02. 돌다리 건너기​

const solution = (n: number): number => {
  const goal: number = n + 1;

  const dy: Array<number> = Array.from({ length: goal + 1 }, () => 0);
  dy[1] = 1;
  dy[2] = 2;

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

  return dy[goal];
};

Ch.10 - 03. 최대부분증가수열(LIS)​

const solution = (arr: Array<number>): number => {
  const dy: Array<number> = Array.from({ length: arr.length }, () => 1);

  for (let i = 1; i < arr.length; i++) {
    let max = 0;
    for (let j = 1; j < i; j++) {
      if (arr[i - j] < arr[i]) {
        max = Math.max(max, dy[i - j]);
      }
    }
    dy[i] = max + 1;
  }

  return Math.max(...dy);
};

Ch.10 - 04. 동전교환(냅색 알고리즘)​

const solution = (coinList: Array<number>, change: number): number => {
  const dy: Array<number> = Array.from({ length: change + 1 }, () => 100);
  dy[0] = 0;

  for (let i = 0; i < coinList.length; i++) {
    const curCoin: number = coinList[i];
    for (let j = curCoin; j <= change; j++) {
      dy[j] = Math.min(dy[j], dy[j - curCoin] + 1);
    }
  }

  return dy[change];
};

Ch.10 - 05. 최대점수 구하기(냅색을 이용한 조합)​

const solution = (n: number, arr: Array<Array<number>>) => {
  const dy: Array<number> = Array.from({ length: n + 1 }, () => 0);
  dy[0] = 0;

  for (let i = 0; i < arr.length; i++) {
    const [point, time] = arr[i];

    for (let j = time; j <= n; j++) {
      dy[j] = Math.max(dy[j], dy[j - time] + point);
    }
  }

  return dy[n];
};

참고​