Chapter 08. 동적 프로그래밍

동적 프로그래밍 (기초 문제 풀이)

혼자 힘으로 풀어 보기

01타일: https://www.acmicpc.net/problem/1904

문제 제목: 01타일
문제 난이도: 하(Easy)
문제 유형: 동적 프로그래밍
추천 풀이 시간: 20분

문제 풀이 핵심 아이디어

• 사용할 수 있는 타일의 종류는 2개입니다.

• 두 가지 종류의 타일을 이용하여, N 길이의 수열을 만드는 모든 경우의 수를 구해야 합니다.

• 가장 전형적인 동적 프로그래밍 문제입니다.

• N이 최대 1,000,000이므로 시간 복잡도 O(N)으로 해결해야 합니다.
  

• 타일을 왼쪽에서부터 오른쪽으로 이어서 붙인다고 가정합니다.

• 예를 들어 N = 3일때, 경우의 수는 3가지입니다.
  

• 예를 들어 N=4일 때, 경우의 수는 5가지 입니다.
  

• 동적 프로그래밍 문제를 풀기 위해서는 점화식(인접한 항들사이의 관계식)을 세워야 합니다.

• D[i] = '수열의 길이가 i일 때의 경우의 수'라고 합시다.

• 예를 들어 D[3] = 3, D[4] = 5 입니다.

• 타일을 왼쪽에서부터 오른쪽으로 이어서 붙인다고 가정합시다.

• 생각해 보면, 길이가 i인 수열을 형성하는 방법은 다음의 두 가지 뿐입니다.
  

• 따라서 D[i] = '수열의 길이가 i일 때의 경우의 수'라고 하면,

• D[i] = D[i-1]+D[i-2]

• 다시 말해 이 문제는 피보나치 수열과 동일한 문제입니다.

소스 코드

n = int(input())

dp = [0] * 1000001
dp[1] = 2
dp[2] = 2

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

print(dp[n])

혼자 힘으로 풀어 보기

평범한 배낭: https://www.acmicpc.net/problem/12865

문제 제목: 평범한 배낭
문제 난이도: 하(Easy)
문제 유형: 동적 프로그래밍
추천 풀이 시간: 30분

문제 풀이 핵심 아이디어

• 배낭 문제(Knapsack Problem)으로도 알려져 있는, 전형적인 동적 프로그래밍 문제입니다.
• 물품의 수가 N, 배낭에 담을수 있는 무게가 K입니다.
• 동적 프로그래밍을 이용하여 시간 복잡도 O(NK)로 문제를 해결할 수 있습니다.
• 핵심 아이디어: 모든 무게에 대하여 최대 가치를 저장하기
• D[i][j] = 배낭에 넣은 물품의 무게 합이 j일 때 얻을 수 있는 최대 가치
• 각 물품의 번호 i에 따라서 최대 가치 테이블 D[i][j]를 갱신하여 문제를 해결할 수 있습니다.
• D[i][j] = D[i-1][j] (if j < W[i]), max(D[i-1][j], D[i-1][j-W[i]] + V[i]) (if j >= W[i])
• 예를 들어 N=4, K=7일 때의 예시를 확인해 봅시다.
  

소스 코드

n, k = map(int, input().split())
dp = [[0] * (k+1) for _ in range(n+1)]

for i in range(1, n+1):
    weight, value = map(int, input().split())
    for j in range(1, k+1):
        if j < weight:
            dp[i][j] = dp[i-1][j]
        else:
            dp[i][j] = max(dp[i-1][j], dp[i-1][j-weight] + value)

print(dp[n][k])

혼자 힘으로 풀어 보기

가장 긴 증가하는 부분 수열: https://www.acmicpc.net/problem/11053

문제 제목: 가장 긴 증가하는 부분 수열
문제 난이도: 하(Easy)
문제 유형: 동적 프로그래밍, LIS
추천 풀이 시간: 30분

문제 풀이 핵심 아이디어

• 가장 긴 증가하는 부분 수열(LIS) 문제는, 전형적인 동적 프로그래밍 문제입니다.
• 수열의 크기가 N일 때, 기본적인 동적 프로그래밍 알고리즘으로 O(N^2)에 해결할 수 있습니다.
• D[i] = array[i]를 마지막 원소로 가지는 부분 수열의 최대 길이
• 모든 0 <= j < i에 대하여, D[i] = max(D[i], D[j]+1) if array[j] < array[i]
• N = 6일 때, 예시 수열에 대하여 다음과 같이 계산할 수 있습니다.
  

소스 코드

n = int(input())
array = list(map(int, input().split())
dp = [1] * n

for i in range(1, n):
    for j in range(0, 1):
        if array[j] < array[i]:
            dp[i] = max(dp[i], dp[j] + 1)

print(max(dp))

동적 프로그래밍 (핵심 유형 문제풀이)

혼자 힘으로 풀어 보기

LCS: https://www.acmicpc.net/problem/9251

문제 제목: LCS
문제 난이도: 하(Easy)
문제 유형: 동적 프로그래밍, LCS
추천 풀이 시간: 30분

문제 풀이 핵심 아이디어

• 두 수열이 주어졌을 때, 두 수열 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾아야 합니다.
• 가장 긴 공통 부분 수열(LCS)문제로 알려진 대표적인 동적 프로그래밍 문제입니다.
• 두 수열의 길이가 N 미만일 때, 시간복잡도 O(N^2)으로 문제를 해결할 수 있습니다.
• 두 수열을 각각 X, Y라고 합시다.
• D[i][j] = X[0...i]와 Y[0...j]의 공통 부분 수열의 최대 길이
• 두 문자열의 길이를 조금씩 늘려 가며 확인하여, 공통 부분 수열의 최대 길이를 계산합니다.
• D[i][j] = D[i-1][j-1]+1 (if X[i] = Y[j]), max(D[i][j-1], D[i-1][j]) (if X[i] != Y[j])
• X는 "ACAYKP"이고, Y는 "CAPCAK"일 때
  

소스 코드

x = input()
y = input()

dp = [[0] * (len(y) + 1) for _ in range(len(x) +1)]

for i in range(1, len(x) + 1):
    for j in range(1, len(y) + 1):
        if x[i-1] == y[j-1]:
            dp[i][j] = dp[i-1][j-1] +1
        else:
            dp[i][j] = max(dp[i][j-1], dp[i-1][j])

print(dp[len(x)][len(y)])

혼자 힘으로 풀어 보기

기타리스트: https://www.acmicpc.net/problem/1495

문제 제목: 기타리스트
문제 난이도: 중(Medium)
문제 유형: 동적 프로그래밍
추천 풀이 시간: 40분

문제 풀이 핵심 아이디어

• 차례대로 곡을 연주한다는 점에서, 동적 프로그래밍으로 해결할 수 있는 문제입니다.
• 곡의 개수가 N, 볼륨의 최댓값은 M입니다.
• 동적 프로그래밍을 이용하여 시간 복잡도 O(NM)으로 문제를 해결할 수 있습니다.
• 핵심 아이디어: 모든 볼륨에 대하여 연주 가능 여부를 계산하기
• D[i][j+1] = i번째 노래일 때 j크기의 불륨으로 연주 가능한지 여부
• 노래를 순서대로 확인하며, 매 번 모든 크기의 불륨에 대하여 검사합니다.
• D[i][j-V[i]] = True if D[i-1][j] = True
• D[i][j+V[i]] = True if D[i-1][j] = True
• N = 3, S = 5, M = 10일 때의 예시를 확인해 봅시다.
  

소스 코드

n, s, m = map(int, input().split())
array = list(map(int, input().split()))

dp = [[0] * (m+1) for _ in range(n+1)]

for i in range(1, n+1):
    for j in range(m+1):
        if dp[i-1][j] == 0:
            coutinue
        if j - array[i-1] >= 0:
            dp[i][j-array[i-1]] = 1
        if j + array[i-1] <= m:
            dp[i][j+array[i-1]] = 1

result = -1
for i in range(m, -1, -1):
    if dp[n][i] == 1:
        result = i
        break

print(result)

혼자 힘으로 풀어 보기

가장 높은 탑 쌓기: https://www.acmicpc.net/problem/2655

문제 제목: 가장 높은 탑 쌓기
문제 난이도: 상(Hard)
문제 유형: 동적 프로그래밍, LIS
추천 풀이 시간: 50분

문제 풀이 핵심 아이디어

• 가장 긴 증가하는 부분 수열(LIS) 문제의 심화 변형 문제입니다.
• 벽돌의 수가 N개일 때, 시간 복잡도 O(N^2)으로 해결할 수 있습니다.
• 벽돌의 번호를 출력해야 한다는 점에서, 계산된 테이블을 역추적할 수 있어야 합니다.
• 가장 먼저 벽돌을 무게 기준으로 정렬합니다.
• D[i] = 인덱스가 i인 벽돌을 가장 아래에 두었을 때의 최대 높이
• 각 별돌에 대해서 확인하며 D[i]를 갱신합니다.
• 모든 0<=j<i에 대하여, D[i] = max(D[i],D[j]+height[i]) if area[i] > area[j]
• N = 5일 때, 예시 벽돌들에 대하여 다음과 같이 계산할 수 있습니다.
  

소스 코드

n = int(input())
array = []

array.append((0,0,0,0))
for i in range(1, n+1):
    area, heigjt, weight = map(int, input().split())
    array.append((i, area, height, weight))

# 무게를 기준으로 정렬합니다.
array.sort(key=lambda data: data[3])

dp = [0] * (n+1)

for i in range(1, n+1):
    for j in range(0,i):
        if array[i][1] > array[j][1]:
            dp[i] = max(dp[i], dp[j] + array[i][2])

max_value = max(dp)
index = n 
result = []

while index != 0:
    if max_value == dp[index]:
        result.append(array[index][0])
        max_value -= array[index][2]
    index -= 1

result.reverse()
print(len(result))
[print(i) for i in result]