비선형 자료구조: 우선순위 큐(Priority Queue)

이번 글에서는, 우선순위 큐의 개념과 원리를 상세히 설명하고, 자바에서 우선순위 큐를 사용하는 예제 코드를 제공하겠습니다. 먼저, 우선순위 큐의 개념과 원리를 살펴보고, 그다음으로 자바에서 우선순위 큐를 사용하는 방법과 기본 연산에 대해 알아보겠습니다. 마지막으로 성능 측면을 고려한 구현 방법을 설명하겠습니다.

---

1. 우선순위 큐의 개념 및 원리

우선 순위 큐는 이름에서 알 수 있듯이 각 요소가 어떤 '우선행'을 가지는 추상적인 데이터 유형입니다. 이 '우선행'은 보통 요소의 값에 의해 결정되며, 때로는 별도의 비교 함수에 의해 결정됩니다. 일반적인 배열이나 리스트와 달리, 데이터가 추가되거나 제거됨에 따라 동적으로 재정렬됩니다.

---

2. 자바에서의 우선순위 큐 사용법 및 주요 기능

자바에서는 PriorityQueue 클래스를 활용하여 힙(heap)과 같은 성질을 가지는 데이터 구조인 '우선순위 큐'를 구현할 수 있습니다.

// PriorityQueue 생성 및 초기화

PriorityQueue<Integer> minHeap = new PriorityQueue<>();

PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());

 

// 값 추가

minHeap.add(1);

maxHeap.add(1);

 

// 최소값 혹은 최대값 확인 (제거하지 않음)

int minValue = minHeap.peek();

int maxValue = maxHeap.peek();

 

// 최소값 혹은 최대값 제거 및 반환

minValue = minHeap.poll();

maxValue = maxHeap.poll();

---

3. 우선순위 큐 활용 사례

 

우선순위 큐는 다양한 분야에서 활용되며, 그중 몇 가지 예시를 들어보겠습니다:

 

• Dijkstra 알고리즘:
  시작 노드로부터 모든 다른 노드까지의 최단 경로를 찾습니다.
  우선순위 큐는 그래프 알고리즘 중 하나인 Dijkstra의 최단 경로 알고리즘에서 사용됩니다. 이 알고리즘은 시작 노드로부터 모든 다른 노드까지의 최단 경로를 찾는데, 우선순위 큐를 사용하여 다음으로 탐색할 노드(가장 짧은 거리에 있는 노드)를 선택합니다.

 

• 임의의 K번째 요소 찾기:
  정렬된 데이터에서 K번째 요소를 효율적으로 찾아냅니다.
  우선순위 큐는 데이터 집합에서 임의의 K번째 요소를 효율적으로 찾아내는 문제에도 활용됩니다. 이러한 문제들은 대개 정렬된 데이터에서만 해결 가능하지만, 우선순위 큐를 사용하면 전체 데이터를 정렬하지 않아도 특정 위치의 값을 찾을 수 있습니다.

 

• 스케줄링:
  여러 작업 중 어떤 것을 먼저 처리할 것인지 결정합니다.
  운영 체제에서 작업이나 프로세스 스케줄링에도 우선순위 큐가 자주 활용됩니다. 여러 작업 중 어떤 것을 먼저 처리할 것인지 결정하는데 있어서, 각 작업이 가진 우선순위에 따라 결정하기 때문입니다.

---

4. 예제 코드

 

다음은 Dijkstra 알고리즘과 K번째 요소 찾기 알고리즘의 예제 코드입니다:

 

• Dijkstra 알고리즘:

public void dijkstra(int start, int[][] graph) {

    PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[1] - b[1]);

    int[] distance = new int[graph.length];

    Arrays.fill(distance, Integer.MAX_VALUE);

   

    pq.add(new int[]{start, 0});

    distance[start] = 0;

   

    while (!pq.isEmpty()) {

        int[] current = pq.poll();

        int currentNode = current[0];

        int currentDist = current[1];

       

        if (distance[currentNode] < currentDist) continue;

       

        for (int i=0; i<graph[currentNode].length; i++) {

            if (graph[currentNode][i] != 0) {

                int cost = distance[currentNode] + graph[currentNode][i];

                if (cost < distance[i]) {

                    distance[i] = cost;

                    pq.add(new int[]{i, cost});

                }

            }

        }

    }

 

    System.out.println(Arrays.toString(distance));

}

 

• 임의의 K번째 요소 찾기:

 

public static void findKthLargest(int[] nums, int k) {

   PriorityQueue<Integer> q = new PriorityQueue<>(k);

   for(int i: nums){

       q.offer(i);

 

       if(q.size()>k){

           q.poll();

       }

   }

 

   System.out.println(q.peek());

}

---

5. 결론

 

우선순위 큐는 복잡한 데이터 세트에서 가장 크거나 작은 요소, 혹은 특정 조건에 부합하는 요소를 빠르게 찾아내야 하는 경우 매우 유용한 자료구조입니다. 자바에서 제공하는 PriorityQueue 클래스와 같은 도구들을 활용하면 개발자가 직접 코드 작성 없이 필요한 기능을 쉽게 사용할 수 있습니다.

 

우선순위 큐와 관련된 알고리즘을 잘 이해하고 활용한다면, Dijkstra 최단 경로 구현 등 다양한 분야에서 복잡한 문제들을 효율적으로 해결할 수 있습니다. 그러므로 우선 숫자큽의 기본 개념과 원리, 그리고 이를 활용하는 방법에 대해 충분히 공부하고 이해하는 것이 중요합니다.

 

특히 실제 문제 상황에서 가장 적합한 알고리즘이나 자료구조를 선택하여 사용할 수 있도록 하는 것이 중요합니다. 예를 들어, 데이터 스트림에서 중앙값을 찾거나 K번째 최대/최소 원소를 찾는 등의 문제에 효율적으로 활용될 수 있습니다.

 

우선순위 큐는 비선형 자료구조 중 하나로서 많은 상황에서 높은 성능을 보여주는 자료구조입니다. 따라서 효과적인 소프트웨어 개발을 위해서는 우선순위 큐와 같은 자료구조에 대한 깊은 이해가 필수적입니다. 그래야만 복잡한 문제 상황에서도 적절한 자료구조를 선택하고, 효율적인 알고리즘을 설계하여 문제를 해결할 수 있습니다.

 

우선순위 큐와 관련된 이론적 지식과 실제 구현 능력, 그리고 이를 활용하는 알고리즘에 대한 이해는 복잡한 데이터 조작 문제를 보다 간결하고 효율적으로 해결할 수 있습니다. 자료구조는 결국 우리가 데이터를 어떻게 조직화하고 관리하는지에 대한 학문이므로, 알맞은 자료구조를 선택하고 활용하는 것이 중요합니다.