DP + 그리디 과제 정리

알고리즘 마지막 주차, DP와 그리디 주차이다.

이전 포스팅과 마찬가지로 개인적으로 어려웠거나 실수했던 문제 위주로 정리한다.

 

동전

 

https://www.acmicpc.net/problem/9084

 

 

DP의 대표 유형인 동전 문제이다.

DP 문제를 풀때는 보통 1차원 혹은 2차원 배열(리스트)로 접근하는데, 이때 dp의 의미를 정의할 수 있는 것이 핵심이라고 생각한다.

 

이 문제에서 dp를 1차원 배열로 만들었고, dp[i]를 "i원을 만들 수 있는 경우의 수"라고 정의했다.

 

동전의 가치가 만약 오름차순으로 정렬되어 있다고 하자.

그럼 새로운 동전을 획득할 때마다, 어떠한 가치를 만들 수 있는 경우의 수는 더 많아질 확률이 있다.

 

예를 들어 1원으로는 1~10원을 만들 수 있는 경우의 수는 1이다.
그러나 여기서 2원짜리 동전이 생기면, 2원을 만들 수 있는 경우는 1가지가 더 발생한다.

 

그럼 2원짜리 동전까지 탐색했을 때 2원을 만드는 경우 dp[2]=2가 될것이다.

그럼 2원짜리 동전까지 탐색했을 때 4원을 만드는 경우는?

 

1111

112

22

 

이렇게 3가지이다.

그럼 이 과정을 조금 더 일반화해서 나타내보자.

 

1원까지 탐색했을 때 dp[4]=1이었다. 

2원이 생기자 dp[4]를 만드는 경우는 2가지 더 생겼다. 이는 위 3가지 경우 중 112, 22에 해당한다(새로운 동전 사용)

잘 보면 11과 2에 각각 2가 붙은 것을 볼 수 있고,

 

이는 "2원 동전을 사용해서 4원을 만드는 방법은 이미 2원을 만든 상태에서 2원을 추가하는 것과 같다." 는 것을 말한다.

물론 그전에 1원으로 만든 경우의 수도 고려를 해줘야한다.

 

 

따라서 동전을 탐색하며 dp를 갱신한다 했을 때

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

 

우리는 이런식의 코드를 생각할 수 있다.

 

여기에 초기값이 잘 동작하도록 dp[0]=1을 설정해주면(0원을 만드는 방법은 항상 1가지이다) 된다.

완성 코드

import sys
input= sys.stdin.readline


T= int(input())

for _ in range(T):
    N= int(input())
    coins=list(map(int,input().split()))
    M= int(input())

    dp=[0] * (M+1)
    dp[0]=1

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

    print(dp[M])

 

 

---

0-1 knapsack 베낭

 

 

https://www.acmicpc.net/problem/12865

 

knapsack이라고 불리는 베낭 문제이다.(0-1 냅색)

 

어떻게 하면 K이내의 무게에서, 최대값을 이끌어 낼 수 있을까? 

결국 물건의 무게와 그 가치가 일정한 규칙을 가지는게 아닌만큼,

 

물건들을 비교해가면서 가치의 최댓값을 갱신해야한다.

 

그러면 dp를 첫 번째부터 i번째 물건까지 고려했을 때, 무게 제한이 j인 배낭에 넣을 수 있는 물건들의 최대 가치라고 잡고 시작한다.

 

import sys
input = sys.stdin.readline

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

items=[]  
for _ in range(N):
    w,v = map(int, input().split())
    items.append((w,v))

for i in range(1, N+1):
    for j in range(1, K+1):
        weight=items[i-1][0]  
        value=items[i-1][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])

 

 

근데 베낭문제를 dp=1차원 배열로 최적화하는 과정에서 의문이 생겼다. 왜 바로 1차원으로 접근하기가 어렵지?

 

 

 

여기서 동전 문제와의 차이가 보이는데,

배낭은 "제한된 자원의 최적 선택", 동전은 "무제한 자원의 조합" 문제 

라고 할 수 있다.

 

 

 

동전 문제는 현재 상태가 이전 동전들의 사용 여부에 의존하지 않기 때문에 1차원으로 선언이 가능하다.

 

• 어떤 동전을 몇 개 썼는지 기억할 필요 없음
• 현재 금액 i만 알면 충분함

 

dp[i] = min(dp[i], dp[i-coin] + 1) # 같은 동전을 또 써도 됨

 

상태 전이에서 이전 단계의 선택을 구분할 필요가 없다는 건 동전의 개수가 무제한이라는 조건과 연관이 있다.

Unbounded Knapsack의 특수한 형태라고 할 수 있다.

 

그래서 동전문제는 정순 순회로 1차원 배열로 나타낼 수 있다.

 

 

그러나 0-1 Knapsack인 베낭 문제는 각 물건을 1개씩 밖에 사용할 수 없고, 따라서 같은 물건을 재사용하지 못하도록

역순 순회를 해야 최적화할 수 있다.

 

import sys
input = sys.stdin.readline

N, K = map(int, input().split())
dp = [0] * (K + 1)

for _ in range(N):
    w, v = map(int, input().split())

    for j in range(K, w-1, -1):
        dp[j] = max(dp[j], dp[j-w] + v)

print(dp[K])

 

최적화의 효과는 대략 두배 정도이다.

 

 

결론

 

- 동전 문제: Unbounded Knapsack → 정순 순회

- 배낭 문제: 0-1 Knapsack → 역순 순회

 

즉 사용 횟수 제약이 DP 구현 방식을 결정한다라고 결론지었다.

그러나 아직 확신이 서지 않아 다시 공부해보려한다..

 

---

외판원 순회

https://www.acmicpc.net/problem/2098

 

 

 

 

이 문제는 외판원 순회2와 거의 같다. 로직도 dfs를 이용한 탐색으로 동일하기 때문에 로직 설명은 생략한다.

다만 N의 범위가 다르고, 이것이 난이도를 골드1까지 올려놓았다.

 

 

1주차에 풀었던 외판원 순회2는 최대 N이 10이었다.

탐색가능한 경로가 최대 10! 이었고 이는 400만 이하였던 것으로 기억한다.

 

그러나 지금은 16!으로 전부 탐색하면 O(N!)으로 시간 제한을 완전히 넘겨버린다.

 

따라서 이를 해결하기 위해 dp를 도입해야 하는데,

이때 필수적으로 비트마스킹도 해야한다.

 

TSP 문제에서 DP + 비트마스킹이 필수인 이유는 뭘까.

 

이 문제에서 "상태"는 (현재 위치, 방문한 도시들)로 나타낼 수 있는데, 

이 경우 시간복잡도: O(N² × 2^N)로 나타낼 수 있다.

따라서 N=16일때 통과가 가능하다

 

dp[cur][visited]

#cur: 현재 위치 (0 ~ N-1) → N가지 
#visited: 방문한 도시들의 비트마스크 (0 ~ 2^N-1) → 2^N가지

 

• 각 (cur, visited) 상태를 딱 한 번만 계산
• 상태 개수: N × 2^N
• 각 상태당 작업량: O(N) 

 

그럼 DP는 그렇다 치고, 왜 비트마스킹을 사용해야 할까?

먼저 방문 여부를 튜플로 저장한다고 해보자.

 

import sys
input = sys.stdin.readline

N = int(input())
matrix = []
for _ in range(N):
    matrix.append(list(map(int, input().split())))

memo = {}

def dfs(cur, visited_tuple):
    # 모든 도시를 방문했다면
    if all(visited_tuple):
        if matrix[cur][0] != 0:
            return matrix[cur][0]
        else:
            return float('inf')
    
    # 이미 계산된 값이 있다면 반환
    state = (cur, visited_tuple)
    if state in memo:
        return memo[state]
    
    # 최소값을 찾기 위해 무한대로 초기화
    min_cost = float('inf')
    
    # 다음 도시들을 탐색
    for next_city in range(N):
        # 현재 도시에서 next_city로 갈 수 없거나, 이미 방문한 도시라면 스킵
        if matrix[cur][next_city] == 0 or visited_tuple[next_city]:
            continue
        
        # 새로운 방문 상태 생성 (tuple이므로 새로 만들어야 함)
        new_visited = list(visited_tuple)
        new_visited[next_city] = True
        new_visited_tuple = tuple(new_visited)
        
        # 다음 도시로 가는 비용 + 그 이후의 최소 비용
        cost = matrix[cur][next_city] + dfs(next_city, new_visited_tuple)
        min_cost = min(min_cost, cost)
    
    memo[state] = min_cost
    return min_cost

# 시작: 0번 도시에서 시작, 0번 도시만 방문한 상태
initial_visited = [False] * N
initial_visited[0] = True
print(dfs(0, tuple(initial_visited)))

 

다음은 방문 여부를 비트마스킹으로 체크하는 방법이다.

import sys
input = sys.stdin.readline

N = int(input())
matrix = []
for _ in range(N):
    matrix.append(list(map(int, input().split())))

dp = [[-1] * (1 << N) for _ in range(N)]

def dfs(cur, visited):
    # 모든 도시를 방문했다면
    if visited == (1 << N) - 1:
        if matrix[cur][0] != 0:
            return matrix[cur][0]
        else:
            return float('inf')
    
    # 이미 계산된 값이 있다면 반환
    if dp[cur][visited] != -1:
        return dp[cur][visited]
    
    # 최소값을 찾기 위해 무한대로 초기화
    dp[cur][visited] = float('inf')
    
    # 다음 도시들을 탐색
    for next_city in range(N):
        # 현재 도시에서 next_city로 갈 수 없거나, 이미 방문한 도시라면 스킵
        if matrix[cur][next_city] == 0 or (visited & (1 << next_city)):
            continue
        
        # 다음 도시로 가는 비용 + 그 이후의 최소 비용
        cost = matrix[cur][next_city] + dfs(next_city, visited | (1 << next_city))
        dp[cur][visited] = min(dp[cur][visited], cost)
    
    return dp[cur][visited]

print(dfs(0, 1))

 

위가 비트마스킹, 아래가 튜플

 

 

• 메모리: Dictionary가 2차원 배열보다 오버헤드 큼
• 속도: 튜플 생성/해시 계산으로 인한 속도 저하

압도적인 성능차이로 인해 TSP문제에서는 비트마스킹이 표준이 되었다.

예상으로는 메모리 차이가 더 클것으로 생각했는데, 시간 차이가 훨씬 많이 나서 놀랐다.

 

 

---

점프

https://www.acmicpc.net/problem/2253

 

 

최소의 점프 횟수를 출력하는 것이 이 문제의 핵심이다.

 

이 문제에도 아까 동전과 유사한, 방향성이 있는 전이라는 개념이 존재한다.

 

• 점프: 앞으로만 이동 가능 (돌 번호 증가)
• 동전: 금액이 증가하는 방향으로만

 

그러나 점프문제에서는 속도라는 개념이 추가로 등장한다.

그것도 속도의 목록이 정해져 있는 것이 아닌 이전 속도 x에 대하여 x-1,x,x+1이라는 제약조건이 달려있다.

 

만약 속도가 [1,3,5] 처럼 정해져있고 그 속도로만 이동할 수 있다면, 이 문제는 동전 문제와 완전히 동일한 문제가 될 것이다.

(특정 속도를 반복해서 사용할 수 있으므로)

 

그러나 제약조건 때문에 우리는 이 문제를 조금 다른 관점으로 바라볼 필요가 있다.

 

 

속도를 이용해 목적지까지 도달하는 "최소 횟수" 라는 키워드를 통해 BFS 풀이법을 떠올릴 수 있다.

 

check= [ [] for _ in range(N+1)]
def bfs():
    q=deque([(1,0,0)])

    while q:
        cur,jump,cnt= q.popleft()

        for x in [jump, jump-1,jump+1]:
            if x>0:
                next=cur+x
                if next==N:
                    return cnt+1
                if next<N and next not in small and x not in check[next]:
                    check[next].append(x)
                    q.append((next,x,cnt+1))

    return -1
print(bfs())

 

 

이번에는 DP로 접근해보자.

 

 

dp[i][j] = i번째 돌에 속도 j로 도달하는 최소 점프 수라고 가정한다면,

점화식은 자연스럽게 이전에 밟은 돌(i-j)에서의 최소를 따져야 한다.

 

속력은 최대 i번에 도달하기까지 (2i**0.5)면 충분하므로 범위를 잘 설정해준다.

import sys
input = sys.stdin.readline
from collections import deque

N,M=map(int,input().split())

small=set()

for _ in range(M):
    small.add(int(input()))

# dp[i][j]=i라는 점에 j의 속도로 도달했을 때의 최소 점프 횟수
dp= [ [float('inf')] * (int((2*N) ** 0.5) +2) for _ in range(N+1)]
dp[1][0]=0

for i in range(2, N+1):
    if i in small:
        continue
    for j in range(1, int((2*i)**0.5)+1):
        dp[i][j]= min(dp[i-j][j-1], dp[i-j][j],dp[i-j][j+1])+1

if min(dp[N])==float('inf'):
    print(-1)
else:
    print(min(dp[N]))

 

위치 i에 속도 j로 도달하려면, 위치 (i-j)에서 속도 (j-1, j, j+1) 중 하나로 와야 한다.

따라서 코드와 같은 점화식을 사용할 수 있다.

 

---

멀티탭 스케줄링

 

https://www.acmicpc.net/problem/1700

 

그리디 문제 중에 도전 과제를 빼고 골드1로 상당히 난이도가 높은 문제지만, 전체적인 흐름 자체는 이해할 만하다.

현재의 상황에 선택한 최적해가 전체의 최적해가 된다는 성질을 이용해야 한다.

 

이 문제가 그리디라는 걸 알아내는 건 그리 어렵지는 않지만

그런데 어떻게 그걸 그리디 문제 풀 때마다 알아내냐거....

 

이게 시작 단계이다.

그림 그리기 쉬운거만 그림 넣기

 

멀티탭의 구멍이 2개이므로 처음에는 이렇게 될 것이다.

 

 

그 다음, 우리는 다음에 오는 2,3을 "사용"하기 위해 멀티탭 플러그를 뽑을 필요가 없다는 것을 알게 된다.

 

 

 

어..... 2번 물건은 다시 사용하는데... 그럼 2번은 아껴뒀다가 다시 쓰면 되잖아

그럼 다시 안 쓰이는 3번을 그냥 빼면 나중에 쓸데없이 2를 뺐다가 꽂는 횟수를 줄일 수 있겠다! 가 핵심 아이디어이다.

만약 3번이 다시 쓰이더라도, 다시 등장하는 2의 뒤 에 등장한다면 마찬가지로 3번을 먼저 빼는게 최소한 손해는 보지않는 

방법이라는 것을 알 수 있다.

 

 

2는 그대로 쓰이고 7만 바꾸면 됨

 

 

따라서 3번과 1번만 빼면 최소 횟수가 보장이 된다.

 

import sys
input = sys.stdin.readline

N, K = map(int, input().split())
seq = list(map(int, input().split()))

multitap = set()
count = 0

for i in range(K):
    # 이미 꽂혀있으면 넘어감
    if seq[i] in multitap:
        continue
    
    # 멀티탭에 자리가 있으면 그냥 꽂음
    if len(multitap) < N:
        multitap.add(seq[i])
        continue
    
    # 멀티탭이 가득 찬 경우: 
    # 가장 나중에 사용되는 기기를 찾아서 뽑음
    latest_use = -1
    remove = -1
    
    for plugged in multitap:
        # 현재 꽂혀있는 기기가 앞으로 언제 사용되는지 찾음
        next_use = K  
        for j in range(i + 1, K):
            if seq[j] == plugged:
                next_use = j
                break
        
        # 가장 나중에 사용되는 기기를 찾음
        if next_use > latest_use:
            latest_use = next_use
            remove = plugged
    
    # 가장 나중에 사용되는 기기를 뽑고 새 기기를 꽂음  
    multitap.remove(remove)
    multitap.add(seq[i])
    count += 1

print(count)

 

현재 멀티탭에 꽂혀있는 물건을 탐색하면서, 아직 꽂히지 않고 순서를 기다리는 물건이 있는지 찾는 구현이 조금 복잡한 문제였다.

 

---

마치며

 

DP와 그리디는 난이도가 매우 높은 문제가 많아서 힘든 한주였다.

내일 시험을 마지막으로 알고리즘은 끝나지만 한 달 고생한만큼 1일 1백준 계속 하면서 감 잃지 않으려고 한다.

 

다음 C도 화이팅...!