heapq

[문제] https://www.acmicpc.net/problem/11000 11000번: 강의실 배정 첫 번째 줄에 N이 주어진다. (1 ≤ N ≤ 200,000) 이후 N개의 줄에 Si, Ti가 주어진다. (0 ≤ Si < Ti ≤ 109) www.acmicpc.net [풀이] 문제의 핵심은 현재 수업의 종료 시간이 다음 수업의 종료 시간보다 늦을 경우 회의실 하나를 더 배정해야 한다. 먼저 수업의 시작과 끝 시간을 queue에 넣고 이를 정렬하면 시작 시간이 가장 빠른 수업이 가장 앞에 오게 되기 때문에 첫 수업의 종료시간을 새로운 큐인 room에 넣는다. 두 번째 수업부터 첫 번째 회의와 비교를 하는데 두 번째 수업의 시작시간 < 첫 수업의 종료시간 일 경우 강의실을 새로 배정해야 하고 그렇지 않..

[문제] https://www.acmicpc.net/problem/11286 11286번: 절댓값 힙 첫째 줄에 연산의 개수 N(1≤N≤100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 0이 아니라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0 www.acmicpc.net [풀이] 이전에 풀었던 7662번 이중 우선순위 큐와 유사하다. 2022.06.24 - [문제풀이/BOJ] - [Python] BOJ/백준 7662번 이중 우선순위 큐 [Python] BOJ/백준 7662번 이중 우선순위 큐 [문제] https://www.acmicpc.net/problem/7662 7662번: 이중 우선순위 큐 입력 데이터는 표준입력을 사용한다. 입..

[문제] https://www.acmicpc.net/problem/7662 7662번: 이중 우선순위 큐 입력 데이터는 표준입력을 사용한다. 입력은 T개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에는 입력 데이터의 수를 나타내는 정수 T가 주어진다. 각 테스트 데이터의 첫째 줄에는 Q에 적 www.acmicpc.net [풀이] 가장 간단한 방법인 max, min 으로 찾는 방법은 시간초과가 나온다 (당연함) 파이썬의 우선순위 큐 문제는 heapq, PriorityQueue 두 가지 라이브러리를 사용할 수 있다. https://stackoverflow.com/questions/36991716/whats-the-difference-between-heapq-and-priorityqueue-in-pytho..

[문제] https://www.acmicpc.net/problem/11279 11279번: 최대 힙 첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 www.acmicpc.net [풀이] 이전 글의 최소 힙과 같이 파이썬의 heapq 모듈을 사용하나, 해당 모듈은 최소 힙 기능만 동작하기 때문에 최대 힙으로 활용하기 위해서는 조금의 조작이 추가로 필요하다. 2021.08.28 - [BOJ] - [Python] BOJ/백준 1927번 최소 힙 [Python] BOJ/백준 1927번 최소 힙 [문제] https://www.acmicpc.net/pr..

[문제] https://www.acmicpc.net/problem/1927 1927번: 최소 힙 첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0 www.acmicpc.net [풀이] 힙(Heap)? 힙은 완전 이진트리로 수의 집합에서 가장 작은 수나 가장 큰 수만을 자주 꺼내올 때 유용한 자료구조이다. 항상 자식은 두개밖에 없으며, leaf의 가장 왼쪽부터 값을 채운다. 힙은 크게 최소힙과 최대 힙 두 가지가 있다. 최소 힙은 가장 작은 값이 루트이고, 최대 힙은 가장 큰 값이 루트이다. 힙은 완전 이진트리이지만 코드를 구현하기 위해서는 ..