[Python] Algorithm #05: 동적 계획법 (Dynamic Programming)

동적 계획법(Dynamic Programming, DP)의 개념과 문제 해결 방법을 다룹니다.

 

DP는 큰 문제를 작은 문제로 나누어 해결하고, 이미 계산한 결과를 저장하여 같은 계산을 반복하지 않는 방법입니다.

모든 문제를 DP로 해결할 수 있는 것은 아닙니다. 문제에 반복되는 부분 문제가 있는지, 작은 문제의 결과로 큰 문제를 만들 수 있는지 확인하는 것이 중요합니다.

---

1. 동적 계획법이란?

피보나치 수열은 다음과 같이 정의됩니다.

F(0) = 0
F(1) = 1
F(N) = F(N - 1) + F(N - 2)

 

이를 재귀 함수로 그대로 구현할 수 있습니다.

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

    return fibonacci(n - 1) + fibonacci(n - 2)

• 구현은 간단하지만 같은 값을 여러 번 계산합니다.

 

예를 들어 fibonacci(5)를 계산하는 과정에서 fibonacci(3), fibonacci(2) 등이 반복해서 호출됩니다.

이 방식의 시간복잡도는 약 O(2ⁿ)으로 매우 비효율적입니다.

 

이미 계산한 값을 저장해 다시 사용하면 중복 계산을 줄일 수 있습니다.

---

2. DP를 사용할 수 있는 조건

DP는 주로 다음 두 가지 특징을 가진 문제에서 사용할 수 있습니다.

 

중복되는 부분 문제

같은 작은 문제가 여러 번 반복해서 등장합니다.

피보나치 수열에서 동일한 fibonacci(n)이 여러 번 호출되는 것이 예시입니다.

 

최적 부분 구조

작은 문제의 최적해를 이용해 큰 문제의 최적해를 구할 수 있습니다.

예를 들어 어떤 위치까지의 최소 비용을 알고 있을 때, 그 값을 이용해 다음 위치까지의 최소 비용을 구할 수 있습니다.

 

문제에서 다음과 같은 표현이 보인다면 DP를 고려할 수 있습니다.

• 경우의 수
• 최댓값 또는 최솟값
• 특정 위치까지 도달하는 방법
• 이전 상태의 결과로 현재 상태를 계산

---

3. 메모이제이션: Top-Down

재귀 함수의 결과를 저장하여 같은 계산을 반복하지 않는 방식을 메모이제이션이라고 합니다.

memo = {}

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

    if n in memo:
        return memo[n]

    memo[n] = fibonacci(n - 1) + fibonacci(n - 2)

    return memo[n]

 

• 한 번 계산한 fibonacci(n)을 memo에 저장합니다.
• 같은 값이 다시 필요하면 재귀 호출 없이 저장된 값을 반환합니다.

 

리스트를 사용해 저장할 수도 있습니다.

def fibonacci(n):
    memo = [-1] * (n + 1)

    def dp(x):
        if (x <= 1):
            return x

        if (memo[x] != -1):
            return memo[x]

        memo[x] = dp(x - 1) + dp(x - 2)

        return memo[x]

    return dp(n)

• Top-Down 방식은 큰 문제에서 시작해 필요한 작은 문제를 재귀적으로 계산합니다.

---

4. 테이블 채우기: Bottom-Up

작은 문제부터 차례대로 계산해 큰 문제의 답을 만드는 방식을 Bottom-Up이라고 합니다.

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

    dp = [0] * (n + 1)
    dp[1] = 1

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

    return dp[n]

• dp[i]는 i번째 피보나치 수를 의미합니다.
• dp[0], dp[1]부터 시작해 필요한 값을 순서대로 채웁니다.
• 시간복잡도는 O(N), 공간복잡도는 O(N)입니다.

---

5. 공간 최적화

현재 값을 계산할 때 바로 이전의 두 값만 필요하므로 전체 리스트를 저장하지 않아도 됩니다.

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

    prev2 = 0
    prev1 = 1

    for _ in range(2, n + 1):
        current = prev1 + prev2
        prev2 = prev1
        prev1 = current

    return prev1

• 시간복잡도는 여전히 O(N)이지만, 공간복잡도는 O(1)이 됩니다.
• 다만 모든 DP 문제가 이처럼 공간을 줄일 수 있는 것은 아닙니다.

 

이전의 어떤 상태가 필요한지 확인해야 합니다.

---

6. DP 문제 해결 순서

DP 문제에서는 코드를 작성하기 전에 상태와 점화식을 정하는 것이 중요합니다.

 

다음 순서로 생각해볼 수 있습니다.

1. dp[i]가 무엇을 의미하는지 정의합니다.
2. 작은 입력의 정답인 초기값을 정합니다.
3. 이전 상태에서 현재 상태를 만드는 점화식을 찾습니다.
4. 계산 순서를 정합니다.
5. 최종적으로 반환할 값을 확인합니다.

 

가장 중요한 부분은 dp[i]의 의미를 한 문장으로 정확하게 정의하는 것입니다.

---

7. 계단 오르기 예제

한 번에 1칸 또는 2칸을 이동할 수 있을 때, N번째 계단에 도달하는 방법의 수를 구해보겠습니다.

 

상태 정의

dp[i] = i번째 계단에 도달하는 방법의 수

 

점화식

i번째 계단에는 다음 두 방법으로 도착할 수 있습니다.

• i - 1번째 계단에서 1칸 이동
• i - 2번째 계단에서 2칸 이동

 

따라서 점화식은 다음과 같습니다.

dp[i] = dp[i - 1] + dp[i - 2]

 

구현

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

    dp = [0] * (n + 1)
    dp[1] = 1
    dp[2] = 2

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

    return dp[n]

• 시간복잡도는 O(N), 공간복잡도는 O(N)입니다.

---

8. 최소 비용 예제

각 칸에 비용이 있고, 한 번에 1칸 또는 2칸 이동할 수 있다고 가정해보겠습니다.

 

마지막 칸까지 이동하는 최소 비용을 구할 수 있습니다.

cost = [10, 20, 15, 25, 10]

 

상태 정의

dp[i] = i번째 칸까지 이동하는 최소 비용

 

점화식

i번째 칸에는 i - 1 또는 i - 2번째 칸에서 올 수 있습니다.

dp[i] = min(dp[i - 1], dp[i - 2]) + cost[i]

 

구현

def min_cost(cost):
    n = len(cost)

    if (n == 1):
        return cost[0]

    dp = [0] * n
    dp[0] = cost[0]
    dp[1] = cost[1]

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

    return dp[n - 1]

• 문제의 이동 규칙과 시작 위치에 따라 초기값과 반환값은 달라질 수 있습니다.

---

9. 2차원 DP

상태를 하나의 값만으로 표현할 수 없다면 2차원 리스트를 사용할 수 있습니다.

 

격자의 왼쪽 위에서 오른쪽 아래로 이동하며 경로의 수를 구하는 상황을 생각해보겠습니다.

오른쪽 또는 아래쪽으로만 이동할 수 있다면 현재 칸에는 위쪽과 왼쪽에서 올 수 있습니다.

dp[row][col] = dp[row - 1][col] + dp[row][col - 1]

def count_paths(rows, cols):
    dp = [[0] * cols for _ in range(rows)]

    for row in range(rows):
        dp[row][0] = 1

    for col in range(cols):
        dp[0][col] = 1

    for row in range(1, rows):
        for col in range(1, cols):
            dp[row][col] = dp[row - 1][col] + dp[row][col - 1]

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

• 시간복잡도와 공간복잡도는 모두 O(rows × cols)입니다.

---

10. Top-Down과 Bottom-Up 비교

구분	Top-Down	Bottom-Up
구현 방식	재귀와 메모이제이션	반복문과 테이블
계산 순서	큰 문제에서 작은 문제로	작은 문제에서 큰 문제로
장점	점화식을 코드로 표현하기 자연스러움	재귀 호출 부담이 없고 실행 흐름이 명확함
주의점	재귀 깊이 제한	계산 순서를 직접 정해야 함

• 두 방식의 핵심은 모두 계산한 결과를 저장해 재사용하는 것입니다.
• 문제에 따라 더 자연스러운 방식을 선택하면 됩니다.

---

11. 자주 하는 실수/주의점

• dp[i]가 의미하는 값을 정하지 않고 코드부터 작성하지 않습니다.
• 초기값이 점화식에 맞는지 확인해야 합니다.
• 반복문의 시작과 끝 인덱스를 주의해야 합니다.
• 최댓값 문제인지 최솟값 문제인지에 따라 초기화 방법이 달라집니다.
• Top-Down에서 계산한 값을 저장하지 않으면 단순 재귀와 차이가 없습니다.
• 재귀 방식은 Python의 재귀 깊이 제한에 걸릴 수 있습니다.
• 2차원 리스트는 [[0] * M] * N이 아니라 [[0] * M for _ in range(N)]으로 생성합니다.

---

12. 종합 요약

• DP는 작은 문제의 결과를 저장하여 중복 계산을 줄이는 방법
• 중복되는 부분 문제와 최적 부분 구조가 있는지 확인
• Top-Down: 재귀와 메모이제이션
• Bottom-Up: 반복문으로 DP 테이블 채우기
• dp[i]의 의미, 초기값, 점화식, 계산 순서를 먼저 결정
• 필요한 이전 상태가 적다면 공간복잡도를 줄일 수 있음
• 경우의 수, 최댓값, 최솟값 문제에서 자주 활용