동적 계획법(Dynamic Programming, DP) - DP

DP란 무엇일까? 동적 계획법은 큰 문제를 여러 개의 작은 문제로 나누어 해결한 후, 그 결과를 저장하여 전체 문제를 효율적으로 해결하는 방법이다. 예를 들어, 큰 퍼즐을 맞출 때, 각 조각을 따로 기억해둔다면 다시 같은 조각을 찾지 않아도 된다.

 

 

DP의 핵심 개념

  • 부분 문제(Overlapping Subproblems) : 큰 문제를 해결하는 과정에서 동일한 작은 문제가 여러 번 반복되는 경우가 있다.
  • 최적 부분 구조(Optimal Substructure) : 문제의 최적해가 그 하위 문제들의 최적해로 구성될 수 있을 때, DP를 적용할 수 있다.

 

 

대표 문제 : 계단 오르기

 - 문제 설명 : 계단이 총 n개 있고, 한 번에 1계단 또는 2계단씩 오를 수 있을 때, 계단을 모두 오르는 방법의 수를 구하시오.

 - 예시 : n = 3일때, 가능한 경우는

  1.      1,1,1
  2.      1,2
  3.      2,1

   총 3가지 방법

 

 

 - 문제 해결을 위한 아이디어

  • 계단 오르기 문제는 작은 문제(예 : n-1 계단을 오르는 방법, n-2 계단을 오르는 방법)로 나누어 생각할 수 있다.
  • 점화식 : n 번째 계단에 도달하는 방법의 수는 dp[n] = dp[n-1] + dp[n-2] 이다. 왜냐하면 마지막에 한 계단을 오르는 경우와 두 계단을 오르는 경우로 나눌 수 있기 때문이다.
  • 기본 조건 : dp[0] = 1 (아무 계단도 오르지 않은 경우를 1가지 방법으로 간주) / dp[1] = 1 (첫 번째 계단까지 오르는 방법은 1가지)

 

1. 반복적(Bottom-Up) 방식으로 DP 구현하기

fun climbStairs(n: Int): Int {
    // n이 0 또는 1인 경우 바로 반환
    if (n <= 1) return 1

    // dp 배열 생성: dp[i]는 i번째 계단까지 도달하는 방법의 수
    val dp = IntArray(n + 1)
    dp[0] = 1
    dp[1] = 1

    // 2번째 계단부터 n번째 계단까지 방법의 수를 구함
    for (i in 2..n) {
        dp[i] = dp[i - 1] + dp[i - 2]
    }
    return dp[n]
}

fun main() {
    val n = 5  // 예를 들어 계단이 5개인 경우
    println("계단 $n개를 오르는 방법의 수: ${climbStairs(n)}")
    // 출력 예시: 계단 5개를 오르는 방법의 수: 8
}

 

 

2. 재귀와 메모이제이션을 활용한 방식

fun climbStairsRecursive(n: Int, memo: MutableMap<Int, Int> = mutableMapOf()): Int {
    // n이 0 또는 1이면 바로 반환
    if (n <= 1) return 1
    // 이미 계산된 값이면 바로 반환
    if (memo.containsKey(n)) return memo[n]!!

    // 재귀 호출과 메모이제이션
    memo[n] = climbStairsRecursive(n - 1, memo) + climbStairsRecursive(n - 2, memo)
    return memo[n]!!
}

fun main() {
    val n = 5
    println("재귀적 접근: 계단 $n개를 오르는 방법의 수: ${climbStairsRecursive(n)}")
    // 출력 예시: 재귀적 접근: 계단 5개를 오르는 방법의 수: 8
}

// 같은 계산을 반복하지 않도록, 한 번 계산한 결과를 memo에 저장한다. 이렇게 하면, 재귀 호출의 중복을 피할 수 있다.

+ Recent posts