PriorityQueue2 [JAVA] 우선순위 큐 Priority Queue 📌 우선순위 큐란? 큐(Queue)는 먼저 들어오는 데이터가 먼저 나가는 FIFO(First-In-First-Out) 구조를 가진다. 하지만 우선순위 큐(Priority Queue)는 먼저 들어오는 데이터가 아니라, 우선순위가 높은 데이터가 먼저 나가는 형태의 구조를 가진다. 우선순위 큐는 힙을 이용하여 구현하는 것이 일반적이다. 📌 우선순위 큐의 특징 높은 우선순위의 요소를 먼적 꺼내서 처리하는 구조 내부 요소는 힙으로 구성되어 있음 이진 트리 구조 -> 시간 복잡도는 O(NlogN) 📌 우선순위 큐의 사용법 ✔️ 우선순위 큐 선언 import java.util.PriorityQueue; // import // 자료형에 맞는 priorityQueue 선언 // Integer형 우선순위가 낮은 숫자 순 .. 2023. 3. 22. 백준 1655번 : 가운데를 말해요 | JAVA 📌 알고리즘 선택 이 문제는 단순히 생각하면 입력받은 수들을 계속해서 정렬하고 가운데 값을 찾아주면 된다. 하지만 무턱대고 정렬하면 시간복잡도가 N x N x logN 까지 올라 시간초과가 난다... (당연함) 어떻게 시간복잡도를 줄일 수 있을까 고민하다가 시간복잡도를 N x logN 까지 줄일 수 있는 힙정렬(heap sort)을 활용했다. ✔️ 힙 정렬 Heap Sort 힙 정렬은 완전이진트리 형태를 이용하여 정렬하는 방식으로, 가장 큰 값이나 가장 작은 값이 필요할 때 활용하면 좋다. 하지만 힙 정렬을 사용한다고 하더라도 가운데 값을 구하기 위해서는 두개의 힙이 필요하다는 것이 핵심이다. 📌 풀이 일단 힙을 만들기 위해 우선순위 큐 PriorityQueue를 사용했다. 입력한 값의 작은 값들을 담는.. 2023. 3. 10. 이전 1 다음
