다이나믹 프로그래밍

계단 오르기

let n = 7;

function solution(n) {
  let answer = 0;
  let dy = Array(n + 1).fill(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];
  console.log(dy);
  return answer;
}

돌다리 건너기

let n = 7;

function solution(n) {
  n = n + 1;
  let d = Array(n + 1).fill(0);

  function DP(x) {
    if (x === 1) return 1;
    if (x === 2) return 2;
    if (d[x] !== 0) return d[x];
    return (d[x] = DP(x - 1) + DP(x - 2));
  }
  return DP(n);
}

최대 부분 증가수열

let nums = [5, 3, 7, 8, 6, 2, 9, 4];

function solution(nums) {
  let answer = [],
    pos = 0;
  let dy = Array(nums.length + 1).fill(0);
  let pa = Array(nums.length + 1).fill(-1);
  dy[0] = 1;

  for (let i = 0; i < nums.length; i++) {
    let max = 0;
    for (let j = i - 1; j >= 0; j--) {
      if (nums[j] < nums[i] && dy[j] > max) {
        max = dy[j];
        pa[i] = j;
      }
    }
    dy[i] = max + 1;
    if (dy[i] > answer) {
      answer = dy[i];
      pos = i;
    }
  }

  // 수열 구하는 파트
  let path = [];
  function DFS(idx) {
    if (idx === -1) {
      return;
    } else {
      DFS(pa[idx]);
      path.push(nums[idx]);
    }
  }
  DFS(pos);

  return answer;
}

효율적인 공부

let times = [
  [3, 5, 20],
  [4, 7, 16],
  [1, 2, 5],
  [11, 13, 7],
  [9, 10, 6],
];
let r = 2;

function solution(times, r) {
  let answer = 0;
  let dy = Array(times.length).fill(0);
  times.sort(([, a], [, b]) => a - b);
  for (let i = 0; i < times.length; i++) {
    dy[i] = times[i][2];
    for (let j = i - 1; j >= 0; j--) {
      if (times[j][1] + r <= times[i][0] && dy[j] + times[i][2] > dy[i]) {
        dy[i] = dy[j] + times[i][2];
      }
    }
    answer = Math.max(answer, dy[i]);
  }
  return answer;
}

가방문제

냅색 알고리즘

let nums = [
  [5, 12],
  [3, 8],
  [6, 14],
  [4, 7],
];
let m = 11;

function solution(nums, m) {
  let answer = 0;
  let dy = Array(m + 1).fill(0);
  for (let i = 0; i < nums.length; i++) {
    for (let j = nums[i][0]; j <= m; j++) {
      dy[j] = Math.max(dy[j], dy[j - nums[i][0]] + nums[i][1]);
    }
    console.log(dy);
  }
  answer = dy[m];
  return answer;
}

동전교환

냅색 알고리즘

function solution(nums, m) {
  let answer = 0;
  let dy = Array(m + 1).fill(Number.MAX_SAFE_INTEGER);
  dy[0] = 0;
  for (let i = 0; i < nums.length; i++) {
    for (let j = nums[i]; j <= m; j++) {
      dy[j] = Math.min(dy[j], dy[j - nums[i]] + 1);
    }
    console.log(dy);
  }
  answer = dy[m];
  return answer;
}

최대점수 구하기

냅색 알고리즘

let nums = [
  [10, 5],
  [25, 12],
  [15, 8],
  [6, 3],
  [7, 4],
];
let m = 20;

function solution(nums, m) {
  let answer = 0;
  let dy = Array(m + 1).fill(0);
  for (let i = 0; i < nums.length; i++) {
    let ps = nums[i][0];
    let pt = nums[i][1];
    for (let j = m; j >= pt; j--) {
      dy[j] = Math.max(dy[j], dy[j - pt] + ps);
    }
  }
  answer = dy[m];
  return answer;
}

최대 공통부분 문자열

LCS

function solution(s1, s2) {
  let answer = 0;
  let len1 = s1.length;
  let len2 = s2.length;
  let dy = Array.from(Array(len1 + 1), () => Array(len2 + 1).fill(0));

  for (let i = 1; i <= len1; i++) {
    for (let j = 1; j <= len2; j++) {
      if (s1[i - 1] === s2[j - 1]) dy[i][j] = dy[i - 1][j - 1] + 1;
      else {
        dy[i][j] = Math.max(dy[i - 1][j], dy[i][j - 1]);
      }
    }
  }
  console.log(dy);
  answer = dy[len1][len2];

  let path = [];
  function DFS(p1, p2) {
    if (p1 === 0 || p2 === 0) return;
    if (s1[p1 - 1] === s2[p2 - 1]) {
      DFS(p1 - 1, p2 - 1);
      path.push(s1[p1 - 1]);
    } else {
      if (dy[p1 - 1][p2] > dy[p1][p2 - 1]) DFS(p1 - 1, p2);
      else DFS(p1, p2 - 1);
    }
  }
  DFS(len1, len2);
  console.log(path);
  return answer;
}

최소편집

function solution(s1, s2) {
  let answer = 0;
  let len1 = s1.length;
  let len2 = s2.length;
  let dy = Array.from(Array(len1 + 1), () => Array(len2 + 1).fill(0));

  for (let i = 1; i <= len1; i++) dy[i][0] = i;
  for (let i = 1; i <= len2; i++) dy[0][i] = i;
  for (let i = 1; i <= len1; i++) {
    for (let j = 1; j <= len2; j++) {
      if (s1[i - 1] === s2[j - 1]) {
        dy[i][j] = dy[i - 1][j - 1];
      } else {
        dy[i][j] = Math.min(dy[i - 1][j], dy[i][j - 1], dy[i - 1][j - 1]) + 1;
      }
    }
  }

  answer = dy[len1][len2];
  return answer;
}