[Javascript로 정리하는 이코테] 7. 다이나믹 프로그래밍

http://www.yes24.com/Product/Goods/91433923

이것이 취업을 위한 코딩 테스트다 with 파이썬 - YES24

 

개념

• 다이나믹 프로그램은 한 번 계산한 문제는 다시 계산하지 않도록 하는 알고리즘
• 메모리 공간을 약간 더 사용하여 연산 속도를 비약적으로 증가시키는 방법
• 다이나믹 프로그래밍을 사용하기 위해서는, 다음 두 조건을 만족해야 한다.
  1. 큰 문제를 작은 문제로 나눌 수 있다.
  2. 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일하다.
• 다이나믹 프로그램을 구현하는 방식은 두 가지가 있다.
  • Top-Down: 재귀적으로 구현 (w/ 메모이제이션)
  • Bottom-Up: 반복문으로 구현 (w/ DP 테이블)
• 시간복잡도: O(n)

 

참고) 자세한 문제 풀이 전략은 여기를 참고하자.

 

💡 다이나믹 프로그래밍 유형 파악하기

• 특정 문제를 완전 탐색 알고리즘으로 접근했을 때 시간이 매우 오래 걸린다면, 해결하고자 하는 부분 문제들의 중복 여부를 확인해 다이나믹 프로그래밍을 적용할 수 있는지 알아보자.
• 일단 재귀 함수를 구현 한 뒤, 메모이제이션을 적용할 수 있으면 코드를 개선해 나아가는 방법도 좋다.
• 스택 오버플로우를 방지하기 위해 가능한 Bottom-Up 방식으로 구현하자.

 

예제 8-1. 피보나치 함수

동일한 함수가 반복적으로 호출된다 → O(2^n)

const fibo = (x) => {
  if (x === 1 || x === 2) return 1;
  return fibo(x - 1) + fibo(x - 2);
};

console.log(fibo(4));

 

예제 8-2. 피보나치수열 (재귀적)

한 번 구한 정보를 배열에 저장한다 → O(n)

let d = [...Array(100).fill(0)];

const fibo = (x) => {
  if (x === 1 || x === 2) return 1;

  if (d[x] != 0) return d[x];
  return (d[x] = fibo(x - 1) + fibo(x - 2));
};

console.log(fibo(4));

 

예제 8-3. 호출되는 함수 확인

let d = [...Array(100).fill(0)];

const fibo = (x) => {
  console.log(`f(${x})`);
  if (x === 1 || x === 2) return 1;

  if (d[x] != 0) return d[x];
  return (d[x] = fibo(x - 1) + fibo(x - 2));
};

fibo(6);

 

예제 8-4. 피보나치 수열 (반복적)

보텀업 방식으로 구현 → O(n)

const n = 99;
let d = [...Array(n + 1).fill(0)];

const fibo = (x) => {
  d[1] = d[2] = 1;

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

console.log(fibo(n));

 

 

실전 문제

1로 만들기

방법 1. Top-Down

const fs = require('fs');
let input = fs.readFileSync('../tc.txt').toString().trim();

const n = +input;

const d = [...Array(n + 1).fill(0)];

const dp = (x) => {
  if (x === 1 || x === 2 || x === 3 || x === 5) return 1;

  if (d[x] !== 0) return d[x];

  if (x % 5 === 0) return (d[x] = Math.min(dp(x / 5), dp(x - 1)) + 1);
  if (x % 3 === 0) return (d[x] = Math.min(dp(x / 3), dp(x - 1)) + 1);
  if (x % 2 === 0) return (d[x] = Math.min(dp(x / 2), dp(x - 1)) + 1);
  return (d[x] = dp(x - 1) + 1);
};

function solution(n) {
  return dp(n);
}

console.log(solution(n));

 

방법 2. Bottom-Up

const dp = (x) => {
  d[1] = d[2] = d[3] = d[5] = 1;
  d[4] = 2;

  for (let i = 6; i <= x; i++) {
    d[i] = d[i - 1] + 1;
    if (i % 2 === 0) d[i] = Math.min(d[i / 2], d[i - 1]) + 1;
    if (i % 3 === 0) d[i] = Math.min(d[i / 3], d[i - 1]) + 1;
    if (i % 5 === 0) d[i] = Math.min(d[i / 5], d[i - 1]) + 1;
  }

  return d[x];
};

 

개미 전사

• i번째 식량 창고를 털지 안 털지 결정하고 최댓값을 구하면 된다.
• d[i]는 i번째 식량 창고에 도달했을 때 털 수 있는 최대 식량을 의미한다.

const fs = require('fs');
let input = fs.readFileSync('../tc.txt').toString().trim().split('\n');

let [n, arr] = input;
n = +n;
arr = arr.split(' ').map((v) => +v);

const d = [...Array(n + 1).fill(0)];

const dp = (n) => {
  d[0] = arr[0];
  d[1] = Math.max(arr[0], arr[1]);

  for (let i = 2; i < n; i++) {
    d[i] = Math.max(d[i - 2] + arr[i], d[i - 1]);
  }

  return d[n - 1];
};

function solution(n, arr) {
  return dp(n);
}

console.log(solution(n, arr));

 

바닥 공사

• d[i]는 가로가 i일 때 바닥을 채우는 방법의 수를 의미한다.

const fs = require('fs');
let input = fs.readFileSync('../tc.txt').toString().trim();

const n = +input;

const DIV = 796796;
const d = [...Array(n + 1).fill(0)];

const dp = (n) => {
  d[1] = 1;
  d[2] = 3;

  for (let i = 3; i <= n; i++) {
    d[i] = (d[i - 2] * 2 + d[i - 1]) % DIV;
  }

  return d[n];
};

function solution(n) {
  return dp(n);
}

console.log(solution(n));

 

효율적인 화폐 구성

• d[i]는 i원을 만들기 위한 최소한의 화폐 개수이며, d[i]=Infinity인 경우 i원을 만들 수 있는 화폐 구성이 없다는 의미이다.

const fs = require('fs');
let input = fs.readFileSync('../tc.txt').toString().trim().split('\n');

const [nm, ...arr] = input;
const [n, m] = nm.split(' ').map((v) => +v);
const coins = arr.map((v) => +v);

const d = [...Array(m + 1).fill(Infinity)];

const dp = (n, m, coins) => {
  d[0] = 0;
  for (const coin of coins) d[coin] = 1;

  for (let i = 1; i <= m; i++) {
    for (const coin of coins) {
      if (i < coin) continue;
      d[i] = Math.min(d[i], d[i - coin]) + 1;
    }
  }

  return d[m];
};

function solution(n, m, coins) {
  const result = dp(n, m, coins);
  return result === Infinity ? -1 : result;
}

console.log(solution(n, m, coins));