우선순위 큐

1374번: 강의실 첫째 줄에 강의의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 줄마다 세 개의 정수가 주어지는데, 순서대로 강의 번호, 강의 시작 시간, 강의 종료 시간을 의미한다. 강의 www.acmicpc.net 1379번: 강의실 2 첫째 줄에 강의의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 줄마다 세 개의 정수가 주어지는데, 순서대로 강의 번호, 강의 시작 시간, 강의 종료 시간을 의미한다. 강의 www.acmicpc.net 풀이 과정 - 강의실 1. 강의실을 최소로 배정하는 개수를 구해야 한다. 2. heap에서 시작시간, 끝나는 시간, 강의실 번호를 heap push를 한다. 3. 첫 번째로 시작시간이 가..

23843번: 콘센트 광재는 전자기기 대여사업을 시작했다. 퇴근하기 전에 다음날 손님들에게 빌려줄 N개의 전자기기를 충전하려 한다. 사용 가능한 콘센트는 M개가 있고, 성능은 모두 동일하다. 전자기기들은 한 www.acmicpc.net 풀이 과정 1. 입력받은 충전 시간 배열을 내림차순 정렬을 시킨다. 2. 콘센트 배열을 생성시킨다. 3. 내림차순 정렬된 충전 시간을 콘센트 배열에 삽입한다. 3-1 ) 만약 콘센트 배열의 크기가 주어진 콘센트 개수(m) 보다 작을 경우 -> 콘센트 배열에 해당 time을 삽입 3-2 ) 만약 콘센트 배열의 크기가 주어진 콘센트 개수(m) 이상일 경우 -> 가장 작은 값 + 현재 time을 더해서 다시 삽입 4. 콘센트 배열에 있는 값 중 가장 큰 값을 출력한다. -> 가..

코딩테스트 연습 - 프린터 일반적인 프린터는 인쇄 요청이 들어온 순서대로 인쇄합니다. 그렇기 때문에 중요한 문서가 나중에 인쇄될 수 있습니다. 이런 문제를 보완하기 위해 중요도가 높은 문서를 먼저 인쇄하는 프린 programmers.co.kr 문제 설명 일반적인 프린터는 인쇄 요청이 들어온 순서대로 인쇄합니다. 그렇기 때문에 중요한 문서가 나중에 인쇄될 수 있습니다. 이런 문제를 보완하기 위해 중요도가 높은 문서를 먼저 인쇄하는 프린터를 개발했습니다. 이 새롭게 개발한 프린터는 아래와 같은 방식으로 인쇄 작업을 수행합니다. 1. 인쇄 대기목록의 가장 앞에 있는 문서(J)를 대기목록에서 꺼냅니다. 2. 나머지 인쇄 대기목록에서 J보다 중요도가 높은 문서가 한 개라도 존재하면 J를 대기목록의 가장 마지막에 ..

우선순위 큐(Priority Queue)란? 모든 데이터가 우선순위를 가지고 있고, 들어온 순서와 상관없이 우선순위가 높은 데이터가 먼저 출력된다. 스택이나 큐를 우선순위 큐로 구현할 수 있으며, 응용분야로는 네트워크 트래픽 제어, os의 작업 스케쥴링 등이 있다. 우선순위 큐 구현 방법 힙(heap)이란? 완전 이진트리(complete binary tree)로 구성되며 최대 힙, 최소 힙의 두 가지 표현법이 있다. 우선순위 큐를 위해 만들어진 자료구조로 큰 값이 상위 레벨에 있고 작은 값이 하위 레벨에 있다는 정도의 느슨한 정렬 상태를 유지한다. 힙의 목적이 삭제 연산에서 가장 큰 값을 효율적으로 찾아내기만 하면 되는 것이므로 전체를 정렬할 필요는 없다.(최대 힙을 가정할 때) 최대 힙(max heap..