우선순위큐

Algorithm/Baekjoon Online Judge
[Java] 백준 1933 (스카이라인) Gold 2
Problem : https://www.acmicpc.net/problem/1933 1933번: 스카이라인 첫째 줄에 건물의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 N개의 건물에 대한 정보가 주어진다. 건물에 대한 정보는 세 정수 L, H, R로 나타나는데, 각각 건물의 왼쪽 x좌표, 높이, 오 www.acmicpc.net Approach 우선순위 큐(PriorityQueue)와 TreeMap 자료구조를 활용하는 문제이다. 문제에서 원하는 것은 높이가 변하는 부분의 x좌표와 그 때의 최대높이이다. 이를 위해 우선순위 큐와 TreeMap을 사용한다. 우선순위 큐는 x좌표 기준 오름차순(같을 경우, 높이 기준 내림차순)으로, 트리맵은 높이 기준 내림차순의 정렬 기준을 규정한다..
→2021.06.03
Algorithm/Baekjoon Online Judge
[Java] 백준 21773 (가희와 프로세스 1) Gold 5
Problem : https://www.acmicpc.net/problem/21773 21773번: 가희와 프로세스 1 1초일 때 부터 4초일 때 상황을 그림으로 나타내면 아래와 같습니다. 아래 그림에서 주황색은 특정 시점에 스케쥴러가 선택한 프로세스를 의미합니다. www.acmicpc.net Approach 우선순위 큐(PriorityQueue) 를 이용한 문제이다. 문제의 로직은 다음과 같다. 레디 큐에서 가장 우선순위가 높은 프로세스를 꺼내 1초동안 실행시킨다. 꺼낸 프로세스를 제외한 레디 큐에 있는 모든 프로세스의 우선순위는 1증가한다. 위 로직을 구현하려면, 먼저 우선순위 큐의 정렬 기준을 확립해야 한다. 프로세스의 우선순위 기준 내림차순이 필요할 것이다. 이제 우선순위큐에서 프로세스를 하나 뽑..
→2021.06.02
Algorithm/Baekjoon Online Judge
[Java] 백준 2109 (순회강연) Gold 4
Problem : 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 Approach 우선순위 큐를 사용한 그리디(Greedy) 알고리즘 문제이다. 먼저 pay 기준 내림차순으로 정렬된 우선순위 큐가 필요하다. pay가 같을 경우에는 day가 더 작은 것이 우선이다. 그리고 주어진 입력 d의 최대 크기만큼의 cost 배열을 선언한다. cost[i] 는 i일에 얼마짜리 강의를 하는지를 저장한다. cost 배열의 총..
→2021.05.19
Algorithm/Baekjoon Online Judge
[Java] 백준 1766 (문제집) Gold 2
Problem : https://www.acmicpc.net/problem/1766 1766번: 문제집 첫째 줄에 문제의 수 N(1 ≤ N ≤ 32,000)과 먼저 푸는 것이 좋은 문제에 대한 정보의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 둘째 줄부터 M개의 줄에 걸쳐 두 정수의 순서쌍 A,B가 빈칸을 사이에 두고 주 www.acmicpc.net Approach 위상정렬 + PriorityQueue 를 활용한 문제이다. 위상정렬을 알고 있다면 꽤 쉬운 문제이다. 문제를 풀이하는데 있어 순서가 존재하므로 위상정렬을 떠올릴 수 있었다. 또한, 지금 풀 수 있는 문제가 여러개일 때, 번호가 작은 문제부터 풀어야 하므로 우선순위 큐를 생각할 수 있겠다. 입력을 모두 받을 때까지 inDegree 배열..
→2021.04.07

• 이전
• 1
• 다음