[알고리즘] 다이나믹 프로그래밍2 : 더 많은 예제 풀이

다이나믹 프로그래밍이 중요한 만큼 더 많은 문제를 풀어보자!

다이나믹 프로그래밍이란?

이전 포스팅에서도 설명했지만 다시 한번 짚고 넘어가자면 다이나믹 프로그래밍$DP$은 복잡한 문제를 해결하기 위한 알고리즘 기법 중 하나로, 작은 하위 문제들을 해결한 결과를 이용하여 더 큰 문제를 해결하는 방법입니다. 이를 통해 중복 계산을 줄이고 효율적으로 문제를 풀 수 있습니다.

핵심 개념

1. 문제 분할: 문제를 여러 하위 문제로 나눕니다.
2. 중복 계산 제거: 동일한 하위 문제를 여러 번 계산하지 않도록 메모이제이션을 사용합니다.
3. 최적 부분 구조: 문제의 최적 해가 부분 문제의 최적 해로 구성됩니다.

저번에 대강 넘어갔던 부분이긴 합니다. DP를 사용하기 위해선 위와 같은 핵심 개념이 성립해야 풀 수 있기 때문에 이 점을 주의하시면 좋을 것 같습니다. 

문제 풀이 예제

문제 15988: 1, 2, 3 더하기 3

정수 nnn을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 문제입니다.

• 점화식: dp[n]=dp[n−1]+dp[n−2]+dp[n−3]dp[n] = dp[n-1] + dp[n-2] + dp[n-3]dp[n]=dp[n−1]+dp[n−2]+dp[n−3]
• 기저 조건: dp[0]=1,dp[1]=1,dp[2]=2,dp[3]=4dp[0] = 1, dp[1] = 1, dp[2] = 2, dp[3] = 4dp[0]=1,dp[1]=1,dp[2]=2,dp[3]=4

MOD = 1000000009

def count_ways(n):
    dp = [0] * (n + 1)
    dp[0] = 1
    dp[1] = 1
    if n > 1:
        dp[2] = 2
    if n > 2:
        dp[3] = 4

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

    return dp[n]

# 입력 처리
t = int(input())
results = []
for _ in range(t):
    n = int(input())
    results.append(count_ways(n))

# 결과 출력
for result in results:
    print(result)

• 참고 사항 : % 1000000009가 필요한 이유? : https://www.acmicpc.net/board/view/129686

문제 1149: RGB거리

 

집을 빨강, 초록, 파랑으로 칠하는 비용을 최소화하는 문제입니다.

• 점화식: dp[i][0]=cost[i][0]+min⁡$dp[i−1][1],dp[i−1][2]$dp[i][0] = cost[i][0] + \min$dp[i-1][1], dp[i-1][2]$dp[i][0]=cost[i][0]+min(dp[i−1][1],dp[i−1][2])
• 기저 조건: dp[0][0]=cost[0][0]dp[0][0] = cost[0][0]dp[0][0]=cost[0][0]

def min_cost_to_paint_houses(costs):
    n = len(costs)
    dp = [[0] * 3 for _ in range(n)]
    
    dp[0][0] = costs[0][0]
    dp[0][1] = costs[0][1]
    dp[0][2] = costs[0][2]

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

    return min(dp[n-1])

# 입력 처리
n = int(input())
costs = [list(map(int, input().split())) for _ in range(n)]
print(min_cost_to_paint_houses(costs))

문제 11055: 가장 큰 증가 부분 수열

 

수열에서 가장 큰 증가 부분 수열의 합을 구하는 문제입니다.

• 점화식: dp[i]=max⁡$dp[j]$+arr[i]dp[i] = \max$dp[j]$ + arr[i]dp[i]=max(dp[j])+arr[i] $0 ≤ j < i, arr[j] < arr[i]$
• 기저 조건: dp[i]=arr[i]dp[i] = arr[i]dp[i]=arr[i]

def largest_increasing_subsequence_sum(arr):
    n = len(arr)
    dp = [0] * n
    
    for i in range(n):
        dp[i] = arr[i]
        for j in range(i):
            if arr[j] < arr[i]:
                dp[i] = max(dp[i], dp[j] + arr[i])
    
    return max(dp)

# 입력 처리
n = int(input())
arr = list(map(int, input().split()))
print(largest_increasing_subsequence_sum(arr))

문제 13398: 연속합 2

 

한 개의 수를 제거하여 얻을 수 있는 가장 큰 연속 부분합을 구하는 문제입니다.

• 점화식: dp[i][0]=max⁡$dp[i−1][0]+arr[i],arr[i]$dp[i][0] = \max$dp[i-1][0] + arr[i], arr[i]$dp[i][0]=max(dp[i−1][0]+arr[i],arr[i]), dp[i][1]=max⁡$dp[i−1][1]+arr[i],dp[i−1][0]$dp[i][1] = \max$dp[i-1][1] + arr[i], dp[i-1][0]$dp[i][1]=max(dp[i−1][1]+arr[i],dp[i−1][0])
• 기저 조건: dp[0][0]=arr[0],dp[0][1]=arr[0]dp[0][0] = arr[0], dp[0][1] = arr[0]dp[0][0]=arr[0],dp[0][1]=arr[0]

def max_sum_with_one_removal(arr):
    n = len(arr)
    if n == 1:
        return arr[0]
    
    dp = [[0] * 2 for _ in range(n)]
    dp[0][0] = arr[0]
    dp[0][1] = arr[0]

    max_sum = arr[0]

    for i in range(1, n):
        dp[i][0] = max(dp[i-1][0] + arr[i], arr[i])
        dp[i][1] = max(dp[i-1][1] + arr[i], dp[i-1][0])
        max_sum = max(max_sum, dp[i][0], dp[i][1])

    return max_sum

# 입력 처리
n = int(input())
arr = list(map(int, input().split()))
print(max_sum_with_one_removal(arr))

문제 2133: 타일 채우기

3×N 크기의 벽을 2×1과 1×2 타일로 채우는 모든 방법의 수를 계산하는 문제입니다.

• 점화식: dp[n]=dp[n−2]×3+∑k=4,6,8,…ndp[n−k]×2dp[n] = dp[n-2] \times 3 + \sum_{k=4, 6, 8, \ldots}^{n} dp[n-k] \times 2dp[n]=dp[n−2]×3+∑k=4,6,8,…n​dp[n−k]×2
• 기저 조건: dp[0]=1,dp[2]=3dp[0] = 1, dp[2] = 3dp[0]=1,dp[2]=3

def tile_filling(n):
    if n % 2 != 0:
        return 0
    
    dp = [0] * (n + 1)
    dp[0] = 1
    dp[2] = 3
    
    for i in range(4, n + 1, 2):
        dp[i] = dp[i-2] * 3
        for j in range(4, i + 1, 2):
            dp[i] += dp[i-j] * 2
    
    return dp[n]

# 입력 처리
n = int(input())
print(tile_filling(n))

 

• 참고자료 : https://velog.io/@yje876/python%EB%B0%B1%EC%A4%80DP-2133-%ED%83%80%EC%9D%BC-%EC%B1%84%EC%9A%B0%EA%B8%B0

[python/백준/DP] 2133 : 타일 채우기

---

Pypy3로 제출하면 통과되는 경우

이럴때, Pypy3로 돌리면 또 맞는...

써도 됩니다! 오히려 쓰라고 권장하고 있습니다. 저도 python3로만 해결해야한다고 생각했지만 백준이 Python3에 친화적이지 않기도 하고 시간복잡도를 줄일 수 있는 좋은 방법이 이미 있는데 안쓸 이유가 없다고 합니다. 

그럼에도 불구하고 Python3에서 시간 복잡도를 줄이면서 얻는 공부들이 있을 것 아니냐? 라는 질문도 있을 수 있겠지만 그걸로 공부의 흥미를 잃을 바에는 다른 문제를 더 풀어보는 것이 도움된다고 합니다.

참고 : https://djm03178.tistory.com/16

PyPy3로 제출하면 통과됩니다.

결론

다이나믹 프로그래밍은 큰 문제를 작은 문제로 나누어 해결하는 강력한 기법입니다. 다양한 문제에서 이를 활용하여 효율적인 해결책을 찾을 수 있습니다. 문제의 특성을 파악하고 점화식을 세우는 것이 중요합니다. 추가적으로 Pypy3를 써도 되는지에 대해서도 추가적으로 작성해봤습니다.