우선순위 큐

문제https://www.acmicpc.net/problem/1766백준 문제집 - 0x1A강 - 위상 정렬 알고리즘: 우선순위 큐, 방향 비순환 그래프, 위상 정렬풀이A B => "B를 풀기 전 A를 먼저 푸는것이 좋음"하지만 문제 조건에 "가능하면 쉬운 문제부터" 푸는것이 좋다고 명시되어있기 때문에,우선순위가 같은 문제들은 작은 번호부터 풀어나가야 한다.예를들어 우선순위가 1 → 2, 1 → 4와 같이 되어있다고 가정해보자.기존의 위상 정렬은 결과가 1, 2, 4가 되든, 1, 4, 2가 되든 상관없었지만,이 문제에선 "쉬운 문제"부터 풀어야 하므로 1, 2, 4가 답이 된다. 첫 시도는 DFS로 N번 문제부터 풀어나가는 방식이었다.큰 번호 → 작은 번호 순으로 진행되므로 자연스럽게 어려운 문제 → ..

문제https://www.acmicpc.net/problem/1781백준 문제집 - 0x17강 - 우선순위 큐 알고리즘: 그리디, 정렬, 우선순위 큐풀이 각 문제를 데드라인까지 풀어야 하며, 문제를 푸는 단위시간은 1.최대한 많은 컵라면을 받아야 한다.단순하게 컵라면 갯수를 기준으로 정렬했다가 실패했던 문제다.도움이 됐던 반례는 아래와 같다.1️⃣ https://www.acmicpc.net/board/view/1528282️⃣ https://www.acmicpc.net/board/view/123972 🗝️ 해결 방법은 데드라인 기준으로 정렬 후, 힙의 크기와 데드라인을 비교해가며 pop을 실행하는것이다.먼저 데이터를 (데드라인, 컵라면 갯수) 형태로 저장 후 오름차순으로 정렬한다.정렬한 리스트를 순회하..

문제https://www.acmicpc.net/problem/1655백준 문제집 - 0x17강 - 우선순위 큐 알고리즘: 우선순위 큐풀이 현재까지 주어진 수가 홀수개라면 중간값을, 짝수개라면 중간값 중 더 작은값을 출력해야한다. 이 문제는 두 개의 힙(left, right)으로 해결할 수 있다.left에는 중간값보다 작거나 같은, right에는 중간값보다 큰 수들이 들어가게끔 구성한다.즉 left는 최대 힙으로, right는 최소 힙으로 구현한다. 그리고 새로운 수 x가 주어질때마다 left와 right의 길이를 비교한다.- 두 힙의 길이가 같다면 left에 -x를 삽입 (주어진 수가 짝수개라면 더 작은값을 출력해야하므로)- 길이가 다르다면 right에 x를 삽입 힙에 삽입 후 left의 첫번째 원소값,..

문제https://www.acmicpc.net/problem/13975백준 문제집 - 0x17강 - 우선순위 큐 알고리즘: 그리디, 우선순위 큐풀이 최소 힙을 사용하는 문제다.사실 이러나 저러나 최종 파일 크기는 같을수밖에 없다.(어쨌든 N개의 파일을 모두 더해주는것이기 때문) 하지만 비용 == 두 파일을 합친 크기 이므로, 결국 매 턴마다 가장 작은 파일 두개를 뽑아 합치는것이 최소 비용인 셈이다. 전체 코드# 메모리: 138080KB / 시간: 7644msfrom sys import stdinfrom heapq import heappush, heappopinput = stdin.readlineT = int(input())for _ in range(T): K = int(input()) fil..

문제https://www.acmicpc.net/problem/7662백준 문제집 - 0x16강 - 이진 검색 트리 알고리즘: 우선순위 큐풀이 단순하게 최대힙, 최소힙으로만 관리했다가 틀렸던 문제다.최대힙에서 추출했던 숫자가 최소힙에서는 아직 존재할수도 있으므로, 각 숫자의 상태(갯수)를 따로 저장해둬야한다. 입력이 I로 주어질경우 해당 숫자의 갯수를 +1 카운트.D일경우 명령어에 맞춰 최대/최소힙에서 숫자를 추출.만약 추출한 숫자의 갯수가 0인 상태라면 이미 전체 힙에서 제거된 상태이므로, 갯수가 0이 아닌 숫자를 찾을때까지 계속 추출한다.찾으면 1 감소시킨 후 해당 숫자를 출력하면 된다. 모든 과정이 끝나고나서 힙의 길이가 0이라면 "EMPTY"를, 남아있다면 최댓값, 최솟값을 추출한다.이때는 숫자의 ..

문제https://www.acmicpc.net/problem/2461백준 문제집 - 0x14강 - 투 포인터 알고리즘: 투 포인터, 우선순위 큐, 정렬풀이투포인터만 사용하면 시간초과가 나는 문제다.Python3로 통과하기 위해선 우선순위 큐, 힙heapq을 사용해야한다. 우선 각 반의 능력치를 모두 오름차순 정렬한다.그리고 힙 리스트 heap에 각 반의 최솟값들을 (값, 반, 인덱스) 형태로 삽입한다.이 중 가장 큰 값은 따로 저장해둬야 한다.heap에서 최솟값을 꺼냄 => (값, 반, 인덱스)기존 결과값과 (최댓값 - 최솟값) 중 더 작은 값을 새로운 결과값으로 업데이트.인덱스를 1 증가시킴.해당 반에서 몇번째 값을 가리키는지 나타내는 포인터 역할즉, 현재까지의 가장 최솟값의 포인터를 뜻함.+1 처리 ..