동적 계획법의 개념과 점화식, 문제풀이

동적 계획법(Dynamic Programming, DP)은 복잡한 문제를 작은 부분 문제로 나누어 해결하는 효율적인 알고리즘 기법입니다. 동적 계획법은 문제를 더 작은 하위 문제들로 나누어 계산하며, 이미 해결한 하위 문제의 결과를 저장해 재활용함으로써 반복되는 계산을 방지합니다.

주로 최적화 문제와 경로 탐색 문제에서 사용되며, 피보나치 수열 계산, 최단 경로, 배낭 문제(knapsack)와 같은 대표적인 예제를 포함합니다.

동적 계획법은 이전에 계산한 결과를 저장하고 재활용하는 방법으로, 같은 문제를 여러 번 계산하지 않도록 함으로써 성능을 크게 향상시킵니다. 이 접근법은 재귀적으로 하위 문제를 반복하여 계산하는 대신, 계산 결과를 저장해 중복 계산을 피하는 점에서 매우 효율적입니다.

DP의 구현 방식은 주로 Bottom-Up (상향식)과 Top-Down (하향식) 접근으로 나뉩니다:

• Bottom-Up 접근법: 작은 문제를 먼저 해결해, 큰 문제로 점차 확장해 나갑니다. for 반복문을 통해 문제를 풀어나갑니다.
• Top-Down 접근법: 큰 문제를 작은 문제로 나누어 해결하며, 재귀적 방식과 메모이제이션(memoization)을 사용해 중복 연산을 방지합니다.

DP의 장점

• 동일한 하위 문제를 여러 번 계산하지 않아 효율적입니다.
• 복잡한 문제를 체계적이고 간단하게 해결할 수 있습니다.
• 많은 최적화 문제에서 효과적입니다.

예제 문제: "한 사람이 계단을 올라갈 때, 한 번에 1계단 또는 2계단을 오를 수 있습니다. n개의 계단이 있을 때, 이를 오르는 방법의 수는 몇 가지일까요?" 이 문제를 DP로 해결하기 위해, 문제를 작은 문제로 분해하고, 이전 계산을 재활용하는 방식으로 점진적으로 최종 해답을 구할 수 있습니다.

점화식은 DP에서 문제를 정의하고, 큰 문제와 작은 문제 간의 관계를 수식으로 표현하는 역할을 합니다. 점화식이 올바르게 정의되면 문제를 풀어가는 체계적인 과정이 가능합니다.

점화식을 구성하는 것은 DP 문제 풀이의 첫걸음입니다. 일반적으로, 작은 문제에서 큰 문제로 확장하는 관계를 정의하고, 이를 바탕으로 문제를 해결하는 단계로 나아갑니다.

앞서 소개한 계단 오르기 문제는 동적 계획법을 통해 효율적으로 해결할 수 있습니다. 계단의 수가 n일 때, 한 번에 1계단 또는 2계단을 오를 수 있는 경우의 수를 계산해봅시다.

문제 정의 및 점화식 설정

현재 계단을 오르는 방법은 이전 계단에서 1계단을 오르는 경우와, 두 계단 아래에서 2계단을 오르는 경우 두 가지가 있습니다. 따라서 점화식은 다음과 같이 정의할 수 있습니다:

Ways(n) = Ways(n-1) + Ways(n-2)

이 점화식을 바탕으로 상향식 DP 방식으로 문제를 해결해 봅시다.

Python 코드 예제:
def climb_stairs(n):
    if n <= 1:
        return 1
    dp = [0] * (n + 1)  # DP 배열 초기화
    dp[1] = 1
    dp[2] = 2

    for i in range(3, n + 1):
        dp[i] = dp[i - 1] + dp[i - 2]  # 점화식 적용

    return dp[n]

# 예제 사용
print(climb_stairs(5))  # 출력: 8
                

설명: climb_stairs 함수는 계단 수에 따라 오를 수 있는 모든 경우의 수를 계산합니다. 이전 계단들의 결과를 재활용해 계산 속도를 크게 향상시키며, 중복 계산을 피할 수 있습니다.

다음 예제는 일정한 비용이 드는 칸을 이동하여 최종 도착지에 도달하는 문제입니다. DP를 통해 최소 비용으로 도착하는 경로를 계산해 보겠습니다.

문제 정의: 비용이 주어진 각 칸에서 한 칸 또는 두 칸씩 이동할 수 있을 때, 최종 칸까지의 최소 비용을 계산하는 문제입니다.

점화식: 현재 위치에서의 최소 비용은 이전 두 칸 중 최소 비용으로 이동하는 값에 해당 칸의 비용을 더한 값이 됩니다. Cost(n) = min(Cost(n-1), Cost(n-2)) + cost[n]로 정의됩니다.

Python 코드 예제:
def min_cost_climb(cost):
    n = len(cost)
    dp = [0] * (n + 1)  # 결과를 저장할 배열 생성
    dp[0] = 0
    dp[1] = cost[0]

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

    return dp[n]

# 예제 사용
cost = [10, 15, 20]
print(min_cost_climb(cost))  # 출력: 15
                

설명: min_cost_climb 함수는 현재 칸까지 도달하는 데 필요한 최소 비용을 계산합니다. 이전 칸의 결과를 재활용하여 중복 계산을 방지하며, 효율적으로 최적의 경로를 찾습니다.

동적 계획법을 사용할 때, 문제 해결을 보다 체계적으로 접근할 수 있는 몇 가지 팁을 소개합니다.

• 1. 작은 단위로 문제를 나누어보기 - 문제를 더 작고 간단한 하위 문제들로 나누어 해결할 수 있어야 합니다.
• 2. 점화식 구성 - 큰 문제와 작은 문제의 관계를 나타낼 수 있는 점화식을 설정하는 것이 핵심입니다.
• 3. 메모이제이션 사용 - 이미 계산한 부분 문제의 결과를 저장하여 중복 계산을 방지합니다.
• 4. Bottom-Up과 Top-Down 방식 선택 - 문제에 따라 두 가지 방식 중 더 효율적인 방법을 선택합니다.

이 팁들을 통해 DP를 보다 효율적이고 정확하게 사용할 수 있습니다. 또한, 연습을 통해 점화식과 DP 배열의 구조를 빠르게 파악하는 능력을 기를 수 있습니다.