[LeetCode] DP 기본 문제들; 계단오르기, Min Sum Path, Coin Change, Decode Ways(JavaScript)

Youtube 코드 없는 프로그래밍 DP 플레이리스트 따라서,
LeetCode DP 초급 문제 풀이
Decode Ways는 초급치고는 난이도가 좀 있었다

DP 문제에 대한 기본적인 접근 방법

• 전체 문제와 부분 문제로 나눠질 수 있는 문제인지 판단
• 점화식을 '잘' 구해야 한다
  • 보통 점화식만 잘 구하면 구현 자체 난이도는 높지 않은 경우가 많다고 한다..
  • 그 '잘' 구하는게 어렵..
  • 특정 위치에서 이전 값을 가지고 연산할 수 있는지?
  • 직관적으로 구하기 어려우면 손으로 직접 decision table을 그려보자
  • top-down 방식 보다는 bottom-up 방식이 좀더 효율적인 경우가 많다
• memoization
  • 점화식은 이전 식에서 계산된 값들을 가지고 연산하기 때문에
  • 그 이전 식에서 계산된 값들을 배열 등 자료구조에 저장해놔야 빠른 연산이 가능하다
  • memoization 자료에 접근하기 편한 방식을 찾아보자
• Recursion vs. Iteration
  • Recursion으로 좀더 편하게 구현하기 쉬운 문제들이 많지만,
  • 10만 단위 이상으로 입력이 커지게 되면 콜 스택 한도 초과 에러를 만나게 된다
  • 일단 Recursion으로 빠르게 구현해보고, 문제가 발생하면 Iteration으로 변경

746. Min Cost Climbing Stairs

문제 요약

• 계단을 한칸 또는 두칸씩 올라갈 수 있을 때,
• 각 계단을 올라가는 비용들의 최소합

/**
 * @param {number[]} cost
 * @return {number}
 */
const minCostClimbingStairs = (cost) => {
	const accs = [cost[0], cost[1]];
	const SIZE = cost.length;
	let i = 2;
	while (i < SIZE) {
		accs[i] = Math.min(accs[i - 1], accs[i - 2]) + cost[i];
		i++;
	}
	return Math.min(accs[SIZE - 1], accs[SIZE - 2]);
};

64. Minimum Path Sum

문제 요약

• m X n 배열에서 각 지점을 지나가는 비용 최소합
• 위 계단 문제가 1차원 배열이라면, 이 문제는 2차원 배열 활용

/**
 * @param {number[][]} grid
 * @return {number}
 */
const minPathSum = (grid) => {
  const m = grid.length;
  const n = grid[0].length;
  for (const row in grid) {
    for (const col in grid[row]) {
      if (row === "0" && col === "0") continue;
      if (row === "0") grid[row][col] += grid[row][col - 1];
      else if (col === "0") grid[row][col] += grid[row - 1][col];
      else {
        grid[row][col] += Math.min(grid[row - 1][col], grid[row][col - 1]);
      }
    }
  }
  return grid[m - 1][n - 1];
};

322. Coin Change

문제 요약

• 주어진 숫자 배열의 값들을 가지고
• target을 만들 수 있다면 최소 몇개를 가지고 만들 수 있는지
• 만들 수 없다면 -1

회고

• 이 문제부터 조금씩 구현 난이도가 올라가는 듯
• 점화식: 특정 target을 만들수 있는 동전의 수 = min( (target-각 동전 값)에서 만들 수 있는 동전수) + 1

/**
 * @param {number[]} coins
 * @param {number} amount
 * @return {number}
 */
const coinChange = (coins, amount) => {
  const res = Array(amount + 1).fill();
  res[0] = 0;

  let cur = 0;
  while (cur <= amount) {
    
    // cur == 현재 단계의 target number
    cur++;
    
    // 일단 1개로 입력
    // 현재 단계가 coins에 있으면 한번에 가능하므로 바로 다음 단계로 이동
    res[cur] = 1;
    if (coins.includes(cur)) continue;

    // 동전 배열 순회하면서 
    // 범위가 맞지 않거나 이전 단계에서 생성 불가능했다면 continue
    // 이전 단계에서 생성 가능했다면 해당 가지 수를 추가
    const temp = [];
    for (const coin of coins) {
      if (cur - coin < 0) continue;
      if (res[cur - coin] === -1) continue;
      temp.push(res[cur - coin]);
    }

    // 이전 단계에서 모두 생성 불가능했다면, 이번 단계에서도 생성 불가능하므로 -1
    // 생성 가능한 경우의 수 중 최소값 입력
    temp.length === 0 ? (res[cur] = -1) : (res[cur] += Math.min(...temp));
  }

  return res[amount];
};

91. Decode Ways

문제 요약

• 주어진 숫자 문자열을 알파벳으로 decoding 할 경우
• decoding 될 수 있는 모든 경우의 수

회고

• 코드 없는 프로그래밍님 강의 영상을 보고도 구현하기 어려웠던 문제
• 점화식을 생각해내기가 어려웠다..
• 재귀로 풀었더니 시간 초과가 나버림
  • memoization이 제대로 구현되지 않은 상태로 DFS 접근한 것 같다
• 아래 코드는 bottom-up 방식으로 구현
• 반드시 복습해야 할 문제..!

/**
 * @param {string} s 숫자 문자열
 * @return {number} 몇개의 문자열로 decoding 될 수 있는지
 */
const numDecodings = (s) => {
  // 0으로 시작하는 경우는 decoding 불가능하므로 바로 예외 처리
  if (s[0] === "0") return 0;

  // 해당 숫자 문자열이 유효한지
  const isValid = (ss) => {
    const num = Number(ss);
    return ss[0] !== "0" && 0 < num && num < 27;
  };

  // 문자열 길이가 1인 경우는 바로 유효성 검사로 return
  // 아래에서 시작하는 인덱스가 2부터이기 때문에 미리 처리해야 함
  const SIZE = s.length;
  if (SIZE === 1) return isValid(s) ? 1 : 0;

  // memoization 초기화
  // base case인 첫 인덱스와 두번째 인덱스는 미리 계산해서 입력
  // 배열로 하는 것이 정석이지만, 여기서는 구현 편의상 Object 활용
  // 어차피 JS에서는 배열도 Object다..
  const memo = {};
  memo[SIZE - 1] = isValid(s[SIZE - 1]) ? 1 : 0;
  memo[SIZE - 2] =
    // 한자리 수 유효성 검사
    (isValid(s[SIZE - 2]) ? memo[SIZE - 1] : 0) +
    // 두자리 수 유효성 검사
    (isValid(s[SIZE - 2] + s[SIZE - 1]) ? 1 : 0);
  for (let i = SIZE - 3; i > -1; i--) {
    let tmp = 0;
    if (isValid(s[i])) tmp += memo[i + 1];
    if (isValid(s[i] + s[i + 1])) tmp += memo[i + 2];
    memo[i] = tmp;
  }

  return memo[0];
};

LeetCode 메모리 효율성 최상위 코드

• 이 코드가 이해하기도 좀더 좋아보인다
• 재귀를 쓰려면 정말 잘 구현해야 하는 듯

var numDecodings = function(s) {
    let memo = Array(s.length).fill(null);
    return helper(s, 0, memo);
};

var helper = (s, start, memo) => {
    if (start === s.length) return 1;
    if (s[start] === '0') return 0;
    if (start === s.length-1) return 1;
    if (memo[start] !== null) return memo[start];
    
    let result = helper(s, start+1, memo);
    if (Number(s.slice(start, start+2)) <= 26) result += helper(s, start+2, memo)
    
    memo[start] = result;
    return result;
}