우선순위큐

우선순위 큐(Priority Queue) 큐(Queue)는 먼저 들어오는 데이터가 먼저 나가는 FIFO(First In First Out) 형식의 자료구조 우선순위 큐는 먼저 들어오는 데이터가 아니라, 우선순위가 높은 데이터가 먼저 나가는 형태의 자료구조 일반적으로 heapq로 구현 파이썬 라이브러리 PriorityQueue 파이썬 우선순위 큐 구현에서 heapq가 PriorityQueue보다 실행시간이 적게 걸려 heapq를 일반적으로 많이 사용 또, PriorityQueue와 heapq는 최소 힙만 다룰 수 있기 때문에 큰 수부터 pop 하고싶을 때는 - 부호를 붙혀 push heappush()와 heappop() 모두 O(logN)의 시간복잡 q = PriorityQueue() q.put((0,k)..

1715번: 카드 정렬하기 정렬된 두 묶음의 숫자 카드가 있다고 하자. 각 묶음의 카드의 수를 A, B라 하면 보통 두 묶음을 합쳐서 하나로 만드는 데에는 A+B 번의 비교를 해야 한다. 이를테면, 20장의 숫자 카드 묶음과 30장 www.acmicpc.net """ 정렬된 두 묶음의 숫자 카드가 있다고 하자. 각 묶음의 카드의 수를 A, B라 하면 보통 두 묶음을 합쳐서 하나로 만드는 데에는 A+B 번의 비교를 해야 한다. 10장, 20장, 40장의 묶음 10+20, 40 => 30, 40 : (10 + 20) + (30 + 40) = 100번의 비교 10+40, 20 => 50, 20 : (10 + 40) + (50 + 20) = 120번의 비교 N개의 숫자 카드 묶음의 각각의 크기가 주어질 때, 최..

다익스트라 음수간선 X S 시작점부터 다른 모든 노드로 가는 최단거리 구하는 알고리즘 기출 : 음수간선이 없는데 시작점이 있고 최단거리 구하는 문제 원리 최단거리를 구할 노드에서 시작하여 거리가 입력된 노드 중 최단거리가 가장 작은 노드를 돌아가며 선택 노드를 돌아가면서, 더 거리가 나오면 값 갱신하여 저장 우선순위 큐 파이썬 우선순위 큐, 힙 우선순위 큐(Priority Queue) 큐(Queue)는 먼저 들어오는 데이터가 먼저 나가는 FIFO(First In First Out) 형식의 자료구조 우선순위 큐는 먼저 들어오는 데이터가 아니라, 우선순위가 높은 데이터가 먼저 나 karla.tistory.com 풀이 (PriorityQueue) import sys from queue import Priori..