최소힙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.

• 

  백준 알고리즘 1927번: 최소 힙 문제 정보 1927번: 최소 힙 첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0 www.acmicpc.net 핵심 최소 힙을 구현하거나, 이미 구현되어 있는 Collection 을 사용하면 된다 구현하는 경우에는 클래스를 만들어서, 풀어가면 되고 이미 있는 자료구조를 사용하려면 PriorityQueue (우선순위 큐)를 사용하면 된다 나는 그래도 힙에 대해서 다시금 정리할 겸 구현하여 풀이하는 식으로 풀어 나갔다 Heap 은 완전 이진 트리로 구현되는 자료구조이기 때문에, 노드의 개수를 알면 트리의 구조를 특정할 수 있다는 특징이 있다 그.. 알고리즘/Java 2024. 4. 8.