넌 과감해질 필요가 있어

출처: 이것이 취업을 위한 코딩테스트다 with 파이썬, 나동빈, 2021

강의: https://youtu.be/5Lu34WIx2Us?si=OJpwTfcdclJ1HMaq

다이나믹 프로그래밍 Dynamic Programming

요약

다이나믹 프로그래밍(DP)은 동적 계획법이라고도 부른다.

메모리를 사용하여, 처리 시간을 단축하는 방법이다. 이를 메모이제이션(Memoization)이라고 한다.

조건

1. 최적 부분 구조 (Optimal Substructure)
   - 큰 문제를 작은 문제로 나눌 수 있다. 작은 문제의 답을 모아서 큰 문제를 해결할 수 있다.
2. 중복되는 부분 문제 (Overlapping Subproblem)
   - 동일한 작은 문제를 반복적으로 사용하여 해결해야 한다.

접근 방식

• 하향식(Top-Down): 큰 문제로 시작하여, 풀리지 않는 작은 문제를 만나면 재귀적으로 해결.
• 상향식(Bottom-Up ): 작은 문제를 모아서 큰 문제를 해결하는 방식.

Top-Down 접근 방식을 메모이제이션(Memoization)이라고도 부른다.

계산 결과를 메모리에 저장하여 중복 계산을 방지한다.

주로 재귀 함수를 반복적으로 호출하여 문제를 해결한다.

Bottom-Up 접근 방식은 타뷸레이션(Tabulation)이라고 한다.

테이블에 기록한다는 느낌.

주로 반복문으로 구현한다.

따라서 재귀 호출에 따른 오버헤드 혹은 스택 오버플로우 위험이 없다.

기본적으로 Bottom-Up으로 접근하는 것이 더 직관적이다.

일단 그렇게 하고, 막히면 Top-Down으로 풀이하자.

DP인지 어떻게 판단?

가장 중요한 문제이다.

1. 주어진 입력값의 범위가 너무 크면 의심해본다.
2. 완탐, 그리디로 풀리지 않으면 의심해본다.
3. 상술된 조건을 이용한다. (quick sort가 왜 DP가 아닌지 떠올리면 더 좋다. 최적 부분 구조는 맞지만, 중복되는 부분 문제는 없다.)

피보나치 수열을 DP로 구현

피보나치 수열이 뭔지는 생략하지 않지 않지 않겠다.

1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...

An = An-1 + An-2의 규칙을 반복하는 수열이다.

그림과 같은 방식으로 풀이하면, 중복 계산이 발생하여 지수 시간복잡도를 갖는다.

그래서 DP로 풀이하기 딱 좋은 유형이다.

f(6)을 구하기 위해, 작은 문제로 나눌 수 있다. 작은 문제를 합치면 f(6)을 구할 수 있다. (최적 부분 구조)

f(2)와 같이 작은 문제가 중복 계산되고 있다. (중복되는 부분 문제)

햐향식 Top-Down 접근

dp = [0] * 100 # 계산된 결과를 메모이제이션 하기 위한 리스트

def fibo(x):
    if x == 1 or x == 2:
        return 1
        
    if dp[x] != 0: # 이미 계산된 결과는 즉시 return. 중복 계산 방지. 상수 시간 소요.
        return dp[x]

    dp[x] = fibo(x - 1) + fibo(x - 2) # 새로운 문제는 재귀적으로 구함.
    return dp[x]

print(fibo(10)) # 55

상향식 Bottom-Up 접근

# 엥 이것도 메모이제이션 아니에요? 
# 동의하는 부분.. 다만 탑다운에서 이미 계산된 결과는 즉시 반환하는 등 명시적으로 다루고 있어서 구분 짓나 보다.
dp = [0] * 100

d[1] = 1
d[2] = 1

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

print(dp[10]) # 55

예제 1. 개미 전사

# DP인지 판단
# 최적 부분 구조가 가능한가?
    # 특정 구간의 최대 조합이 있을 것이다. 그것은 구간을 확장해도 조합이 바뀌지 않을 것이다.
# 중복되는 부분 문제가 있는가?
    # 특정 구간의 조합이 다음 구간에 영향을 주므로 (1칸 이상 떨어져야 함) 중복되는 문제가 있다고 보아야 한다.

# 메모이제이션 - 탑 다운으로 풀이해보자
# 배열의 크기가 1일 때는? a1
# 2일 때는? max(S1, a2)
# 3일 때는? max(S2, S1 + a3)
# 4일 때는? max(S3, S2 + a4)
# 5일 때는? max(S4, S3 + a5)
# 6일 때는? max(S5, S4 + a6)
# n일 때는? max(Sn-1, Sn-2 + an)
# S1 = arr[0]
# S2 = max(arr[1], arr[0])
# Sn = max(Sn-1, Sn-2 + an)

n = int(input())
arr = list(map(int, input().split()))
dp = [0] * 10
dp[0] = arr[0]
dp[1] = max(arr[0], arr[1])

def get_food(n):

    if dp[n] != 0:
        return dp[n]
    
    dp[n] = max(dp[n - 1], dp[n - 2] + arr[n])

    return dp[n]

print(get_food(n - 1))
print(dp)

예제 2. 1로 만들기

# 최적 부분 구조
    # 맞다. 특정 수를 만드는 최소 연산 회수는 정해져 있다.
# 중복되는 부분 문제
    # 맞다. 특정 수까지의 최소 연산 회수가 정해져 있으므로, 계산 과정에서 반복적으로 사용한다.

# 조건
# 5로 나눈다.
# 3으로 나눈다.
# 2로 나눈다.
# 1로 뺸다.

# 풀이
# 항상 큰 수로 나누는 것이 유리한가?
# 그렇지만, 순서의 차이는 있다. 16의 경우 16 -> 15 -> 3 -> 1 (3번) / 16 -> 8 -> 4 -> 2 -> 1 (4번)). 그리디처럼 풀이하는 것은 아니다.
# 반대로 1부터 dp 테이블 해당 인덱스를 구하기 위한 최소 연산 회수로 채워가는 것은 어떤가?
# [0, 1, 2, 3, 4, 5, 6, 7, ...]
# [0, 0, 1, 1, 2, 1, 2, 3, ...]

# 7을 살펴보자. 다음과 같은 방법으로 만들 수 있다.
# 6 + 1
# 6을 살펴보자.
# 5 + 1, 3 * 2, 2 * 3
# 10을 살펴보자.
# 9 + 1, 5 * 2, 2 * 5
# Sn = min(Sn-1 + 1, Sn//5 + 1, Sn//3 + 1, Sn//2 + 1)이다.
# if n이 어떤 수로 나누어 떨어지느냐에 따라 if 조건문으로 나누면 풀이할 수 있을 것이다.

# n = 1 return 1
# n = 2 return 1
# n = 3 return 1
# n = 5 return 1

# if n % 5 == 0
    # min(Sn-1 + 1, Sn//5 + 1)
# elif n % 3 == 0
    # min(Sn-1 + 1, Sn//3 + 1)
# elif n % 2 == 0
    # min(Sn-1 + 1, Sn//2 + 1)
# else
    # Sn-1 + 1

n = int(input())

dp = [0] * 30001
dp[0] = 0
dp[1] = 0
dp[2] = 1
dp[3] = 1
dp[5] = 1

for i in range(4, n + 1):
    dp[i] = dp[i-1] + 1
    if i % 5 == 0:
        dp[i] = min(dp[i], dp[i//5] + 1)
    if i % 3 == 0:
        dp[i] = min(dp[i], dp[i//3] + 1)
    if i % 2 == 0:
        dp[i] = min(dp[i], dp[i//2] + 1)

print(dp[n])

예제 3. 효율적인 화폐 구성

# 최적 부분 구조
    # 맞다. 특정 값을 구성하기 위한 최소 화폐 개수는 정해져 있다.
# 중복되는 부분 문제
    # 해당 구조가 여러 번 반복된다.


# 풀이
# 무조건 고액 화폐를 많이 사용하는 것이 옳은가?
# 그렇지 않다. 700을 고려해보자. 300 + 300 + ...? / 300 + 200 + 200
# 1로 만들기 문제처럼, 100부터 목표 값까지 최소 화폐 개수를 채워나가보자.
# coins = [200, 300]
# [100, 200, 300, 400, 500, 600, 700, 800, 900, 1000]
# [  0,   1,   1,   2,   2,   2,   3,   3,   3,    4]
# 쉬운 듯?
# min(Sn-300 + 1, Sn-200 + 1)

# if 조건문으로 모든 케이스를 검증하며 풀이해보자. 아니다. 조건문조차 필요가 없다.
# dp = [0] * 10001

# for coin in coins:
# dp[coin] = 1

# for i in range(min(coins), m + 1)
    # for coin in coins:
        # if i > coin:
            # dp[i] = min(dp[i], dp[i - coin] + 1)

# -1 if dp[m] == 1 else dp[m]


n, m = map(int, input().split())
coins = [int(input()) for _ in range(n)]

dp = [10001] * (m + 1)
dp[0] = 0

for i in range(n): # 화폐 단위
    for j in range(coins[i], m+1): # 목표 금액
        if dp[j - coins[i]] != 10001:
            dp[j] = min(dp[j], dp[j-coins[i]] + 1)

if dp[m] == 10001:
    print(-1)
else:
    print(dp[m])

예제 4. 금광

# 최적 부분 구조
    # 맞다. 전체의 문제를 한 열씩 나눠서 판단할 수 있다. 
    # 특정 구간 최적 경로는 전체 구간에서 봐도 그렇다.
# 중복되는 부분 문제
    # 하나의 최적 경로를 구하는 문제이므로, 같은 구간이 중복되어 계산된다.

# 풀이
# 무작정 3방향 중 최대값을 선택하면 되는가?
# 안 된다. 그건 그리디이다. 이동 범위 밖에 있는 최적 경로가 존재할 수 있다.

# 전체 행에서 최대값을 선택하는 것도 불가능하다. 이동이 불가능할 수도 있으므로.

# 2차원 배열을 탐색하며 이전 3방향의 최대값을 더해주는 방식으로 배열을 갱신해야겠다.
# 현재 인덱스의 값은, 이전 3방향 값 중 최대값을 더한 값이다.
# 즉, 다음과 같다.
# dp[i][j] = dp[i - 1][j] +  matrix[i][j-1]
# if i > 0:
# dp[i][j] = max(dp[i][j], dp[i-1][j-1] + matrix[i][j])
# if i + 1 < n 
# dp[i][j] = max(dp[i][j], dp[i+1][j-1] + matrix[i][j])


tc = int(input())

for k in range(tc):
    n, m = map(int, input().split())
    arr = list(map(int, input().split()))

    matrix = []
    for i in range(0, len(arr), m):
        matrix.append(arr[i : i + m])

    dp = [[0] * m for _ in range(n)]
    for i in range(n):
        dp[i][0] = matrix[i][0]

    for j in range(1, m):
        for i in range(n):
            if i == 0:
                left_up = 0
            else:
                left_up = dp[i - 1][j - 1]
            
            if i == n - 1:
                left_down = 0
            else:
                left_down = dp[i + 1][j - 1]
            
            left = dp[i][j - 1]
            dp[i][j] = matrix[i][j] + max(left_up, left, left_down) # 2차원 탐색 문제는 이렇게

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

예제 5. 병사 배치하기

# 최적 부분 구조
    # 나눠서 풀 수 있는가?
    # 연속되는 구간 별로 나눠서 특정 병사를 제외했을 때, 그것이 최선이 되는가?
    # 직관적으로 생각나지는 않지만, 딱히 반례가 떠오르는 것도 아니다.

# 중복되는 부분 문제
    # 하나의 최적 배열을 구하는 것이므로, 부분 문제가 중복된다고 할 수 있다.

# 풀이
# 최장 연속 부분 수열? 그런 유형인 듯하다.
# 내림차순이 성립하지 않는 모든 수만 제거하면 되는가? 그럼 문제가 발생한다.
# [15 11 2 10 9] 이런 배열이 있다면 내림차순이 성립함에도 불구하고, 2를 제거하는 것이 옳다.
# [9 8 7 6 5 4 3 2 10 5 9 8 7] 이런 경우에는 4 3 2 5를 제거해야 한다.


n = int(input())
arr = list(map(int, input().split()))
arr.reverse()

dp = [1] * n

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

print(n - max(dp))

위 문제는 가장 긴 연속하는 부분 수열(Longest Increasing Subsequence, LIS) 유형이다.

LIS의 점화식은 다음과 같다.

# D[i] = array[i]를 마지막 원소로 포함하는, 부분 수열의 최대 길이
모든 0 ≤ j < i에 대하여, D[i] = max(D[i], D[j] + 1) if array[j] < array[i]

모든 i에 대하여 0 ~ i 범위를 탐색하면서 비교하므로 시간복잡도는 O(N^2)이다.