코드 # 선수문제, 위상정렬로 하되 큐에 들어가는 값에 우선순위가 있다. # 큐를 이용할 때 우선순위가 생기면 우선순위 큐를 사용한다. # 여기서는 앞에 문제가 뒤에 문제보다 쉽기 때문에 우선순위 큐를 사용해준다. import sys, heapq input = sys.stdin.readline n,m = map(int, input().split()) graph = [[] for _ in range(n+1)] indegree = [0]*(n+1) for _ in range(m): x,y = map(int, input().split()) graph[x].append(y) indegree[y] += 1 def topol_sort(): solve = [] queue = [] for i in range(1, n+..
우선순위 큐
우선순위 큐 우선순위 큐는 데이터를 추가한 순서대로 삭제하는 큐와 달리, 데이터 추가는 어떤 순서로 해도 상관 없지만 데이터를 제거할 때는 가장 작은 값을 제거하는 특성을 가지는 자료구조이다. 이는 내부적으로 정렬 메커니즘이 있다는 것을 의미한다. 우선순위 큐는 내부적으로 힙이라는 완전 이진 트리로 되어있다. 힙 트리의 루트노드에는 데이터들 중에 가장 큰 값 혹은 가장 작은 값을 담게 되는데 전자는 최대힙(Max-heap) 후자는 최소힙 (Min-heap)이라고 한다. 어떤 값을 넣어도 항상 루트에 가장 큰 값 또는 가장 작은 값이 위치하도록 자동으로 갱신한다. 이 과정이 꽤 효율적이라 우선순위 큐의 값 삽입/삭제 시간 복잡도는 O(logN)이다. 무작위 숫자들을 힙에 전부 넣고 하나를 빼면 정렬된 결과..
