우선순위큐3 [백준] 2075번 : N번째 큰 수 – JAVA [자바] https://www.acmicpc.net/problem/2075 문제 해결 방법이 문제를 해결하는 가장 직관적인 방법은 N×N개의 숫자를 정렬한 후 N번째 큰 값을 찾는 것이다. 하지만 이는 O(N² log N²) = O(N² log N)의 시간 복잡도를 가지므로, N = 1500인 경우 비효율적일 수 있다. 이를 해결하기 위해 우선순위 큐(PriorityQueue)를 활용하여 메모리를 절약하고 실행 속도를 개선할 수 있다. 최적화 방법 (최소 힙 사용)1. 최소 힙(PriorityQueue)을 사용하여 최대 N개의 숫자만 저장2. 처음 N개의 숫자는 힙에 삽입3. N+1번째 숫자부터는 힙의 최솟값(peek)보다 크면 교체4. N×N개의 숫자를 모두 처리한 후, 힙의 최솟값이 N번째 큰 수 이 방.. 2025. 3. 18. [백준] 15903번 : 카드 합체 놀이 – JAVA [자바] https://www.acmicpc.net/problem/15903 문제 해결 방법 이 문제는 그리디 알고리즘(Greedy Algorithm)을 이용하여 해결할 수 있다. 항상 가장 작은 두 수를 합치는 것이 최적의 선택이 되므로, 우선순위 큐(Priority Queue, 최소 힙)를 사용하면 효과적으로 풀 수 있다. 1. 처음에 주어진 n장의 카드를 우선순위 큐(최소 힙)에 넣는다. 2. m번 동안 다음 과정을 반복한다. - 가장 작은 두 개의 카드를 꺼낸다. - 두 값을 더한 뒤, 해당 값을 두 카드에 덮어쓴다. - 새로운 값을 다시 큐에 삽입한다. 3. 모든 합체가 끝난 후, 큐에 남아있는 값들의 합이 최종 점수가 된다. 코드 import java.io.*;import java.util.*;.. 2025. 3. 12. [백준] 11000번 : 강의실 배정 – JAVA [자바] https://www.acmicpc.net/problem/11000 문제문제 풀이문제 접근 방법:1. 수업을 정렬하여 집행 순서 정하기수업 시작 시간을 기준으로 오름차순 정렬한다.같은 시작 시간이면 종료 시간을 기준으로 정렬한다2. 우선순위 큐를 활용한 강의실 배정종료 시간이 가장 빠른 수업부터 관리하여 강의실을 재사용할 수 있는지 확인한다.종료 시간이 가장 빠른 수업을 추적하기 위해 우선순위 큐(Priority Queue, Min-Heap) 를 사용한다3. 그리디 알고리즘현재 진행 중인 강의 중 가장 빨리 끝나는 강의와 새 강의의 시작 시간을 비교한다.만약 현재 진행 중인 강의가 끝난 후 새 강의를 배정할 수 있다면, 기존 강의실을 재사용한다.그렇지 않다면 새로운 강의실을 추가해야 한다.4. 강의실 개.. 2025. 2. 21. 이전 1 다음 반응형
