우선순위큐
파이썬 heapq 모듈 사용법과 응용
✏️ heapq 최소 힙(min heap) 자료구조를 제공한다. 원소는 항상 정렬되어 추가되고 삭제되며 가장 작은 값이 언제나 인덱스 0에 위치하게 된다. import heapq ✏️ 최소힙의 생성 heapq 모듈을 이용함으로써 일반 리스트를 마치 최소 힙처럼 다룰수 있게 된다. 그냥 빈 리스트를 생성하고 heapq 모듈의 함수를 호출할 때마다 리스트를 인자로 넘겨서 사용하면된다. 즉 heapq모듈을 통해서 원소를 추가하고 삭제하면 그 리스트는 최소힙이 된다. heap=[] ✏️ 최소힙 원소추가 heappush(), 첫번째 인자는 원소를 추가할 대상 리스트, 두번째 인자는 추가할 원소 시간복잡도: O(logN) heapq.heappush(heap, 4) heapq.heappush(heap, 1) heap..
백준 11000: 강의실 배정 해설 - python
✏️ 문제 https://www.acmicpc.net/problem/11000 11000번: 강의실 배정 첫 번째 줄에 N이 주어진다. (1 ≤ N ≤ 200,000) 이후 N개의 줄에 Si, Ti가 주어진다. (0 ≤ Si < Ti ≤ 109) www.acmicpc.net ✏️ 풀이 그리디 알고리즘 공부하겠다고 푼거긴한데 우선순위큐가 핵심인 문제인 것 같다. 회의의 [시작, 끝]을 리스트에 입력받는다. 회의시작시간을 기준으로 정렬시킨다. 첫 회의의 종료시간을 새로운 큐를 만들어 저장시킨다. 그 다음 반복문으로 두번째 회의의 시작시간부터 비교하면서 회의가 가능하면 회의가 진행되었다고 생각하고 새로운 큐를 업데이트해주고 회의가 불가능한 시간이면(회의겹치면) 새로운 큐에 push를 해주어 강의실이 하나 더 ..