[코딩 테스트] 20일차: 동적 프로그래밍

동적 프로그래밍 (Dynamic Programming)

동적 프로그래밍은 복잡한 문제를 더 작은 부분 문제로 나누어 해결하는 방법입니다. 부분 문제의 해결 결과를 저장하여 동일한 부분 문제를 다시 계산하지 않도록 합니다. 동적 프로그래밍은 주로 최적화 문제에 사용되며, 메모이제이션(Memoization)과 타뷸레이션(Tabulatioon) 두 가지 방법으로 구현할 수 있습니다.

동적 프로그래밍의 주요 개념

• 부분 문제(Subproblem): 원래 문제를 구성하는 더 작은 문제
• 최적 부분 구조(Optimal Substructure): 부분 문제의 최적 해를 이용하여 원래 문제의 최적 해를 구할 수 있는 구조
• 중복되는 부분 문제(Overlapping Subproblems): 동일한 부분 문제가 여러 번 반복되는 문제 구조

메모이제이션 (Memoization)

메모이제이션은 재귀를 사용하여 부분 문제의 해결 결과를 저장하는 방법입니다. 이를 통해 동일한 부분 문제를 다시 계산하지 않도록 합니다.

예제: 피보나치 수열 (메모이제이션)

JavaScript

function fibonacci(n, memo = {}) {
  if (n <= 1) {
    return n;
  }
  if (memo[n]) {
    return memo[n];
  }
  memo[n] = fibonacci(n - 1, memo) + fibonacci(n - 2, memo);
  return memo[n];
}

console.log(fibonacci(6)); // 8
console.log(fibonacci(50)); // 12586269025

Python

def fibonacci(n, memo={}):
    if n <= 1:
        return n
    if n in memo:
        return memo[n]
    memo[n] = fibonacci(n - 1, memo) + fibonacci(n - 2, memo)
    return memo[n]

print(fibonacci(6)) # 8
print(fibonacci(50)) # 12586269025

타뷸레이션 (Tabulation)

타뷸레이션은 반복문을 사용하여 부분 문제의 해결 결과를 저장하는 방법입니다. 일반적으로 하향식 접근법을 사용하는 메모이제이션과 달리, 타뷸레이션은 상향식 접근법을 사용합니다.

예제: 피보나치 수열 (타뷸레이션)

JavaScript

function fibonacci(n) {
  if (n <= 1) {
    return n;
  }

  let fib = [0, 1];
  for (let i = 2; i <= n; i++) {
    fib[i] = fib[i - 1] + fib[i - 2];
  }
  return fib[n];
}

console.log(fibonacci(6)); // 8
console.log(fibonacci(50)); // 12586269025

Python

def fibonacci(n):
    if n <= 1:
        return n

    fib = [0, 1]
    for i in range(2, n + 1):
        fib.append(fib[i - 1] + fib[i - 2])
    return fib[n]

print(fibonacci(6)) # 8
print(fibonacci(50)) # 12586269025

동적 프로그래밍의 대표적인 예제

예제 1: 계단 오르기

계단을 1계단 또는 2계단씩 오를 수 있을 때, n계단을 오르는 방법의 수를 구하세요.

JavaScript

function climbStairs(n) {
  if (n <= 2) {
    return n;
  }

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

console.log(climbStairs(3)); // 3
console.log(climbStairs(5)); // 8

Python

def climb_stairs(n):
    if n <= 2:
        return n

    dp = [1, 2]
    for i in range(3, n + 1):
        dp.append(dp[-1] + dp[-2])
    return dp[-1]

print(climb_stairs(3)) # 3
print(climb_stairs(5)) # 8

예제 2: 배낭 문제

주어진 무게 제한을 초과하지 않으면서 최대 가치를 얻을 수 있는 아이템의 조합을 찾으세요.

JavaScript

function knapSack(W, weights, values, n) {
  let dp = Array(n + 1)
    .fill(null)
    .map(() => Array(W + 1).fill(0));

  for (let i = 0; i <= n; i++) {
    for (let w = 0; w <= W; w++) {
      if (i === 0 || w === 0) {
        dp[i][w] = 0;
      } else if (weights[i - 1] <= w) {
        dp[i][w] = Math.max(
          values[i - 1] + dp[i - 1][w - weights[i - 1]],
          dp[i - 1][w]
        );
      } else {
        dp[i][w] = dp[i - 1][w];
      }
    }
  }
  return dp[n][W];
}

let values = [60, 100, 120];
let weights = [10, 20, 30];
let W = 50;
let n = values.length;

console.log(knapSack(W, weights, values, n)); // 220

Python

def knapSack(W, weights, values, n):
    dp = [[0 for _ in range(W + 1)] for _ in range(n + 1)]

    for i in range(n + 1):
        for w in range(W + 1):
            if i == 0 or w == 0:
                dp[i][w] = 0
            elif weights[i - 1] <= w:
                dp[i][w] = max(values[i - 1] + dp[i - 1][w - weights[i - 1]], dp[i - 1][w])
            else:
                dp[i][w] = dp[i - 1][w]

    return dp[n][W]

values = [60, 100, 120]
weights = [10, 20, 30]
W = 50
n = len(values)

print(knapSack(W, weights, values, n)) # 220

연습 문제

문제 1: 최소 비용 계단 오르기

계단의 각 계단마다 비용이 주어질 때, 계단을 오르는 최소 비용을 구하세요. 한 번에 한 계단 또는 두 계단씩 오를 수 있습니다.

JavaScript

function minCostClimbingStairs(cost) {
  let n = cost.length;
  let dp = new Array(n);
  dp[0] = cost[0];
  dp[1] = cost[1];

  for (let i = 2; i < n; i++) {
    dp[i] = cost[i] + Math.min(dp[i - 1], dp[i - 2]);
  }

  return Math.min(dp[n - 1], dp[n - 2]);
}

let cost = [10, 15, 20];
console.log(minCostClimbingStairs(cost)); // 15

cost = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1];
console.log(minCostClimbingStairs(cost)); // 6

Python

def minCostClimbingStairs(cost):
    n = len(cost)
    dp = [0] * n
    dp[0] = cost[0]
    dp[1] = cost[1]

    for i in range(2, n):
        dp[i] = cost[i] + min(dp[i - 1], dp[i - 2])

    return min(dp[n - 1], dp[n - 2])

cost = [10, 15, 20]
print(minCostClimbingStairs(cost)) # 15

cost = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1]
print(minCostClimbingStairs(cost)) # 6

문제 2: 최대 서브어레이 합

주어진 배열에서 연속된 부분 배열의 합 중에서 가장 큰 합을 구하세요.

JavaScript

function maxSubArray(nums) {
  let maxSoFar = nums[0];
  let maxEndingHere = nums[0];

  for (let i = 1; i < nums.length; i++)

 {
    maxEndingHere = Math.max(nums[i], maxEndingHere + nums[i]);
    maxSoFar = Math.max(maxSoFar, maxEndingHere);
  }

  return maxSoFar;
}

let nums = [-2,1,-3,4,-1,2,1,-5,4];
console.log(maxSubArray(nums)); // 6

Python

def maxSubArray(nums):
    max_so_far = nums[0]
    max_ending_here = nums[0]

    for i in range(1, len(nums)):
        max_ending_here = max(nums[i], max_ending_here + nums[i])
        max_so_far = max(max_so_far, max_ending_here)

    return max_so_far

nums = [-2,1,-3,4,-1,2,1,-5,4]
print(maxSubArray(nums)) # 6

결론

이번 글에서는 코딩 테스트 준비를 위해 동적 프로그래밍에 대해 배웠습니다. 이를 통해 동적 프로그래밍의 개념, 메모이제이션과 타뷸레이션의 차이, 그리고 다양한 예제를 통해 동적 프로그래밍 문제를 해결하는 방법을 익혔습니다. 다음 글에서는 분할 정복에 대해 알아보겠습니다.

다음 글에서 만나요!