[유형별 기출문제] 다이나믹 프로그래밍

본 포스팅은 나동빈 저자의 ‘이것이 취업을 위한 코딩테스트’를 공부하며 정리한 노트입니다.

다이나믹 프로그래밍

어떤 문제는 메모리 공간을 약간 더 사용하면 연산 속도를 비약적으로 증가시킬 수 있는 방법이 있다. 대표적인 방법이 다이나믹 프로그래밍이다. 다이나믹 프로그래밍은 다음 조건을 만족할 때 사용할 수 있다.

• 큰 문제를 작은 문제로 나눌 수 있을 때
• 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일할 때

정리하자면 다이나믹 프로그래밍이란 큰 문제를 작게 나누고, 한 번 해결된 부분 문제의 정답을 메모리에 기록하여, 문제를 효율적으로 해결하는 알고리즘 기법이다.

다이나믹 프로그래밍 문제를 푸는 방법

완전 탐색 알고리즘으로 접근했을 때 시간이 매우 오래 걸리면 다이나믹 프로그래밍을 적용할 수 있는지 해결하고자 하는 부분 문제들의 중복 여부를 확인해본다. 문제를 풀기 전에 문제를 도식화하여 동일하게 여러 번 호출되는 과정이 있는지 살펴본다. 문제에서 요구하는 내용을 점화식(인접한 항들 사이의 관계식)으로 표현해본다. 이 점화식을 토대로 소스코드를 작성한다. 다이나믹 프로그래밍을 이용한 소스코드를 작성하는 방법 2가지가 있다.

1) 탑다운

재귀함수를 이용하여 큰 문제를 해결하기 위해 작은 문제를 호출하는 방식

2) 보텀업

반복문을 이용하여 작은 문제를 먼저 해결하고, 해결된 작은 문제를 모아 큰 문제를 해결하는 방식

Q31. 금광

def reshape(arr):
    _array = []
    row = []
    for i in range(n * m):
        if i % m == 0 and i > 0:
            _array.append(row)
            row = []
        row.append(arr[i])
    _array.append(row)
    return _array

t = int(input())
for _ in range(t):
    n, m = map(int, input().split())
    array = reshape(list(map(int, input().split())))
    dp = [[0] * m for _ in range(n)]
    for i in range(n):
        dp[i][0] = array[i][0]
    for j in range(m - 1):
        for i in range(n):
            if i - 1 >= 0 and i + 1 < n:
                dp[i][j + 1] = max(dp[i - 1][j], dp[i][j], dp[i + 1][j]) + array[i][j + 1]
            elif i - 1 >= 0 and i + 1 >= n:
                dp[i][j + 1] = max(dp[i - 1][j], dp[i][j]) + array[i][j + 1]
            else:
                dp[i][j + 1] = max(dp[i][j], dp[i + 1][j]) + array[i][j + 1]

    answer = 0
    for i in range(n):
        answer = max(answer, dp[i][m - 1])
    print(answer)

입력: 테스트 케이스 T, 금광의 크기 N과 M

출력: 테스트 케이스마다 채굴자가 얻을 수 있는 금의 최대 크기

문제 해결 방법: 2차원 배열에 부분 문제의 정답을 저장한다. 즉, 채굴자가 오른쪽 위, 오른쪽, 오른쪽 아래 3가지지 중 하나의 위치로 이동할 때 얻을 수 있는 금의 최대 크기를 저장한다. 단, 이동하면서 주어진 범위의 인덱스를 벗어나지 않도록 구현한다.

점화식: dp[i][j + 1] = max(dp[i - 1][j], dp[i][j], dp[i + 1][j]) + array[i][j + 1]

Q32. 정수 삼각형

n = int(input())
array = []
for _ in range(n):
    array.append(list(map(int, input().split())))
dp = [[0] * n for _ in range(n)]
dp[0][0] = array[0][0]
for i in range(1, n):
    for j in range(n):
        if i < j:
            continue
        if j - 1 >= 0 and j < i:
            dp[i][j] = max(dp[i - 1][j - 1], dp[i - 1][j]) + array[i][j]
        elif j - 1 >= 0 and j == i:
            dp[i][j] = dp[i - 1][j - 1] + array[i][j]
        else:
            dp[i][j] = dp[i - 1][j] + array[i][j]
answer = max(dp[n - 1])
print(answer)

입력: 삼각형의 크기 n, 정수 삼각형

출력: 합이 최대가 되는 경로에 있는 수의 합

문제 해결 방법: 2차원 배열에 부분 문제의 정답을 저장한다. 즉, 모든 위치를 기준으로 ‘왼쪽 위’ 혹은 ‘바로 위’ 위치까지의 최적의 합 중에서 더 큰 합을 가지는 경우를 선택하여 내려온다. 단, 이동하면서 주어진 범위의 인덱스를 벗어나지 않도록 구현한다.

점화식: dp[i][j] = max(dp[i - 1][j - 1], dp[i - 1][j]) + array[i][j]

Q33. 퇴사

n = int(input())
t_arr, p_arr = [0], [0]
d = [0] * (n + 1)
for _ in range(n):
    t, p = map(int, input().split())
    t_arr.append(t)
    p_arr.append(p)
for i in range(n, 0, -1):
    consulting_end_date = i + t_arr[i]
    if consulting_end_date > n + 1:
        d[i] = 0
        continue
    elif consulting_end_date == n + 1:
        d[i] = p_arr[i]
    else:
        d[i] = p_arr[i] + max(d[i + t_arr[i]:])
print(max(d))

입력: 퇴사까지 남은 날 N, N일 동안의 상담 일정

출력: 상담을 통해 얻을 수 있는 최대 이익

문제 해결 방법: 1차원 배열에 부분 문제의 정답을 저장한다. 뒤쪽 날짜부터 거꾸로 확인하는 방식으로 접근한다. 즉, 뒤쪽부터 매 상담에 대하여 ‘현재 상담 일자의 이윤 + 현재 상담을 마친 일자부터의 최대 이윤’을 계산하면 된다.

점화식: d[i] = p_arr[i] + max(d[i + t_arr[i]:])

Q34. 병사 배치하기

n = int(input())
array = list(map(int, input().split()))
dp = [1] * n
for i in range(1, n):
    for j in range(i):
        if array[i] < array[j] and dp[i] < dp[j] + 1:
            dp[i] = dp[j] + 1
print(n - max(dp))

입력: 병사의 수 N, 병사의 전투력

출력: 조건에 맞게 병사가 남아 있도록 하기 위하여 열외시켜야 하는 병사의 수

문제 유형: 가장 긴 증가하는 부분 수열

점화식: 모든 0 ≤ j < i 에 대하여, dp[i] = max(dp[i], dp[j] + 1) if array[i] < array[j]

Q35. 못생긴 수

import heapq
# n번째 못생긴 수를 구하라
n = int(input())
h = [1]
cnt = 0
prev = 0
while True:
    ugly = heapq.heappop(h)
    if prev == ugly:
        continue
    cnt += 1
    heapq.heappush(h, ugly * 2)
    heapq.heappush(h, ugly * 3)
    heapq.heappush(h, ugly * 5)
    prev = ugly
    if cnt == n:
        break
print(ugly)

입력: n

출력: n번째 못생긴 수

문제 해결 방법: 못생긴 수 1을 2, 3, 5를 점진적으로 곱하여 못생긴 수를 만든다. 단, 오름차순으로 못생긴 수를 정렬하며 찾기 위하여 가장 작은 못생신 수를 반환하는 최소 힙 자료구조를 사용한다.

Q36. 편집 거리

str1 = input()
str2 = input()
n, m = len(str1), len(str2)
d = [[0] * m for _ in range(n)]
for i in range(n):
    d[i][0] = i
for j in range(m):
    d[0][j] = j

for i in range(1, n):
    for j in range(1, m):
        if str1[i] == str2[j]:
            d[i][j] = d[i - 1][j - 1]
        else:
            d[i][j] = min(d[i - 1][j], d[i - 1][j - 1], d[i][j - 1]) + 1
print(d[-1][-1])

입력: 두 문자열 A, B

출력: 문자열 A를 편집하여 문자열 B로 만들기 위해 사용한 최소 연산의 수 (최소 편집 거리)

문제 유형: 최소 편집 거리 알고리즘

점화식:

1) 두 문자가 같은 경우

d[i][j] = d[i - 1][j - 1]

2) 두 문자가 다른 경우

d[i][j] = min(d[i - 1][j], d[i - 1][j - 1], d[i][j - 1]) + 1