💡동적계획법 테크닉

아마 이 포스트가 마지막 동적계획법 정리이지 않을까 싶다. 동적 계획법으로 풀 수 있는 다양한 문제들과, 기법들에 대한 내용을 정리한다.

✔최적화 문제의 실제 답 계산하기

이전 포스트에서 LIS(nlogn)방식에서 실제 답을 찾는 방법을 공부했던 적 있다.
위 포스트에서는 최적화 문제를 풀 때 최적해의 점수만을 계산했었다. 예를 들면 LIS에서 그 길이만 출력하는 방식을 고수한것이 그 예이다. 그러나 최적해의 결과를 직접 계산하려면 또다른 테크닉이 필요하다.

LIS 실제로 출력하기

우선 이전에 만들어 둔 코드 먼저 첨부한다.

def lis_dp(start):
    if dp[start] != -1:
        return dp[start]
    dp[start] = 1
    for i in range(start+1, n):
        if (lst[start] < lst[i]):
            dp[start] =  max(dp[start], lis_dp(i)+1)
    return dp[start]

max_len = 0
for i in range(n):
    max_len = max(max_len, lis_dp(i))
print(max_len)

위 코드에서 dp 리스트는 각각 인덱스까지의 길이를 담고있다. 가장 기본적인 생각은 dp 리스트에 기링 대신 실제 LIS 원소들을 담는 배열을 반환하는 것이다.

이렇게 구현하면 직관적인 코드를 짤 수 있으나, 모든 부분 문제마다 실제 답을 계산하는 과정을 직접 구현해야 하므로 느리다. 또한 메모리를 많이 차지하게 되며, 번거롭기까지 하다.

우리가 재귀를 구현할 때, 부분문제의 가장 첫번째 조각을 어떤 선택지로 채울지 하나하나 시도하며 최적해를 찾는데, 각 부분문제마다 어떤 선택지를 택했을 때 최적해를 얻는지 기록해두고, 별도의 재귀함수를 통해 각 조각에서 한 선택을 되짚어가며 최적해를 생성해낸다.

우선 아래는 이 문제를 해결한 코드이며, 바텀 업 방식이다.

from bisect import bisect_left
n = int(input())
s = list(map(int, input().split()))
c = [-float('INF')]
dp = [0] * (n)

for i in range(n):
    if c[-1] < s[i]:
        c.append(s[i])
        dp[i] = len(c) - 1
    else:
        c[k:=bisect_left(c, s[i])] = s[i]
        dp[i] = k

size, res = len(c) -1, []
for i in range(n-1, -1, -1):
    if dp[i] == size:
        res.append(s[i])
        size -= 1
print(len(c) - 1)
print(*res[::-1])

또한 아래 코드는 재귀함수를 이용한 방법이다.

def lis_tech(start):
    if dp[start] != -1:
        return dp[start]
    
    dp[start] = 1
    best_next = -1

    for next in range(start + 1, n+1):
        if start == -1 or S[start] < S[next]:
            cand = lis_tech(next)+1
            if cand > dp[start]:
                dp[start] = cand
                best_next = next

    choices[start+1] = best_next
    return dp[start]

def reconstruct(start, seq:list):
    if start != -1:
        seq.append(S[start])
    next = choices[start+1]
    
    if next != -1:
        reconstruct(next, seq)

최적화 문제의 답 구하기 과정

1. 재귀 호출의 각 단계에서 최적해를 만들었던 선택을 별도의 배열에 저장해둔다
2. 별도의 (재귀)함수를 이용해 이 선택을 따라가면서 각 선택지를 저장하거나 출력한다.

응용 문제

문제	난이도	풀이
BOJ-17411 가장 긴 증가하는 부분수열 K	P2	바로가기
BOJ-18837 가장 긴 증가하는 부분수열 K	D3	바로가기

✔배낭 문제

배낭문제를 우선 완전탐색으로 구현해보자. 문제는 다음 문제를 기준으로 한다.
[BOJ-12865] - 평범한 배낭

우선 완전탐색으로 구현하려면 전체 $2^n$개의 조합이 나온다.
(각 물건에 대하여 가져가거나 말거나 2개의 선택지가 있으므로)

따라서 부분문제의 정의를 다음과 같이 내릴 수 있다.

pack(item) : 지금까지 고른 물건들의 목록이 item에 주어질 때 남은 용량을 채워 얻을 수 있는 최대 가치의 합

여기서 중요한 것은 마지막으로 고른 물건과, 가방에 남아있는 용량이다. 그러면 위 부분 문제를 아래와같이 수정할 수 있다.

pack(capacity, item) : 가방의 용량이 capacity만큼 남았을 때 item 이후의 물건들을 싸서 얻을 수 있는 최대 가치

• item을 가져가는 경우

  $\text{pack}(\text{capacity} - \text{volume}[item], item + 1) + \text{need}[item]$

• item을 가져가지 않는 경우

  $\text{pack}(\text{capacity}, item + 1)$

pack은 두 선택지 중 더 큰것을 고른다.

코드

n, k = map(int, input().split())
we = []
va = []
dp = [[-1]*101 for _ in range(100001)]

for i in range(n):
    weight, value = map(int, input().split())
    we.append(weight);   va.append(value)


def pack(capacity, item):
    if (item == n):
        return 0

    if dp[capacity][item] != -1:
        return dp[capacity][item]

    dp[capacity][item] = pack(capacity, item+1)

    if capacity >= we[item]:
        dp[capacity][item] = max(dp[capacity][item], \
        	pack(capacity-we[item], item+1) + va[item])
    
    return dp[capacity][item]

print(pack(k, 0))

간단한 코드 설명을 덧붙이면 가장 큰 틀은 위의 점화식을 따라가되, 함수의 동작은 물건을 모두 순회하였는지 여부를 통해 기저사례를 조성하고 있다.

즉, 가방의 용량이 k일때, 0번 item 이후의 item을 모두 순회하여, DP테이블에 저장한다.
DP테이블은 가로 $K_i$번 물건, 세로 $W_i$무게이며, 해당 위치에 저장되는 값은 Value 이다.

답 추적하기

각 부분문제에 따른 선택지가 2개뿐이므로, 선택을 저장하지 않고도 문제를 역추적할 수 있다.
pack(capacity, item)부분문제에서, item을 선택했는지 알고싶다면, pack(capacity, item+1)과 pack(capacity, item)이 같은지 비교하면 된다.

만약 두 값이 같다면 해당 item을 무시하고, 그렇지 않다면 item을 답에 포함시킨다.

### 선언부 생략

### function: pack() 생략
picked = []
def reconstruct(capacity, item):
    global picked
    if item == n:
        return
    if (pack(capacity, item) == pack(capacity, item+1)):
        reconstruct(capacity, item+1)
    else:
        picked.append(item)
        reconstruct(capacity - we[item], item+1)

reconstruct(k, 0)
print(picked)

또다른 배낭 문제

• 각 물건을 최대 하나만 고를 수 있는 0/1 배낭 문제
• 한 물건을 여러개 담을 수 있는 배낭 문제
• 물건을 원하는 분량만 쪼개서 남을 수 있는 분수 배낭 문제

응용 문제

문제	난이도	풀이
BOJ-17411 말아톤	G3	바로가기
BOJ-22115 창영이와 커피	G5	바로가기

✔여행하는 외판원 문제 (TSP)

BOJ-2098 외판원 순회 문제를 기준으로 주제를 정리한다.

외판원 순회 문제는 유명한 NP-난해 문제 중 하나로, 어떤 외판원이 $n$개의 도시의 방문계획을 세울 때 각 도시를 한번만 방문하는 최소 거리를 구하는 문제이다.

구현하는 방법 중 하나로는 완전탐색이 있다. 이로 구현하는 경우 $n$이 15정도만 되더라도 동작하지 않는 문제가 있다.(시간복잡도가 $n!$이므로)

재귀함수 하나를 정의해보자.

• $shortestPath(path) \rightarrow$ 지금까지 만든 경로가 path에 주어질 때, 이 경로를 연장해 나머지 도시들을 방문하는 경로 중 최소의 경로

위 함수의 정의에서는 부분 문제의 수가 많기도 하며, 부분구조가 성립하지 않으므로 메모이제이션 적용이 불가능하다.

따라서 함수의 정의에서 지금까지 한 선택들에 대한 정보를 최소로 받도록 함수의 정의를 고쳐야 한다.
지금까지 만든 부분경로인 $path$가 쓰이는 곳은 두 곳으로, 경로가 완성되었을 때 전체 경로의 길이를 계산하는 부분과, 어떤 도시를 전에 방문한 적 있는지 확인하는 부분이다.

• $shortestPath(here, visited) \rightarrow$ 현재 위치가 $here$이고, 각 도시들을 방문한 적이 있는지의 여부가 불린 값 배열 $visited$에 주어질 때, $here$에서 시작해 나머지 도시를 방문하는 부분 경로의 최소 길이를 반환한다.

MAX = 20
INF = 1e9
n = int(input())
dist = [list(map(int, input().split())) for _ in range(n)]
dp = [[-1]*(1<<MAX)for _ in range(MAX)]

def shortestPath(here, visited):
    if visited == (1 << n) - 1:
        if dist[here][0] != 0:
            return dist[here][0]
        return INF
    
    if dp[here][visited] != -1:
        return dp[here][visited]
    
    dp[here][visited] = INF

    for nxt in range(n):
        if visited & (1 << nxt) or dist[here][nxt] == 0:
            continue
        dp[here][visited] = min(dp[here][visited], 
                                shortestPath(nxt, visited | (1 << nxt)) + dist[here][nxt])

    return dp[here][visited]

print(shortestPath(0, 1))

다만 여기서 추가로 고려해준것은 갈 수 없는 노드가 포함되어있으므로 해당 부분을 예외처리해준것이다.

추가로 방문한 노드를 비트필드를 사용하여 관리해주면서, 시간복잡도상의 이득을 받아왔다.