https://www.acmicpc.net/problem/13904 13904번: 과제 예제에서 다섯 번째, 네 번째, 두 번째, 첫 번째, 일곱 번째 과제 순으로 수행하고, 세 번째, 여섯 번째 과제를 포기하면 185점을 얻을 수 있다. www.acmicpc.net 난이도 : 골드 3 태그 : 자료 구조, 그리디 알고리즘, 정렬, 우선순위 큐 설명 과제는 마감일이 있고, 과제 하나를 끝내는 데에는 하루가 걸립니다. 과제를 풀 때마다 각기 다른 점수를 얻을 수 있을 때, 점수의 최댓값을 구하는 문제입니다. 어려운 것 같지만 천천히 접근해봅시다. 최댓값을 구하려면, 어떤 숙제를 해야 할까요? 바로 점수가 높은 숙제부터 하는 것입니다. 그럼 숙제를 언제 해야 할까요? 각 숙제는 마감일 안에 언제든지 하면 됩..

https://www.acmicpc.net/problem/2109 2109번: 순회강연 한 저명한 학자에게 n(0 ≤ n ≤ 10,000)개의 대학에서 강연 요청을 해 왔다. 각 대학에서는 d(1 ≤ d ≤ 10,000)일 안에 와서 강연을 해 주면 p(1 ≤ p ≤ 10,000)만큼의 강연료를 지불하겠다고 알려왔다. www.acmicpc.net 난이도 : 골드 3 태그 : 자료구조, 그리디 알고리즘, 우선순위 큐, 정렬 설명 d일 안에 강의를 하러 오면 p만큼의 돈을 받을 수 있습니다. n개의 강의를 갈 수 있을 때, 최대로 벌 수 있는 돈을 구하는 문제입니다. 이 문제를 처음 봤을 때 든 생각은, 아! 일자를 오름차순 정렬하고, 돈을 내림차순 정렬하면 되겠구나! 생각했습니다. 하지만, 머지않아 몇 개..

https://www.acmicpc.net/problem/11279 11279번: 최대 힙 첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0 www.acmicpc.net 난이도 : 실버 2 태그 : 자료 구조, 우선순위 큐 설명 https://uknowblog.tistory.com/126 [백준 1927번] [Kotlin] 최소 힙 https://www.acmicpc.net/problem/1927 1927번: 최소 힙 첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 ..

https://www.acmicpc.net/problem/1927 1927번: 최소 힙 첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0 www.acmicpc.net 난이도 : 실버 2 태그 : 자료 구조, 우선순위 큐 설명 최소 힙을 사용하여 1. 배열에 자연수 x를 넣고 2.가장 작은 값을 출력후 배열에서 제거 하는 프로그램을 만드는 문제입니다. 자바와 코틀린에는 기본적으로 지원되는 PrioryQueue 자료구조가 있습니다. 말 그대로, 우선순위에 따라 하나씩 꺼내올 수 있는 큐 인데요. 만약 1, 3, 5, 2, 0, 10 순으로 넣었..

https://www.acmicpc.net/problem/1202 1202번: 보석 도둑 첫째 줄에 N과 K가 주어진다. (1 ≤ N, K ≤ 300,000) 다음 N개 줄에는 각 보석의 정보 Mi와 Vi가 주어진다. (0 ≤ Mi, Vi ≤ 1,000,000) 다음 K개 줄에는 가방에 담을 수 있는 최대 무게 Ci가 주어진다. (1 ≤ Ci www.acmicpc.net 난이도 : 골드 2 태그 : 자료 구조, 그리디 알고리즘, 정렬, 우선순위 큐 설명 정렬과 우선순위 큐를 사용해 풀 수 있습니다. 보석의 경우, 무게로 내림차순 정렬하고, 무게가 같을 경우 오름차순 정렬을 합니다. 가방도 무게를 기준으로 오름차순 정렬하고, 각 가방의 무게보다 가볍거나, 같은 보석의 가격을 우선순위 큐(내림차순)에 넣고,..

https://www.acmicpc.net/problem/1715 1715번: 카드 정렬하기 정렬된 두 묶음의 숫자 카드가 있다고 하자. 각 묶음의 카드의 수를 A, B라 하면 보통 두 묶음을 합쳐서 하나로 만드는 데에는 A+B 번의 비교를 해야 한다. 이를테면, 20장의 숫자 카드 묶음과 30장 www.acmicpc.net 난이도 : 골드 4 태그 : 자료 구조, 그리디 알고리즘, 우선순위 큐 설명 비교 횟수가 최소가 되려면 매번 가장 작은 개수의 카드 묶음 두개씩 비교하여 합치면 됩니다. 매번 정렬하여 가장 작은 값 두개를 찾을 필요 없이, 우선순위 큐를 사용하면 쉽게 구할 수 있습니다. 소스코드 import java.util.PriorityQueue fun main() { val br = Syste..

https://www.acmicpc.net/problem/7662 7662번: 이중 우선순위 큐 입력 데이터는 표준입력을 사용한다. 입력은 T개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에는 입력 데이터의 수를 나타내는 정수 T가 주어진다. 각 테스트 데이터의 첫째 줄에는 Q에 적 www.acmicpc.net 난이도 : 골드 4 태그 : 자료구조, 트리를 사용한 집합과 맵, 우선순위 큐 설명 우선순위가 최대 혹은 최소인 원소만 뺏던 기존 우선순위 큐와 달리, 최대와 최소 모두 뺄 수 있는 우선순위 큐 입니다. LinkedList도 써보고, 직접 배열로 우선순위 큐도 구현해 봤는데... 시간초과에서 헤어나오질 못해 검색해 봤더니 TreeMap이라는 자료구조를 발견하게 되었습니다. TreeMap은 키값..