Leo.K | To become a cooler Developer

오늘도 정렬로 분류되는 알고리즘 문제를 풀어보도록 하자. 문제의 난이도가 골드 2로 올라와서 그런지 따져야 할 조건도 많고, 풀이도 떠올리기가 간단하지는 않았다. 기본 베이스는 정렬과 그리디 알고리즘이지만, 이번 문제는 우선순위 큐라는 자료구조를 적당히 잘 사용해서 풀어야 한다. 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 1. 문제 분석 보석의 수 N과 가방의 수 K의 최댓값이 ..

오늘은 우선순위큐에 대한 기본적인 문제를 풀어보았다. 혹시라도 우선순위큐를 처음 들어본 사람은 아래의 링크로 들어가서 정리된 내용을 한 번 공부하고 오길 바란다. https://cm-me0410.tistory.com/79 우선순위큐(Priority Queue) 오늘은 다익스트라 문제를 본격적으로 풀어보기 전에 먼저 그래프 문제에서 자주 사용하는 우선순위 큐라는 자료구조에 대해 정리를 해보겠다. 결국에 큐이기 때문에 add, poll, peek 등의 연산을 cm-me0410.tistory.com 오늘도 마찬가지로 한 문제을 풀이하려 했지만, 카테고리에 분류된 처음 두 문제가 너무 비슷하고 기본적인 문제이기 때문에 두 문제를 모두 풀이하도록 하겠다. 문제에 대한 링크를 아래에 걸어두도록 하겠다. 우선순위큐 ..

오늘은 다익스트라 문제를 본격적으로 풀어보기 전에 먼저 그래프 문제에서 자주 사용하는 우선순위 큐라는 자료구조에 대해 정리를 해보겠다. 결국에 큐이기 때문에 add, poll, peek 등의 연산을 수행하지만, 하는 일과 내부 구조는 기존의 큐와 완전히 다르다. poll이나 peek의 연산으로 추출되는 원소는 기존 큐의 연산순서인 FIFO에 따라서 제일 먼저 들어온 요소가 나오는 것이 아니라, 말 그대로 현재 큐 안에서 제일 우선순위가 높은 요소가 먼저 나온다. 이는 우선순위 큐가 기존 알던 큐가 아닌 힙(heap)이라는 자료구조로 구현되기 때문에 가능하다. 가장 많이 사용하는 형태는 클수록 우선순위가 높은 형태 or 작을수록 우선순위가 높은 형태이다. 어떤 우선순위 큐의 front에 위치하는 원소가 가..