CT | 우선순위 큐(Priority Queue)?

Coding Test

CT | 우선순위 큐(Priority Queue)?

이진유진 2025. 1. 7. 20:25

우선순위 큐(Priority Queue)?

큐에서 각 원소가 우선순위(priority)를 가지며, 높은 우선순위를 가진 원소가 먼저 처리되는 자료구조입니다.

일반 큐에서는 원소가 들어온 순서대로 처리되지만, 우선순위 큐에서는 우선순위가 높은 원소가 먼저 나옵니다.

우선순위 큐는 내부적으로 힙(Heap)구조를 사용하여 구현되는 경우가 많습니다.

이때 우선순위 큐는 최대 힙(Max Heap)또는 최소 힙(Min Heap)을 사용할 수 있습니다.

최대 힙: 가장 높은 우선순위를 가진 원소가 가장 먼저 나오도록 합니다.
최소 힙: 가장 낮은 우선순위를 가진 원소가 가장 먼저 나오도록 합니다.

기본적인 우선순위 큐 사용(최소 힙)

import java.util.PriorityQueue;

public class PriorityQueueExample {
    public static void main(String[] args) {
        // 우선순위 큐 생성 (기본적으로 최소 힙)
        PriorityQueue<Integer> pq = new PriorityQueue<>();

        // 요소 삽입
        pq.offer(10);
        pq.offer(20);
        pq.offer(15);
        pq.offer(5);

        // 우선순위 큐에서 최소값을 꺼냄
        System.out.println("우선순위 큐에서 꺼낸 값: " + pq.poll()); // 5
        System.out.println("우선순위 큐에서 꺼낸 값: " + pq.poll()); // 10
    }
}

최대 힙 구현(Comparator 사용)

import java.util.PriorityQueue;
import java.util.Comparator;

public class MaxHeapExample {
    public static void main(String[] args) {
        // 최대 힙을 만들기 위한 우선순위 큐
        PriorityQueue<Integer> pq = new PriorityQueue<>(Comparator.reverseOrder());

        // 요소 삽입
        pq.offer(10);
        pq.offer(20);
        pq.offer(15);
        pq.offer(5);

        // 우선순위 큐에서 최대값을 꺼냄
        System.out.println("우선순위 큐에서 꺼낸 값: " + pq.poll()); // 20
        System.out.println("우선순위 큐에서 꺼낸 값: " + pq.poll()); // 15
    }
}

사용자 정의 객체와 함께 사용

import java.util.PriorityQueue;
import java.util.Comparator;

class Person {
    String name;
    int age;

    public Person(String name, int age) {
        this.name = name;
        this.age = age;
    }

    // 우선순위 큐에서 나이를 기준으로 정렬하도록 Comparable 구현
    public int getAge() {
        return age;
    }

    @Override
    public String toString() {
        return name + " (" + age + ")";
    }
}

public class PriorityQueueWithObjects {
    public static void main(String[] args) {
        // 나이를 기준으로 정렬하는 우선순위 큐 생성
        PriorityQueue<Person> pq = new PriorityQueue<>(Comparator.comparingInt(Person::getAge));

        // 객체 삽입
        pq.offer(new Person("Alice", 30));
        pq.offer(new Person("Bob", 25));
        pq.offer(new Person("Charlie", 35));

        // 우선순위 큐에서 나이가 가장 어린 사람을 꺼냄
        System.out.println("우선순위 큐에서 꺼낸 사람: " + pq.poll()); // Bob (25)
        System.out.println("우선순위 큐에서 꺼낸 사람: " + pq.poll()); // Alice (30)
    }
}

우선순위 큐의 주요 연산

삽입 (insert): offer() 또는 add() 메서드를 사용하여 우선순위 큐에 원소를 삽입합니다.
삭제 (remove): poll() 메서드를 사용하여 우선순위 큐에서 우선순위가 가장 높은(또는 낮은) 원소를 제거합니다.
조회 (peek): peek() 메서드를 사용하여 우선순위 큐에서 우선순위가 가장 높은(또는 낮은) 원소를 조회합니다.

import java.util.PriorityQueue;

public class PriorityQueueOperations {
    public static void main(String[] args) {
        // 우선순위 큐 생성 (기본적으로 최소 힙)
        PriorityQueue<Integer> pq = new PriorityQueue<>();

        // 삽입 (insert) - offer() 또는 add() 메서드를 사용
        pq.offer(10);  // 10을 큐에 삽입
        pq.offer(20);  // 20을 큐에 삽입
        pq.offer(15);  // 15를 큐에 삽입
        pq.offer(5);   // 5를 큐에 삽입

        // 현재 우선순위 큐 상태
        System.out.println("현재 우선순위 큐: " + pq);

        // 조회 (peek) - 우선순위가 가장 높은 원소를 확인
        System.out.println("우선순위 큐에서 가장 작은 값 (peek): " + pq.peek());  // 가장 작은 값인 5

        // 삭제 (remove) - 우선순위가 가장 높은(가장 작은) 원소를 제거
        System.out.println("우선순위 큐에서 꺼낸 값 (poll): " + pq.poll());  // 5가 제거됨
        System.out.println("우선순위 큐에서 꺼낸 값 (poll): " + pq.poll());  // 10이 제거됨

        // 큐 상태 출력
        System.out.println("현재 우선순위 큐: " + pq);

        // 또 다른 삭제
        System.out.println("우선순위 큐에서 꺼낸 값 (poll): " + pq.poll());  // 15가 제거됨
        System.out.println("우선순위 큐에서 꺼낸 값 (poll): " + pq.poll());  // 20이 제거됨

        // 큐가 비었으므로 peek은 null을 반환
        System.out.println("우선순위 큐에서 가장 작은 값 (peek): " + pq.peek());  // null (큐가 비어있음)
    }
}

실행 결과

현재 우선순위 큐: [5, 10, 15, 20]
우선순위 큐에서 가장 작은 값 (peek): 5
우선순위 큐에서 꺼낸 값 (poll): 5
우선순위 큐에서 꺼낸 값 (poll): 10
현재 우선순위 큐: [15, 20]
우선순위 큐에서 꺼낸 값 (poll): 15
우선순위 큐에서 꺼낸 값 (poll): 20
우선순위 큐에서 가장 작은 값 (peek): null

우선순위 큐(Priority Queue) - 알고리즘에서의 역할

스케줄링 : 우선순위에 따라 작업 처리

import java.util.PriorityQueue;

class Task {
    String name;
    int priority;  // 낮을수록 높은 우선순위

    public Task(String name, int priority) {
        this.name = name;
        this.priority = priority;
    }

    @Override
    public String toString() {
        return name + " (priority: " + priority + ")";
    }
}

public class SchedulingExample {
    public static void main(String[] args) {
        // 우선순위 큐 생성 (최소 힙 사용, 우선순위가 낮을수록 먼저 처리)
        PriorityQueue<Task> pq = new PriorityQueue<>((t1, t2) -> Integer.compare(t1.priority, t2.priority));

        // 작업 삽입
        pq.offer(new Task("Task A", 2));
        pq.offer(new Task("Task B", 1));
        pq.offer(new Task("Task C", 3));

        // 우선순위 큐에서 가장 우선순위가 높은 작업을 처리
        while (!pq.isEmpty()) {
            System.out.println("Processing: " + pq.poll());
        }
    }
}

Processing: Task B (priority: 1)
Processing: Task A (priority: 2)
Processing: Task C (priority: 3)

다익스트라 알고리즘 - 최단 경로 알고리즘에서 우선순위 큐를 사용하여 효율적으로 경로를 선택

import java.util.*;

class Graph {
    Map<Integer, List<int[]>> adjList = new HashMap<>();  // node -> [(neighbor, weight)]

    // 그래프에 엣지 추가
    public void addEdge(int u, int v, int w) {
        adjList.putIfAbsent(u, new ArrayList<>());
        adjList.get(u).add(new int[]{v, w});
    }

    // 다익스트라 알고리즘
    public Map<Integer, Integer> dijkstra(int start) {
        Map<Integer, Integer> dist = new HashMap<>();  // node -> shortest distance
        PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(a -> a[1]));  // [node, distance]
        pq.offer(new int[]{start, 0});  // 시작 노드, 거리 0

        while (!pq.isEmpty()) {
            int[] current = pq.poll();
            int node = current[0];
            int currentDist = current[1];

            if (dist.containsKey(node)) continue;  // 이미 방문한 노드는 무시

            dist.put(node, currentDist);

            // 인접 노드 방문
            for (int[] neighbor : adjList.getOrDefault(node, Collections.emptyList())) {
                int nextNode = neighbor[0];
                int weight = neighbor[1];
                if (!dist.containsKey(nextNode)) {
                    pq.offer(new int[]{nextNode, currentDist + weight});
                }
            }
        }
        return dist;
    }
}

public class DijkstraExample {
    public static void main(String[] args) {
        Graph graph = new Graph();
        graph.addEdge(1, 2, 1);
        graph.addEdge(1, 3, 4);
        graph.addEdge(2, 3, 2);
        graph.addEdge(2, 4, 5);
        graph.addEdge(3, 4, 1);

        Map<Integer, Integer> shortestPaths = graph.dijkstra(1);
        System.out.println("Shortest paths from node 1: " + shortestPaths);
    }
}

Shortest paths from node 1: {1=0, 2=1, 3=3, 4=4}

위의 코드는 다익스트라 알고리즘을 사용하여 그래프의 특정 시작 노드에서 다른 모든 노드까지의 최단 경로를 계산하는 프로그램입니다.

1. Graph 클래스

이 클래스는 그래프를 표현하고, 다익스트라 알고리즘을 구현합니다.

1 인접 리스트(adjList)

Map<Integer, List<int[]>> adjList = new HashMap<>();

그래프는 인접 리스트 방식으로 저장됩니다.
각 노드(Integer)는 연결된 다른 노드들의 리스트(List<int[]>)를 가집니다.
각 리스트 항목은 {neighbor, weight} 형태의 배열(int[]) 입니다.
- neighbor : 연결된 노드 번호
- weight : 해당 간선의 가중치(거리)

2 addEdge 메서드

public void addEdge(int u, int v, int w) {
    adjList.putIfAbsent(u, new ArrayList<>());
    adjList.get(u).add(new int[]{v, w});
}

기능 : 그래프에 엣지(간선)를 추가합니다.
- u : 시작 노드
- v : 끝 노드
- w : u에서 v로 가는 간선의 가중치
동작 :
- adjList에서 시작노드 u가 없으면 빈 리스트를 추가합니다.
- {v, w} (목적지 노드와 가중치)를 시작 노드 u의 리스트에 추가합니다.

3 dijkstra 메서드

public Map<Integer, Integer> dijkstra(int start) {

기능 : 특정 시작 노드(start)에서 모든 노드까지의 최단 거리를 계산합니다.
반환값 : Map<Integer, Integer> 형태로 반환하며, 각 노드와 최단 거리를 저장합니다.

변수 설명

Map<Integer, Integer> dist = new HashMap<>();
PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(a -> a[1]));

dist
1. 각 노드의 최단 거리를 저장합니다.
2. 키: 노드 번호, 값: 시작 노드에서 해당 노드까지의 최단 거리
3. 방문하지 않은 노드는 값이 비어있음
pq :
1. 우선순위 큐로, (노드 번호, 현재까지의 거리) 형태의 배열을 저장합니다.
2. Comparator를 사용하여 거리(a[1])가 작은 순서대로 정렬됩니다.
3. 이를 통해 항상 현재까지의 거리가 가장 짧은 노드를 먼저 탐색합니다.

알고리즘 동작

pq.offer(new int[]{start, 0});  // 시작 노드, 거리 0

시작 노드(start)와 그 거리를 pq에 추가합니다.

while (!pq.isEmpty()) {
    int[] current = pq.poll();
    int node = current[0];
    int currentDist = current[1];

큐에서 우선순위가 가장 높은(가장 짧은 거리) 노드를 꺼냅니다.
current[0]은 노드 번호, current[1]은 현재까지의 거리입니다.

if (dist.containsKey(node)) continue;
dist.put(node, currentDist);

이미 최단 거리를 계산한 노드는 무시합니다 (continue).
그렇지 않다면, 현재 노드와 그 거리를 dist에 저장합니다.

for (int[] neighbor : adjList.getOrDefault(node, Collections.emptyList())) {
    int nextNode = neighbor[0];
    int weight = neighbor[1];
    if (!dist.containsKey(nextNode)) {
        pq.offer(new int[]{nextNode, currentDist + weight});
    }
}

현재 노드와 연결된 모든 이웃 노드(neighbor)를 확인합니다.
- nextNode : 이웃 노드 번호
- weight : 현재 노드에서 이웃 노드로 가는 간선의 가중치
이웃 노드가 아직 방문되지 않았다면, (이웃 노드, 누적 거리)를 큐에 추가합니다.

허프만 코딩 - 데이터 압축 알고리즘에서 우선순위 큐를 사용하여 빈도가 높은 데이터를 우선 처리할 때

허프만 코딩(Huffman Coding)은 데이터를 압축하는 알고리즘입니다.

이 알고리즘은 문자 빈도에 따라 최소 비용의 이진 트리를 만들어 데이터를 압축합니다.

우선순위 큐를 사용하여 가장 빈도가 낮은 문자를 우선 처리하는 방식으로 트리를 구성합니다.

import java.util.*;

class Node {
    char character;
    int frequency;
    Node left, right;

    public Node(char character, int frequency) {
        this.character = character;
        this.frequency = frequency;
        left = right = null;
    }
}

public class HuffmanCodingExample {
    public static void main(String[] args) {
        // 문자의 빈도수
        Map<Character, Integer> freqMap = new HashMap<>();
        freqMap.put('a', 5);
        freqMap.put('b', 9);
        freqMap.put('c', 12);
        freqMap.put('d', 13);
        freqMap.put('e', 16);
        freqMap.put('f', 45);

        // 우선순위 큐를 사용하여 허프만 트리 구성
        PriorityQueue<Node> pq = new PriorityQueue<>(Comparator.comparingInt(a -> a.frequency));
        for (Map.Entry<Character, Integer> entry : freqMap.entrySet()) {
            pq.offer(new Node(entry.getKey(), entry.getValue()));
        }

        while (pq.size() > 1) {
            // 두 개의 가장 작은 빈도수 노드를 꺼냄
            Node left = pq.poll();
            Node right = pq.poll();

            // 새로운 노드 생성 (빈도수 합)
            Node newNode = new Node('\0', left.frequency + right.frequency);
            newNode.left = left;
            newNode.right = right;

            // 새로운 노드를 큐에 삽입
            pq.offer(newNode);
        }

        // 최종적으로 트리가 하나 남으면, 그것이 허프만 트리
        Node root = pq.poll();
        System.out.println("허프만 트리의 루트: " + root.frequency);
    }
}

'Coding Test' 카테고리의 다른 글

CT \| 코딩테스트 연습하기 좋은 순서(백준) (1)	2024.12.09
CT \|백준 15650번 N과 M (2) (0)	2024.11.12
CT \| 백준 15649번 N과 M (1) (0)	2024.11.07
CT \| 백준 1780번 종이의 개수 (0)	2024.11.06
CT \| 백준 17478번 재귀함수가 뭔가요? (0)	2024.11.06

현재글CT | 우선순위 큐(Priority Queue)?

BinaryYujin