1. 우선순위 큐와 힙 내용 정리
● 우선순위 큐 (Priority Queue)
- 우선순위를 가진 항목들을 저장하는 큐
- 우선 순위가 높은 데이터가 먼저 나가게 됨
- 가장 일반적인 큐라고 할 수 있으며, 스택이나 큐를 우선순위 큐로 구현할 수 있음
- 시뮬레이션, 네트워크 트래픽 제어, OS의 작업 스케쥴링 등을 하는데 사용됨
- 우선순위 큐 연산
1) insert(item) : 우선순위 큐에 항목 item을 추가
2) remove() : 우선순위 큐로부터 가장 우선순위가 높은 요소를 삭제하고 이 요소를 반환
3) find() : 우선순위가 가장 높은 요소를 삭제하지 않고 반환
4) isEmpty() : 우선순위 큐가 공백 상태인지를 검사
5) isFull() : 우선순위 큐가 포화상태인지를 검사
6) display() : 우선순위 큐의 모든 요소들을 출력
- 우선순위 큐는 두가지로 구분: 최소 우선순위 큐, 최대 우선순위 큐
- 우선순위 큐 구현 방법: 배열을 통한 구현, 연결리스트를 통한 구현, 힙(heap)을 이용한 구현
- 우선순위 큐 구현 방법 비교 표:
● 힙 (Heap)
- 완전이진트리 형태 (더미)
- 우선순위 큐를 구현하기 위해 만들어진 자료구조
- 일종의 반 정렬 상태를 유지
- 최대 힙(max heap): 부모 노드의 키값이 자식 노드의 키값보다 크거나 같은 완전 이진 트리
- 최소 힙(min heap): 부모 노드의 키값이 자식 노드의 키값보다 작거나 같은 완전 이진 트리
- 힙의 높이: n개의 노드를 가지고 있는 힙의 높이는 O(logn), 마지막 레벨을 제외하고 각 레벨 i 에 (2의 i제곱 - 1)개의 노드가 존재
- 힙은 보통 배열을 이용하여 구현, 각 노드에 배열을 인덱스를 1부터 붙임
- 부모노드와 자식노드의 관계
1) 왼쪽 자식의 인덱스 = (부모의 인덱스) * 2
2) 오른쪽 자식의 인덱스 = (부모의 인덱스) * 2 + 1
3) 부모의 인덱스 = (자식의 인덱스) / 2
2. C++을 이용한 우선순위 큐 프로그래밍 방법
1) 힙 노드 클래스를 만든다.
class HeapNode {
int형의 key 값을 멤버변수로 선언
생성자를 통해 클래스 선언 시 key 값도 함께 저장되도록 함
key 값을 변경할 수 있는 setkey 함수를 선언
key 값을 가져올 수 있는 getkey 함수를 선언
key값을 출력해주는 display 함수를 선언
};
2) 최대 힙 클래스를 만든다.
HeapNode 클래스를 #include받아옴
class MaxHeap {
HeapNode node[MAX_ELEMENT]를 통해 힙 노드 클래스를 생성하도록 함
int형의 size 값을 멤버변수로 선언
생성자 생성
isEmpty, isFull함수를 통해 MaxHeap의 size를 반환받을 수 있도록 함
힙에서 부모노드, 왼쪽 자식노드, 오른쪽 자식노드를 반환받을 수 있도록함
heap에 insert, remove 할 수 있는 함수를 생성
};
3) 최대 힙 클래스에 삽입함수와 삭제함수를 구현한다.
- 삽입함수: 힙에 키값 key를 갖는 새로운 요소를 삽입
void insert ( int key ) {
힙이 가득찬 경우는 더이상 insert되지 않도록 return
++size를 통해 하나 증가한 상태에서 힙을 추가할 수 있도록 함
while문을 통해 트리를 거슬러 올라가며 부모노드와 비교해 부모보다 키값이 크면 부모와 값을 바꿔 위로 올라감
};
- 삭제함수
HeapNode remove ( ) {
힙이 비어있는 경우는 더이상 remove되지 않도록 return
마지막노드를 루트노드로 올린 후, while문을 통해 루트노드에서부터 자식노드와 비교해
자식보다 키값이 작으면 자식과 값을 바꿔 아래로 내려감
원래 루트노드에 있던 값을 반환
};
4) main 함수에서 Maxheap heap; 코드를 통해 최대 힙 클래스를 만든 후,
insert, remove, display 등의 함수를 사용하며 원하는 계산을 실행한다.
3. 문제 풀이
3.1 백준 1966번 - 프린터 큐
1) case_number을 입력받는다.
2) for문을 case_number번 반복하며 코드를 실행한다.
- n과 m을 입력받는다.
- queue에 입력되는 순서(first)와 n개의 입력값(second)을 pair로 묶어 저장한다.
- priority_queue (우선순위 큐)에 n개의 입력값을 저장한다.
- while문을 queue가 비어있을 때까지 반복한다.
queue의 제일 앞에 있는 수를 pop한다.
if-> 우선순위 큐의 값과 queue의 값(second)이 일치한다면
우선순위 값을 pop하고 count도 하나 증가시켜준 후,
queue에 입력되는 순서값(first)과 m이 같다면 count값을 출력한 후 반복문을 종료한다.
else-> queue의 제일 앞에 있는 수가 제일 큰 수가 아니라면 다시 뒤로 push한다.
3.2 백준 1655번 - 가운데를 말해요
1) t를 입력받는다.
2) 우선순위 큐를 선언한다.
(최댓값이 top에 있는 최대힙과 최솟값이 top에 있는 최소힙 두 개를 선언)
=> 최대힙과 최소힙에 값을 넣을 땐 두가지 조건이 있음
1. 최대힙의 크기는 항상 최소합의 크기보다 같거나 1만큼 더 크다.
2. 최소힙의 모든 원소는 최대힙의 모든 원소보다 항상 같거나 커야한다.
3) while문을 t번 반복하며 말해야하는 값을 출력한다.
- a를 입력받는다.
- 최대힙과 최소힙의 크기가 같다면 max(최대 힙)에 a를 저장한다.
그렇지 않다면 min(최소 힙)에 a를 저장한다.
- 최대힙의 top값이 최소힙의 top값보다 크다면 두 값을 swap한다.
- max (최대 힙)의 top에 있는 값을 출력한 후 다시 while문을 반복한다.
(max (최대 힙)의 top에 있는 값이 중간값이거나 가장 작은 수임 == 말해야하는 수임)
(+ 이미지 출처: DATA STRUCTURES USING C++ PPT Chapter 10 우선순위 큐)
'자료구조실습 수업' 카테고리의 다른 글
| [9주차 과제] (0) | 2022.11.06 |
|---|---|
| [MID] 중간 프로젝트 (0) | 2022.10.16 |
| [4주차 과제] (0) | 2022.10.02 |
| [3주차 과제] (0) | 2022.09.25 |
| [1주차 과제] 리포트 요약 과제 (0) | 2022.09.12 |