Priority QueueFIFO(First In First Out) 형식우선순위가 높은 데이터가 먼저 출력되는 형식Heap최대, 최소를 빠르게 찾기 위한 자료구조배열에서는 $O(n)$이 걸린다면, 힙을 사용하면 $O(logn)$완전이진트리최대힙, 최소힙 두 종류데이터 삽입, 삭제 원리(최소힙) 데이터 삽입 시, 가장 아래에 데이터 저장 후 부모 노드와 비교해가면서 작은 값이 부모 노드에 갈 수 있도록 위치 교환(최소힙) 데이터 삭제 시, 루트 노드를 삭제하고 가장 아래 데이터를 루트 노드로 옮기고, 왼쪽과 오른쪽의 크기와 비교해 더 작은 쪽과 위치 교환import heapqhq = []heapq.heappush(hq, 1)heapq.heappush(hq, 5)heapq.heappush(hq, 3)hq[..

🔗 Problem Linkhttps://www.acmicpc.net/problem/1655❔ThinkingN개의 수가 차례대로 주어질 때, 현재까지 숫자들의 중앙값을 출력한다.각 숫자는 -10,000이상 10,000이하의 정수이다.💻Solutionimport sysimport heapqinput = sys.stdin.readlinemax_heap = []min_heap = []N = int(input().rstrip())for _ in range(N): num = int(input().rstrip()) heapq.heappush(max_heap, -num) if max_heap and min_heap and (-max_heap[0] > min_heap[0]): heapq...

🔗 Problem Linkhttps://www.acmicpc.net/problem/1202❔Thinking보석의 무게와 가격이 주어질 때, 가방에 보석 하나씩만을 담아 최대 가격을 반환한다.💻Solutionimport heapqimport sysinput = sys.stdin.readlineN, K = map(int, input().split())jewels = []bags = []for _ in range(N): weight, value = map(int, input().split()) jewels.append((weight, value))for _ in range(K): bags.append(int(input()))jewels.sort() bags.sort()max_heap = [..

🔗 Problem Link 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr❔Thinkingenemy에 담긴 적들을 라운드마다 차례대로 제거할때, 가장 많은 라운드 버틸 방법을 생각한다.'무적권'은 k개 만큼 쓸 수 있고, 쓰는 라운드에 따라 결과가 달라질 수 있다.n=10, k=1일 경우, [10,3,7]을 1라운드만에 끝나거나 3라운드 모두를 버틸 수 있다.💻Solutionimport heapqdef solution(n: int, k: int, enemy: list) -> int: max_heap = [] # 지금까지 만난 적을 저장할 최대 힙 for round_num, e in enu..

다익스트라 알고리즘 한 지점에서, 다른 모든 지점까지의 최단 경로를 찾는 알고리즘 GPS, 라우팅 프로토콜 등에서 사용된다. A -> C 거리가 A -> B -> C 거리보다 짧다면 A에서 C까지의 최단 경로를 수정하는 방식이다. heapq를 활용한 구현 1~2 : 모든 정점까지의 거리를 INF로 초기화 하고, 출발점(start) 자기 자신까지의 거리는 0으로 초기화한다. 3 : 거쳐가는 거리보다 바로 가는 거리가 짧다면 업데이트 하지 않는다. 4 : 거쳐가는 거리가 더 짧은 경우, 거리를 업데이트 한다. queue에 (거리, 도착 정점) 순으로 넣어야 거리가 짧은 정점부터 확인할 수 있다. def dijkstra(start): distance = [int(1e9)] * (N+1) # 1 distance..

🔗 Problem Link 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr ❔Thinking 대기열에 등록된 시간과 작업 시간이 주어질 때, 작업에 요청부터 종료까지 걸리는 평균 시간의 최소값을 반환한다. 작업에 요청부터 종료까지 걸리는 시간은 '대기시간' 및 '작업 시간'을 포함한 시간이다. 💻Solution import heapq def solution(jobs): n = len(jobs) total_task_time = 0 current_time = 0 q = [] jobs = sorted(jobs, key=lambda x: (x[0], x[1])) ..