우선순위큐3

• 

  백준 알고리즘 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 핵심 요약 각 보석들(N개)의 무게 및 가격이 존재한다 가방들(K개)에는 담을 수 있는 최대 무게가 존재한다 각 가방에는 보석을 하나씩만 담을 수 있음 -> 가방들로 담을 수 있는 보석 가격 합의 최대를 구하기 생각한 방법 단순히 무게만 가지고, 가방이 담을 수 있는 최소 무게의 보석을 택하는 것이 아닌 최대의 가격을 함께 생각해서 담아야 함 또한, 가방의 무게를 정렬해서 구해야 왼쪽의 케이.. 알고리즘/Java 2024. 4. 11.

• 

  백준 1655번: 가운데를 말해요 문제 정보 1655번: 가운데를 말해요 첫째 줄에는 백준이가 외치는 정수의 개수 N이 주어진다. N은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수이다. 그 다음 N줄에 걸쳐서 백준이가 외치는 정수가 차례대로 주어진다. 정수는 -1 www.acmicpc.net 핵심 현재까지의 수의 개수가 홀수 개인 경우 가운데에 있는 수를 택하면 됨 짝수 개인 경우에는 두개의 수 중 작은 수를 택하면 됨 처음에는 이런 생각으로 정렬된 배열에서의 중앙 인덱스를 구해서 중앙값을 구하면 되겠다고 생각했지만, 생각해 보니 Heap은 내부가 정렬된 상태는 아니기 때문에 이렇게 풀이하지 못했다 정렬된 상태를 유지하는 자료구조를 써야하나? -> AVL 트리나 레드블랙 트리를 써야 할까도 생각했지만, 중앙 값을 구하는 것.. 알고리즘/Java 2024. 4. 11.

• 

  백준 알고리즘 1715번: 카드 정렬하기 문제 정보 1715번: 카드 정렬하기 정렬된 두 묶음의 숫자 카드가 있다고 하자. 각 묶음의 카드의 수를 A, B라 하면 보통 두 묶음을 합쳐서 하나로 만드는 데에는 A+B 번의 비교를 해야 한다. 이를테면, 20장의 숫자 카드 묶음과 30장 www.acmicpc.net 핵심 답이 도출되는 과정을 이해하면 문제를 쉽게 풀 수 있다! 간단히 설명하면, 이 문제는 카드 묶음 중에서 가장 작은 카드 묶음 두 개를 더해 가면서 문제를 풀이하면 된다 카드 묶음이 5장 있다고 가정해 보자, 우리는 카드 묶음 두 개를 고를 때 가지고 있는 묶음 중에서 가장 작은 2개의 묶음을 선택하면 된다 위처럼 모든 카드 묶음을 합쳐서 하나의 묶음으로 만들 때, (10, 20), (30, 30), (40, 50), (60, 90).. 알고리즘/Java 2024. 4. 10.