1. 우선순위큐와 힙 정리

미리 알아두기

그래프 : 그래프는 간선과 정점으로 이루어져있다 * 간선 = 객체(노드)끼리 이어지는 것
트리 = 사이클을 이루지 않는 그래프
층수(level) : 맨끝에 있는 애들 = leaf node, 노드 맨 처음 애 = root node
모든 층에서 가지 2개씩 = 포화/완전 이진트리
다 두개씩인데 하나가 빠져있다 = 거의 완전 이진트리
왼쪽부터 봤는데 비어있다 = 불완전 이진트리

우선순위큐란?

우선순위가 높은 데이터부터 먼저 나가는 자료구조

element(요소), key(key값이 높을 수록 먼저 나옴), 집합 S로 구성

먼저 들어온 데이터가 먼저 나가는 구조인 큐와 달리 우선 순위가 높은 데이터가 먼저 나간다

스택과 큐와 개념이 비슷한데 차이점이 있다
스택 : 늦게 들어온 데이터가 먼저 나간다(후입선출, LIFO)
큐: 먼저 들어온 데이터가 먼저 나간다(선입선출, FIFO)

우선순위 큐는 이진 트리로 표현된다

아래는 우선순위 큐를 표현하는데 사용할 수 있는 연산들이다

insert(S,x) :S에 x 추가한다
max(S) : S요소 중에서 key가 가장 큰 요소를 알려준다
extract_max(S):S값에서 가장 큰 요소를 pop한다
increase_key(S,x,k) : x요소의 키값을 k만큼 증가시킨다

heap이란?

우선순위 큐를 푸는데 가장 좋은 알고리즘

heap의 성질 2가지

1.거의 완전 이진트리이다
2.모든 요소가 key를 갖고,부모 노드의 key값이 자식 노드의 key값보다 크거나 같다

왼쪽 자식 노드 index를 구하고 싶을 때 : 부모 노드 index x 2
오른쪽 자식 노드 index를 구하고 싶을 때 : 부모 노드 index x 2 + 1
부모 노드 index를 구하고 싶을 때 : 자식 노드 index / 2

최대 힙(max heap) : key(부모노드) ≥key(자식노드)
이진 트리에서 루트가 가장 큰 값을 가진다
max heap은 내림차순으로 정렬된다
통상적으로 최대 힙이 자주 사용된다

최소 힙(min heap) : key(부모노드) ≤key(자식노드)
이진 트리에서 루트가 가장 작은 값을 가진다
min heap은 오름차순으로 정렬된다

2. C++를 이용한 우선순위큐 프로그래밍 방법

우선순위 큐를 구현하는데에는 세가지 방법이 있다

배열

정렬되지 않은 배열-> 기존의 요소들 뒤에 삽입하고자 하는 요소를 삽입한다

정렬된 배열-> 기존의 요소들과 우선순위를 비교하여 삽입 위치를 찾고 해당 위치 이후의 요소들은 하나씩 뒤로 옮긴 후 삽입한다

연결 리스트

정렬되지 않은 연결 리스트-> '정렬되지 않은 배열' 처럼 기존의 요소들 뒤에 삽입하고자 하는 요소를 삽입한다

정렬된 연결 리스트-> 포인터를 이용해 우선순위가 높은 요소를 찾고 첫번째 노드가 되도록 만든다

힙

삽입 연산(upheap)
1. 힙에 새로운 요소가 들어 오면, 일단 새로운 노드를 heap의 마지막 노드에 이어서 삽입한다
2. 삽입 후에 새로운 노드를 부모 노드들과 교환해서 힙의 성질을 만족하게 한다

삭제 연산(downheap)
최대힙에서의 삭제 ➔ 항상 루트가 삭제된다(가장 큰 키값을 가진 노드를 삭제하는 것)
1. 루트 삭제 후 가장 마지막 노드를 루트 위치로 옮긴다
2. 루트에서부터 단말노드까지의 경로에 있는 노드들을 교환하여 히프 성질을 만족하게 한다

그 중 배열을 이용한 구현을 해보면

위의 코드를 출력해보면 우선 순위가 가장 높은 5가 출력이 된다.

3. 문제풀이

3-1. 백준 1966번 - 프린터 큐

3-2. 백준 1655번 - 가운데를 말해요

코드에도 써놨지만 cin.tie(0), cout.tie(0) 은 버퍼 관련 명령어이다. 입력(cin)과 출력(cout)을 번갈아가면서 사용할 때 순서가 꼬여 문제가 발생하는 것을 방지해 준다
ios::sync_with_stdio는 cpp의 iostream을 c의 stdio와 동기화시켜주는 역할로 속도가 빨라지게 해준다