priority queue
-
백준 11000 강의실 배정Algorithm/BOJ 2021. 4. 8. 15:57
출처: www.acmicpc.net/problem/11000 분류: priority queue, greedy 접근방식 문제를 똑바로 안 읽어서 좀 헤맸던 문제입니다.. 문제를 잘 이해해야 하는데요, 강의실에 수업을 배정하는 것이 아니라, 강의를 소화할 수 있게 강의실을 몇 개나 만들어야 하는지 찾는 문제입니다. 따라서 수업을 시작시간을 기준으로 정렬해두고, 생성된 강의실들 중에서 가장 빨리 끝나는 강의실과 수업의 시작시간을 비교해서 시작이 가능하다면 그 강의실에 배정합니다. 우선순위 큐에서 하나 꺼내고 해당 강의실을 집어넣으면 같은 의미가 됩니다! 이렇게 진행하고 결과적으로 우선순위 큐에 남아있는 원소의 개수가 강의실의 개수가 됩니다. 간단하게만 대략적인 그림으로 살펴보면, 아래 그림과 같이 강의실 3개..
-
백준 1202 보석 도둑Algorithm/BOJ 2021. 4. 7. 13:56
출처: www.acmicpc.net/problem/1202 분류: 우선순위 큐, 그리디 접근방식 진짜 어마무시하게 틀렸던 문제입니다... 보석과 가방을 모두 오름차순으로 정렬해두고 가방에 담을 수 있는 보석들을 우선순위 큐에 담아서 가장 비싼 보석을 넣어주면 되는 문제였습니다. 핵심이 되는 코드 부분만 보시면 이해하실 수 있을거에요 :) var jamIdx = 0 for back in backs { while jamIdx Bool) { // 최대 힙인지 최소 힙인지 기준을 잡는다. self.orderCriteria = sort } public init(array: [T], so..
-
백준 1715 카드 정렬하기Algorithm/BOJ 2021. 4. 7. 12:57
출처: www.acmicpc.net/problem/1715 분류: 우선순위 큐, 힙 접근방식 가장 최소인 값 두 개를 계속 더해가면 되는 문제입니다. 문제는 어떻게 최소 두 개를 찾을지가 관건이네요. 역시 최대, 최소 하면 제일 먼저 떠오르는 건 힙이겠죠? 힙으로 풀어봤습니다. Heap 에 대해 궁금하시다면 여기로 다른 분들 풀이를 보니 이분탐색으로 풀어도 아슬아슬하게 통과는 되는 것 같더라구요. 해결방법 public struct Heap { private var nodes = [T]() private var orderCriteria: (T, T) -> Bool public init(sort: @escaping (T, T) -> Bool) { // 최대 힙인지 최소 힙인지 기준을 잡는다. self.ord..