코딩테스트 동적계획법

동적 계획법을 간단히 정의 하면 전체 문제를 한번에 해결 하는 것이 아니라 작은 부분 문제들을 해결 하고, 이것들을 활용하여 전체 문제를 해결하는 방법이라고 할 수 있습니다.

큰 문제를 작은 문제로 나누었을 때 동일한 작은 문제가 반복해서 등장해야합니다.

큰 문제의 해결책은 작은 문제의 해결책의 합으로 구성 할 수 있어야 합니다.

큰 문제를 작은 문제로 나누었을 때 동일한 작은 문제가 반복해서 등장해야 된다.

점화식 세우기와 동적 계획법

문제를 해결하는 해가 이미 있다고 가정합니다.
종료 조건을 설정 합니다.
과정을 통해 점화식을 활용

// 피보나치 수열 (Fibonacci Sequence)
function fibonacci(n) {
  if (n <= 2) return 1
  let dp = [0, 1, 1] // dp[0]은 사용하지 않음
  for (let i = 3; i <= n; i++) {
    dp[i] = dp[i - 1] + dp[i - 2]
  }
  return dp[n]
}

function fibonacciOptimized(n) {
  if (n <= 2) return 1
  let prev1 = 1,
    prev2 = 1
  for (let i = 3; i <= n; i++) {
    let current = prev1 + prev2
    prev2 = prev1
    prev1 = current
  }
  return prev1
}

// 계단 오르기 문제 (Climbing Stairs)
function climbStairs(n) {
  if (n <= 2) return n
  let dp = [0, 1, 2] // dp[0]은 사용하지 않음
  for (let i = 3; i <= n; i++) {
    dp[i] = dp[i - 1] + dp[i - 2]
  }
  return dp[n]
}

// 최소 비용 문제 (Minimum Cost Path)
function minCostPath(cost) {
  let rows = cost.length
  let cols = cost[0].length
  let dp = Array.from({ length: rows }, () => Array(cols).fill(0))

  dp[0][0] = cost[0][0]

  // 첫 번째 열 초기화
  for (let i = 1; i < rows; i++) {
    dp[i][0] = dp[i - 1][0] + cost[i][0]
  }

  // 첫 번째 행 초기화
  for (let j = 1; j < cols; j++) {
    dp[0][j] = dp[0][j - 1] + cost[0][j]
  }

  // DP 테이블 채우기
  for (let i = 1; i < rows; i++) {
    for (let j = 1; j < cols; j++) {
      dp[i][j] = cost[i][j] + Math.min(dp[i - 1][j], dp[i][j - 1])
    }
  }

  return dp[rows - 1][cols - 1]
}

// 예제 실행
console.log(fibonacci(10)) // 55
console.log(fibonacciOptimized(10)) // 55
console.log(climbStairs(5)) // 8
console.log(
  minCostPath([
    [1, 2, 3],
    [4, 8, 2],
    [1, 5, 3],
  ])
) // 8

// 동적 계획법: 탑다운(재귀)과 바텀업(반복) 구현

/**
 * 1. 탑다운(Top-Down) 방식: 재귀 + 메모이제이션
 * @param {number} n - 피보나치 수의 위치
 * @param {Object} memo - 메모이제이션 객체
 * @returns {number} - n번째 피보나치 수
 */
function fibonacciTopDown(n, memo = {}) {
  if (n <= 1) return n // 기본 사례
  if (memo[n]) return memo[n] // 이미 계산된 값 사용

  // 결과를 계산하고 메모이제이션에 저장
  memo[n] = fibonacciTopDown(n - 1, memo) + fibonacciTopDown(n - 2, memo)
  return memo[n]
}

/**
 * 2. 바텀업(Bottom-Up) 방식: 반복 + DP 테이블
 * @param {number} n - 피보나치 수의 위치
 * @returns {number} - n번째 피보나치 수
 */
function fibonacciBottomUp(n) {
  if (n <= 1) return n // 기본 사례

  // DP 테이블 초기화
  const dp = [0, 1]

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

  return dp[n]
}

/**
 * 3. 바텀업 방식 (공간 최적화)
 * @param {number} n - 피보나치 수의 위치
 * @returns {number} - n번째 피보나치 수
 */
function fibonacciBottomUpOptimized(n) {
  if (n <= 1) return n // 기본 사례

  let prev1 = 1 // dp[i-1]
  let prev2 = 0 // dp[i-2]

  for (let i = 2; i <= n; i++) {
    const current = prev1 + prev2 // 현재 피보나치 값
    prev2 = prev1
    prev1 = current
  }

  return prev1
}

// 테스트 데이터
const n = 10

console.log(`탑다운 방식 (n=${n}):`, fibonacciTopDown(n))
console.log(`바텀업 방식 (n=${n}):`, fibonacciBottomUp(n))
console.log(`바텀업 방식 (공간 최적화, n=${n}):`, fibonacciBottomUpOptimized(n))

동적 계획법