1. 택배

트럭으로 옮길 수 있는 택배의 용량, 시작 마을, 끝 마을, 각 마을에 있는 택배의 양이 주어졌을 때 옮길 수 있는 가장 많은 택배의 양을 구하는 문제다.

핵심은 택배 스케줄을 끝나는 마을부터 정렬하는 것이다.

네 가지의 택배 경로가 있다고 가정해보자.

2->3, 3->4, 1->5

세 택배 경로에서 옮겨야하는 택배량이 동일하다고 할 때, 시작 마을부터 정렬하면 1->5의 경로를 먼저 고려하게 되고 1->5를 계산에 넣으면 더 최적해가 될 수도 있는 2->3, 3->4는 생각하지 못하게 된다. 과제 같은 그리디 알고리즘 문제에서도 항상 데드라인을 먼저 생각했다. 이게 어떤 원리이고 왜 도착점을 기준으로 정렬하는 것이 시작점을 기준으로 정렬하는 것과 다르게 예외가 생기지 않는지는 곰곰히 생각하며 본인이 깨달을 수밖에 없겠다.

각 마을에 있는 택배는 한꺼번에 옮기지 않아도 된다. 트럭이 수용할 수 있을만큼 최대한 담는 것이 중요하다. 그래서 각 마을에 들릴 때마다 트럭이 수용할 수 있는 무게를 can list에 설정했다. 초기값은 모두 c이다.

도착점을 기준으로 택배 스케줄을 정렬한 뒤, 옮길 수 있는 최대의 택배를 모두 옮긴다. 옮겨야하는 택배량이 있는 b와 옮길 수 있는 택배량이 있는 can중 작은 값이 해당 스케줄에서 트럭이 옮길 수 있는 택배량이고, 그 값을 ans에 더해준 후 can list에서 빼면 된다. 모든 스케줄에 대하여 과정을 반복하면 최적해가 나오게 된다.

import sys;input=sys.stdin.readline
n,c = map(int,input().split())
schedule = []
can = [c for _ in range(n+1)]
for _ in range(int(input())):
    schedule.append(list(map(int,input().split())))
schedule.sort(key=lambda x : x[1])
ans = 0
for s,e,b in schedule:
    min_vil = min(can[s:e])
    min_vil = min(min_vil,b)
    for i in range(s,e):
        can[i] -= min_vil
    ans += min_vil
print(ans)

뭔가 dp같기도 하고.. 그리디 알고리즘은 맞는 것 같은데 어떻게 풀어야할지 모르겠고.. 그동안 풀었던 수많은 그리디 알고리즘 문제들(강의실, 컵라면, 과제 등등..)이 머릿속을 스쳐가는데 그 문제들이랑은 또 미묘하게 다른 것 같고.. 머리를 아프게 했던 문제다. 결국 검색해서 품ㅋ

2. 친구 네트워크

친구 관계가 들어올 때마다 그 두 친구와 연결된 모든 친구의 수는 얼마인지 묻는 문제다!

분리 집합 문제다. union-find 알고리즘을 사용해야한다는 얘기.

근데 분리 집합 문제를 풀 때마다 느끼는건데.. 알고리즘이 specific해서 그렇지(알고리즘을 알아야만 주어진 시간 안에 문제를 풀 수 있어서 그렇지) 난이도 자체는 어렵지 않은데 랭크가 항상 위에 찍히는 것 같다.

아무튼. python의 dict 자료구조를 사용해서 ID와 숫자를 연결해준다. 그 뒤 find, union 함수를 각각 구성하면 끝. union에서는 두 노드를 연결시킬 때 두 노드의 부모가 다르면 부모 노드가 되는 노드의 연결집합 수를 return하도록 했다. network list에 그 수를 저장해놓았다. union(x,y)에서 만약 x,y가 원래 분리된 집합이었다면 두 노드 parent의 연결집합수를 합한 뒤 return하고, 원래 연결된 집합이었다면 그냥 return network[x]를 해준다.

import sys;input=sys.stdin.readline
def find(x):
    p = parent[x]
    while parent[p]!=p:
        p = parent[p]
    parent[x] = p
    return p
def union(x,y):
    x,y = find(x),find(y)
    if x<y:
        parent[y] = x
        network[x] += network[y]
        return network[x]
    elif x>y:
        parent[x] = y
        network[y] += network[x]
        return network[y]
    else:
        return network[x]
for _ in range(int(input())):
    f = int(input())
    ID = {}
    parent = [i for i in range(2*f+1)]
    network = [1 for _ in range(2*f+1)]
    i = 0
    for _ in range(f):
        a,b = input().split()
        if a not in ID:
            ID[a] = i
            i += 1
        if b not in ID:
            ID[b] = i
            i += 1
        print(union(ID[a],ID[b]))

그럭저럭 풀만했던 문제. find() 함수를 p,x 헷갈리게 짜서 시간낭비한 문제다 ㄱ-

3. 트리의 독립집합

트리에서 다이나믹 프로그래밍이다!

우수 마을과 비슷한 문제인데, 이웃하지 않는 노드들만 모았을 때 트리의 독립집합의 크기를 최대화하는 노드들의 집단을 구하는 문제다. 그러나 이번엔 그 독립집합에 속하는 원소들을 직접 구해야한다는 조건이 추가됐다.

트리에서의 다이나믹 프로그래밍은 DFS를 쓰는 경우가 대부분인 것 같다. DFS를 이용하여 leaf까지 향한 다음 leaf부터 dp list를 채워간다. dp[i][0]은 i번 노드가 독립 집합에 포함되지 않았을 때 독립집합 크기의 최대, dp[i][1]은 i번 노드가 독립 집합에 포함되었을 때 크기의 최대라고 설정한다.

v번 노드를 탐색할 때마다 v와 인접한 노드들의 최적을 살핀다.

dp[v][0]은 v번이 독립집합에 포함되지 않는 경우므로 인접한 노드들은 독립집합에 포함될수도, 그렇지 않을 수도 있다. 둘 중 크기를 더 크게 하는 경우를 더한다.

dp[v][1]은 v번이 독립집합에 포함되는 경우이므로 인접한 노드들은 독립집합에 포함돼선 안된다. 인접한 노드들을 nei라고 할 때, dp[nei][0]을 더해준다.

dp[i][2], dp[i][3]은 독립 집합 표현을 위한 list로 정의했다. 각각 i가 독립집합에 포함되지 않았을 때, 포함되었을 때 최적의 독립집합을 나타낸 list다.

dp[v][3]는 본인 v부터 시작해 dp[nei][2]의 모든 원소를 더하는 것부터 시작한다. v가 독립집합에 포함되었으므로 nei가 독립집합에 포함되면 안된다. 포함되지 않았을 때 최적의 독립집합을 dp[v][3]에 더해주는거다.

dp[v][2]는 nei가 포함되었을 때/포함되지 않았을 때 중 답을 더 크게하는 것을 먼저 고른 뒤에 dp[nei][2] dp[nei][3]중 선택한다.

import sys;input=sys.stdin.readline
n = int(input())
tree = [[] for _ in range(n+1)]
w = [0]+list(map(int,input().split()))
for _ in range(n-1):
    a,b = map(int,input().split())
    tree[a].append(b)
    tree[b].append(a)

# dp[i][0] : i번이 독립집합에 포함되지 않았을 때 최대
# dp[i][1] : i번이 독립집합에 포함되었을 때 최대
# dp[i][2] : i번이 독립집합에 포함 안되었을 때 nodes
# dp[i][3] : i번이 독립집합에 포함되었을 때 nodes
visited = [False for _ in range(n+1)]
dp = [[0,w[i],[],[]] for i in range(n+1)]
def search(v):
    visited[v] = True
    dp[v][3].append(v)
    for nei in tree[v]:
        if not visited[nei]:
            search(nei)
            # v가 독립집합이면 nei는 독립집합에 포함되어선 안돼!
            dp[v][1] += dp[nei][0]
            for i in dp[nei][2]:
                dp[v][3].append(i)
            # v가 독립집합이 아니면 더 최적의 nei를 뽑을거다.
            if dp[nei][1]>dp[nei][0]:
                dp[v][0] += dp[nei][1]
                for i in dp[nei][3]:
                    dp[v][2].append(i)
            else:
                dp[v][0] += dp[nei][0]
                for i in dp[nei][2]:
                    dp[v][2].append(i)

search(1)
if dp[1][0]>dp[1][1]:
    print(dp[1][0])
    dp[1][2].sort()
    print(*dp[1][2])
else:
    print(dp[1][1])
    dp[1][3].sort()
    print(*dp[1][3])

주석에 설명을 따로 달아놨다.