9.1 우선순위 큐 추상 데이터 타입
우선순위 큐(priority Queue)의 소개
우선순위 큐에서는 데이터들이 우선 순위를 가지고 있고 우선 순위가 높은 데이터가 먼저 나가게 된다.
우선순위 큐는 배열, 연결 리스트 등의 여러 가지 방법으로 구현이 가능한데, 가장 효율적인 구조는 힙(heap)이다.
우선순위 큐 추상자료형
객체: n개의 element형의 우선 순위를 가진 요소들의 모임
연산:
create() ::= 우선순위 큐를 생성한다.
init(q) ::= 우선순위 큐 q를 초기화한다.
is_empty(q) ::= 우선순위 큐 q가 비어있는지를 검사한다.
is_full(q) ::= 우선순위 큐 q가 가득 찼는가를 검사한다.
insert(q, x) ::= 우선순위 큐 q에 요소 x를 추가한다.
delete(q) ::= 우선순위 큐로부터 가장 우선순위가 높은 요소를 삭제하고 반환한다.
find(q) ::= 우선순위가 가장 높은 요소를 반환한다.9.2 우선순위 큐의 구현 방법
heap을 사용하는 방법
heap은 CBT(완전 이진 트리)의 일종으로 우선순위 큐를 위하여 특별히 만들어진 자료 구조이다. heap은 일종의 느슨한 정렬 상태를 유지한다. 즉 완전히 정렬된 것은 아니지만 전혀 정렬이 안 된 것도 아닌 상태를 유지한다.
| 표현 방법 | 삽입 | 삭제 |
|---|---|---|
| 순서 없는 배열 | O(1) | O(n) |
| 순서 없는 연결 리스트 | O(1) | O(n) |
| 정렬된 배열 | O(n) | O(1) |
| 정렬된 연결 리스트 | O(n) | O(1) |
| heap | O(logn) | O(logn) |
9.3 heap
heap의 개념
heap을 영어 사전에서 찾아보면 "더미"라고 되어 있다. 컴퓨터 분야에서 heap은 CBT 기반의 "더미"와 모습이 비슷한 특정한 자료 구조를 의미한다.
heap은 여러 개의 값들 중에서 가장 큰 값이나 가장 작은 값을 빠르게 찾아내도록 만들어진 자료 구조이다. heap은 간단히 말하면 부모 노드의 키 값이 자식 노드의 키 값보다 항상 큰 이진 트리를 말한다.
heap 트리에서는 중복된 값을 허용한다.
heap의 종류
- 부모 노드의 키 값이 자식 노드보다 큰 max heap
- 부모 노드의 키 값이 자식 노드보다 작은 min heap
heap의 구현
heap은 완전 이진 트리이기 때문에 각각의 노드에 차례대로 번호를 붙일 수 있다. 이 번호를 배열의 인덱스로 생각하면 배열에 heap의 노드들을 저장할 수 있다. 따라서 heap을 저장하는 표준적인 자료 구조는 배열이다. 프로그램 구현을 쉽게 하기 위하여 배열의 첫 번째 인덱스인 0은 사용되지 않는다. 특정 위치의 노드 번호는 새로운 노드가 추가되어도 변하지 않음을 유의하라. 예를 들어 루트 노드의 오른쪽 노드의 번호는 항상 3번이다.
9.4 heap의 구현
heap의 정의
#define MAX_ELEMENT 200
typedef struct {
int key;
} element;
typedef struct {
element heap[MAX_ELEMENT];
int heap_size;
} HeapType;삽입 연산
heap에 새로운 요소가 들어오면, 일단 새로운 노드를 heap의 마지막 노드로 삽입된다. 마지막 노드 다음에 새로운 노드를 위치시키면 heap 트리의 성질이 만족되지 않을 수 있다. 따라서 삽입 후에 새로운 노드를 부모 노드들과 교환해서 heap의 성질을 만족시켜 주어야 한다.
insert_max_heap(A, key):
1. heap_size ← heap_size + 1;
2. i ← heap_size;
3. A[i] ← key;
4. while i != 1 and A[i] > A[PARENT(i)] do
5. A[i] <-> A[PARAENT];
6. i ← PARENT(i);삭제 연산
max heap에서 삭제 연산은 최대값을 가진 요소를 삭제하는 것이다. max heap에서 최대값은 루트 노드이므로 루트 노드가 삭제된다. 루트 노드 삭제 후에 heap을 재구성하는 것이 필요하게 된다. heap의 재구성이란 heap의 성질을 만족하기 위하여 위, 아래 노드를 교환하는 것이다.
delete_max_heap(A):
1. item ← A[1];
2. A[1] ← A[heap_size];
3. heap_size ← heap_size - 1;
4. i ← 2
5. while i <= heap_size do
6. if i < heap_size and A[i+1] > A[i]
7. then largest ← i + 1;
8. else largest ← i;
9. if A[PARENT(largest)] > A[largest]
10. then break;
11. A[PARAENT(largest)] <-> A[largest];
12. i ← CHILD(largest);
13.
14.return item;전체 프로그램
import java.util.ArrayList;
public class MaxHeap {
private final ArrayList<Integer> heap = new ArrayList<>();
public void insert(int val) {
heap.add(val);
upHeap(heap.size() - 1);
}
public int remove() {
if (heap.isEmpty()) throw new IllegalStateException("Heap is empty");
int root = heap.get(0);
int last = heap.remove(heap.size() - 1);
if (!heap.isEmpty()) {
heap.set(0, last);
downHeap(0);
}
return root;
}
public int peek() {
if (heap.isEmpty()) throw new IllegalStateException("Heap is empty");
return heap.get(0);
}
public boolean isEmpty() {
return heap.isEmpty();
}
private void upHeap(int i) {
while (i > 0) {
int parent = (i - 1) / 2;
if (heap.get(i) <= heap.get(parent)) break;
swap(i, parent);
i = parent;
}
}
private void downHeap(int i) {
int size = heap.size();
while (true) {
int left = 2 * i + 1;
int right = 2 * i + 2;
int largest = i;
if (left < size && heap.get(left) > heap.get(largest)) {
largest = left;
}
if (right < size && heap.get(right) > heap.get(largest)) {
largest = right;
}
if (largest == i) break;
swap(i, largest);
i = largest;
}
}
private void swap(int i, int j) {
int tmp = heap.get(i);
heap.set(i, heap.get(j));
heap.set(j, tmp);
}
public void printHeap() {
System.out.println(heap);
}
}heap의 복잡도 분석
| 연산 | 시간복잡도 | 설명 |
|---|---|---|
| insert | O(log n) | 마지막 위치에 넣고 up-heap |
| remove | O(log n) | 루트 삭제, 마지막 노드를 루트로 → down-heap |
| peek | O(1) | 최댓값 바로 확인 |
| 내부구조 | 완전 이진 트리 | ArrayList로 구현 |
Java의 PriorityQueue
Java의 PriorityQueue는 우선순위 큐(priority queue)를 제공하는 클래스입니다.
내부적으로는 Min-Heap 구조로 구현되어 있으며, 요소들이 우선순위(작은 값 기준)에 따라 자동으로 정렬됩니다.
내부 구조: Min-Heap
- 내부적으로 ArrayList 형태의 완전 이진 트리 사용
- 삽입 시 → up-heap
- 삭제 시 → down-heap
핵심 요약
| 항목 | 설명 |
|---|---|
| 클래스 | java.util.PriorityQueue |
| 내부 구조 | Min-Heap (완전 이진 트리) |
| 정렬 기준 | 기본: 자연 순서 (Comparable) 사용자 지정: Comparator |
| null 허용 여부 | ❌ 요소로 null 허용하지 않음 |
| 주요 메서드 | add(), offer(), poll(), peek() 등 |
| 시간복잡도 | 삽입/삭제 O(log n), 조회 O(1) |
주요 메서드
| 메서드 | 설명 |
|---|---|
add(E e) | 요소 추가 (예외 발생 가능) |
offer(E e) | 요소 추가 (성공 여부 반환) |
peek() | 최우선 요소 조회 (제거하지 않음) |
poll() | 최우선 요소 제거 및 반환 |
remove() | 특정 요소 제거 |
isEmpty() | 비었는지 확인 |
예시 1. 기본 Min-Heap (오름차순)
import java.util.PriorityQueue;
public class Main {
public static void main(String[] args) {
PriorityQueue<Integer> pq = new PriorityQueue<>();
pq.add(5);
pq.add(1);
pq.add(3);
while (!pq.isEmpty()) {
System.out.println(pq.poll()); // 출력: 1, 3, 5
}
}
}예시 2. Max-Heap 만들기 (내림차순)
PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Comparator.reverseOrder());
maxHeap.add(5);
maxHeap.add(1);
maxHeap.add(3);
while (!maxHeap.isEmpty()) {
System.out.println(maxHeap.poll()); // 출력: 5, 3, 1
}예시 3. 사용자 정의 객체 우선순위
class Task {
String name;
int priority;
Task(String name, int priority) {
this.name = name;
this.priority = priority;
}
}
PriorityQueue<Task> taskQueue = new PriorityQueue<>(
Comparator.comparingInt(t -> t.priority)
);
taskQueue.add(new Task("email", 2));
taskQueue.add(new Task("build", 1));
System.out.println(taskQueue.poll().name); // build9.5 heap 정렬
heap 정렬의 구현
public class HeapSort {
public static void heapSort(int[] arr) {
int n = arr.length;
// 1. Max-Heap 만들기
for (int i = n / 2 - 1; i >= 0; i--) {
heapify(arr, n, i);
}
// 2. 하나씩 꺼내서 정렬 영역으로 이동
for (int i = n - 1; i > 0; i--) {
swap(arr, 0, i); // 루트(최댓값) → 끝으로
heapify(arr, i, 0); // 나머지로 Max-Heap 유지
}
}
private static void heapify(int[] arr, int heapSize, int i) {
int largest = i;
int left = 2 * i + 1;
int right = 2 * i + 2;
if (left < heapSize && arr[left] > arr[largest]) {
largest = left;
}
if (right < heapSize && arr[right] > arr[largest]) {
largest = right;
}
if (largest != i) {
swap(arr, i, largest);
heapify(arr, heapSize, largest); // 재귀적으로 자식까지 내려감
}
}
private static void swap(int[] arr, int i, int j) {
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
// 테스트용
public static void main(String[] args) {
int[] arr = {5, 2, 8, 4, 1, 9, 3};
heapSort(arr);
for (int num : arr) {
System.out.print(num + " ");
}
// 출력: 1 2 3 4 5 8 9
}
}import java.util.Collections;
import java.util.PriorityQueue;
public class HeapSortDescending {
public static void heapSortDescending(int[] arr) {
PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());
for (int num : arr) {
pq.add(num);
}
int i = 0;
while (!pq.isEmpty()) {
arr[i++] = pq.poll(); // 가장 큰 값부터 꺼냄
}
}
public static void main(String[] args) {
int[] arr = {5, 2, 8, 4, 1, 9, 3};
heapSortDescending(arr);
for (int num : arr) {
System.out.print(num + " ");
}
// 출력: 9 8 5 4 3 2 1
}
}PriorityQueue<Integer>는 내부적으로 이진 힙(Binary Heap) 구조입니다.
즉, add()로 삽입할 때마다, 그리고 poll()로 꺼낼 때마다,
자동으로 Heapify 작업을 통해 루트(root)에 우선순위가 가장 높은 요소(= 가장 작은 값)가 유지됩니다.
heap 정렬의 복잡도
| 단계 | 복잡도 |
|---|---|
| Heap 구성 | O(n) *아랫 노드는 대부분 O(1)이기 때문 |
| Heap 정렬 | O(n log n) |
| 전체 | O(n log n) |
공간 복잡도는 O(1) (in-place 정렬)
9.6 Machine Scheduling
머신 스케줄링 문제(Machine Scheduling Problem)는 다음을 만족하도록 작업(Job)들을 기계(Machine)에 배정하는 최적화 문제입니다:
“작업들을 여러 기계에 적절히 나눠서 총 수행 시간(Makespan)을 최소화하라”
기본 용어 정리
| 용어 | 의미 |
|---|---|
| Job | 수행해야 할 단위 작업, 각 작업은 고유한 처리 시간 보유 |
| Machine | 작업을 처리할 수 있는 자원 (동시에 여러 대 운용 가능) |
| Processing Time | 작업 하나를 수행하는 데 필요한 시간 |
| Schedule | 어떤 작업을 어떤 순서로 어떤 머신에 배정할지 결정한 것 |
| Makespan | 모든 작업이 끝나는 데 걸리는 총 시간 (최종 완료 시간) |
| Load | 한 머신이 처리하는 작업들의 총합 시간 |
대표적인 문제 유형
| 유형 | 설명 |
|---|---|
| Parallel Machine Scheduling | 동일한 m개의 기계에 n개의 작업을 분배 |
| Open Shop Scheduling | 각 작업이 순서를 따르지 않고 여러 기계에서 처리되어야 함 |
| Flow Shop Scheduling | 모든 작업이 동일한 순서로 여러 기계를 거침 |
| Job Shop Scheduling | 각 작업마다 기계 순서가 다름 (산업 현장에서 현실적) |
| Online Scheduling | 작업이 실시간으로 들어오며 즉시 결정해야 함 |
대표 알고리즘
| 알고리즘 | 설명 | 시간복잡도 |
|---|---|---|
| Greedy (List Scheduling) | 가장 빈 머신에 순서대로 할당 | O(n log m) |
| LPT (Longest Processing Time first) | 처리 시간 긴 작업부터 할당 | O(n log n + n log m) |
| SPT (Shortest Processing Time first) | 평균 지연 최소화용 | O(n log n) |
| Branch & Bound | 정확한 최적해 탐색 | 지수 시간 |
| Dynamic Programming | 작은 문제로 나누어 최적화 | 경우에 따라 가능 |
| Genetic Algorithm, Simulated Annealing | 복잡한 스케줄링 문제의 근사해 |
LPT(Largest Processing Time) 알고리즘의 구현 in Java
LPT (Largest Processing Time first) 알고리즘은 머신 스케줄링 문제(Machine Scheduling Problem)에서 작업들을 처리 시간이 긴 순서대로 정렬하여 가장 일찍 가능한 기계에 할당하는 휴리스틱 알고리즘입니다.
즉, 가장 오래 걸리는 작업부터 먼저 처리하되, 가장 비어 있는 머신에 순차적으로 배정하는 방식입니다.
문제 정의
- n개의 작업(Job)이 주어짐
- 각 작업은 처리 시간을 가짐
- m개의 동일한 기계(Machine)에 작업을 나눠서 스케줄링
- 목표: 전체 완료 시간(makespan) 최소화
LPT 알고리즘 동작 방식
- 작업을 처리 시간 기준으로 내림차순 정렬
- 각 작업을 가장 빨리 작업을 끝낼 수 있는 기계에 배정 (최소 부하 우선)
이 방식은 NP-완전 문제의 근사해법으로 많이 쓰이며,
정렬 + 우선순위 큐 구조로 쉽게 구현할 수 있습니다.
구현
import java.util.*;
class Job {
int id;
int time;
Job(int id, int time) {
this.id = id;
this.time = time;
}
}
class Machine {
int id;
int totalTime = 0;
List<Job> assigned = new ArrayList<>();
Machine(int id) {
this.id = id;
}
void assign(Job job) {
assigned.add(job);
totalTime += job.time;
}
}
public class LPTScheduler {
public static List<Machine> scheduleLPT(List<Job> jobs, int machineCount) {
// 1. 작업을 처리 시간 기준으로 내림차순 정렬
jobs.sort((a, b) -> b.time - a.time);
// 2. 머신들을 우선순위 큐로 구성 (처리 시간이 가장 작은 머신이 먼저)
PriorityQueue<Machine> machines = new PriorityQueue<>(Comparator.comparingInt(m -> m.totalTime));
for (int i = 0; i < machineCount; i++) {
machines.add(new Machine(i));
}
// 3. 하나씩 꺼내 가장 유휴한 머신에 배정
for (Job job : jobs) {
Machine machine = machines.poll();
machine.assign(job);
machines.add(machine); // 갱신 후 다시 큐에 추가
}
// 결과 정렬 (id 기준)
List<Machine> result = new ArrayList<>(machines);
result.sort(Comparator.comparingInt(m -> m.id));
return result;
}
public static void main(String[] args) {
List<Job> jobs = List.of(
new Job(0, 6), new Job(1, 2), new Job(2, 8),
new Job(3, 4), new Job(4, 3), new Job(5, 5)
);
int machineCount = 3;
List<Machine> machines = scheduleLPT(jobs, machineCount);
for (Machine m : machines) {
System.out.println("Machine " + m.id + ": Total time = " + m.totalTime);
for (Job job : m.assigned) {
System.out.println(" - Job " + job.id + " (" + job.time + ")");
}
}
}
}Machine 0: Total time = 9
- Job 2 (8)
- Job 4 (3)
Machine 1: Total time = 8
- Job 0 (6)
- Job 1 (2)
Machine 2: Total time = 9
- Job 5 (5)
- Job 3 (4)시간 복잡도 분석
- 정렬: O(n log n)
- 힙에서 머신 꺼내고 삽입: O(log m) → n개 작업 = O(n log m)
총 시간 복잡도: O(n log n + n log m)
LPT의 장점과 한계
| 장점 | 설명 |
|---|---|
| 간단하고 구현 쉬움 | 정렬 + 힙 구조로 직관적 구현 가능 |
| 괜찮은 근사 성능 | 실제 스케줄링 문제에서 실용적인 품질 |
| 적용 범위 넓음 | 데이터센터 작업 분배, 병렬처리, 공장 계획 등 |
| 한계 | 설명 |
|---|---|
| 최적해 보장 X | NP-완전 문제의 휴리스틱 |
| 균형이 어긋날 수 있음 | 극단적인 작업 조합에서는 편향 가능 |
LPT가 최적해가 아닌 예시
- 기계(Machine) 수: 2대
- 작업(Job)과 처리 시간(Processing Time):
- J1: 3
- J2: 3
- J3: 2
- J4: 2
- J5: 2
| 스케줄링 방식 | 기계 1 작업 할당 | 기계 2 작업 할당 | 완료 시간(Makespan) |
|---|---|---|---|
| LPT 알고리즘 | {3, 2, 2} | {3, 2} | 7 |
| 최적해 | {3, 3} | {2, 2, 2} | 6 |
9.7 허프만 코드
허프만 코드(Huffman Code)는 문자나 기호들의 등장 빈도(확률)에 따라 가변 길이의 이진 코드(binary code)를 부여하는 무손실 데이터 압축 알고리즘입니다.
가장 자주 등장하는 문자에는 짧은 코드, 드물게 등장하는 문자에는 긴 코드를 할당하여 전체 평균 비트 수를 최소화합니다.
핵심 요약
| 항목 | 설명 |
|---|---|
| 목적 | 문자열 압축, 평균 코드 길이 최소화 |
| 방식 | 빈도 기반 이진 트리 구성 → 왼쪽 0, 오른쪽 1 |
| 결과 | Prefix-Free Code (접두어 충돌 없음) |
| 시간 복잡도 | O(n log n) (우선순위 큐 기반) |
예시
문자별 등장 빈도:
| 문자 | 빈도 |
|---|---|
| A | 5 |
| B | 9 |
| C | 12 |
| D | 13 |
| E | 16 |
| F | 45 |
허프만 트리 결과:
(*,100)
/ \
F(45) (*,55)
/ \
(*,25) (*,30)
/ \ / \
C(12) D(13) E(16) (*,14)
/ \
A(5) B(9)코드 할당 예:
| 문자 | 허프만 코드 |
|---|---|
| A | 1110 |
| B | 1111 |
| C | 100 |
| D | 101 |
| E | 110 |
| F | 0 |
→ 자주 나오는 F는 짧고, 적게 나오는 A, B는 길다
→ 압축 효율 극대화
허프만 코드의 특징
| 항목 | 설명 |
|---|---|
| 접두어 코드 (prefix code) | 어떤 코드도 다른 코드의 접두어가 아님 (복원 가능) |
| 이진 트리 기반 | 왼쪽 0, 오른쪽 1로 구성 |
| 최적성 | 주어진 빈도에 대해 최적의 평균 비트 수를 보장 |
| 무손실 압축 | 압축 후 원본 복원 100% 가능 |
사용 사례
- ZIP, GZIP 압축
- JPEG, PNG 등 이미지 압축의 일부
- 텍스트 전송 최적화
- 정보 이론, 통신 분야
허프만 코드 프로그램
import java.util.*;
public class HuffmanCoding {
static class Node {
char ch;
int freq;
Node left, right;
Node(char ch, int freq) {
this.ch = ch;
this.freq = freq;
}
Node(int freq, Node left, Node right) {
this.ch = '\0'; // 내부 노드
this.freq = freq;
this.left = left;
this.right = right;
}
boolean isLeaf() {
return (left == null && right == null);
}
}
// 빈도 기반 허프만 트리 생성
static Node buildHuffmanTree(Map<Character, Integer> freqMap) {
PriorityQueue<Node> pq = new PriorityQueue<>(Comparator.comparingInt(n -> n.freq));
for (var entry : freqMap.entrySet()) {
pq.offer(new Node(entry.getKey(), entry.getValue()));
}
while (pq.size() > 1) {
Node n1 = pq.poll();
Node n2 = pq.poll();
pq.offer(new Node(n1.freq + n2.freq, n1, n2));
}
return pq.poll(); // 루트
}
// 코드 매핑 생성
static void buildCodeMap(Node node, String code, Map<Character, String> map) {
if (node == null) return;
if (node.isLeaf()) {
map.put(node.ch, code);
return;
}
buildCodeMap(node.left, code + "0", map);
buildCodeMap(node.right, code + "1", map);
}
// 인코딩
static String encode(String input, Map<Character, String> codeMap) {
StringBuilder sb = new StringBuilder();
for (char ch : input.toCharArray()) {
sb.append(codeMap.get(ch));
}
return sb.toString();
}
// 디코딩
static String decode(String encoded, Node root) {
StringBuilder sb = new StringBuilder();
Node current = root;
for (char bit : encoded.toCharArray()) {
current = (bit == '0') ? current.left : current.right;
if (current.isLeaf()) {
sb.append(current.ch);
current = root;
}
}
return sb.toString();
}
public static void main(String[] args) {
// 문자 빈도 정의 (F:45, E:16, D:13, C:12, B:9, A:5)
Map<Character, Integer> freqMap = Map.of(
'A', 5,
'B', 9,
'C', 12,
'D', 13,
'E', 16,
'F', 45
);
// 트리 생성
Node root = buildHuffmanTree(freqMap);
// 코드 맵 생성
Map<Character, String> codeMap = new HashMap<>();
buildCodeMap(root, "", codeMap);
// 결과 출력
System.out.println("허프만 코드:");
for (var entry : codeMap.entrySet()) {
System.out.println(entry.getKey() + ": " + entry.getValue());
}
// 테스트
String input = "ACDF";
String encoded = encode(input, codeMap);
String decoded = decode(encoded, root);
System.out.println("\n입력: " + input);
System.out.println("인코딩: " + encoded);
System.out.println("디코딩: " + decoded);
}
}
Backend engineer