우선순위 큐

(C++) 백준 1715번 - 카드 정렬하기

문제 링크 : https://www.acmicpc.net/problem/1715 1715번: 카드 정렬하기 정렬된 두 묶음의 숫자 카드가 있다고 하자. 각 묶음의 카드의 수를 A, B라 하면 보통 두 묶음을 합쳐서 하나로 만드는 데에는 A+B 번의 비교를 해야 한다. 이를테면, 20장의 숫자 카드 묶음과 30장 www.acmicpc.net 풀이 우선순위 큐와 그리디 알고리즘을 사용하여 풀이하였다. 카드 비교 횟수를 최소화하려면 가장 개수가 적은 두 묶음씩 먼저 합치면서 진행하면 된다. 최소 힙을 사용해서 가장 갯수가 적은 묶음 두 개를 합친 후, 다시 이를 최소 힙에 넣고 앞의 과정을 반복하는 방식으로 풀이하였다. #include #include using namespace std; int n, tota..

(C++) 백준 11286번 - 절대값 힙

문제 링크 : https://www.acmicpc.net/problem/11286 11286번: 절댓값 힙 첫째 줄에 연산의 개수 N(1≤N≤100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 0이 아니라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0 www.acmicpc.net 풀이 우선순위 큐와 커스텀 비교 함수를 사용하여 풀이하였다. 우선순위 큐에서는 가장 뒤에 위치한 값이 가장 우선순위가 높다는 것이 풀이하면서 상당히 헷갈리게 만들었다. 또한 우선순위 큐에서 비교 함수를 사용하기 위해서 아래와 같이 cmp라는 클래스와 내부의 operator()를 사용해야 한다는 사실도 새롭게 알게 되었다. #include #include usin..

(C++) 우선순위 큐(Priority Queue)

우선순위 큐란? 우선순위를 가지는 데이터들을 저장하는 큐(Queue)를 말한다. 데이터를 꺼낼 때 우선순위가 높은 데이터가 가장 먼저 나온다는 특징이 있어 운영체제의 작업 스케줄링, 정렬, 네트워크 관리 등의 다양한 기술에 적용되고 있다. 우리가 흔히 말하는 큐(Queue)와의 차이는 일반적인 큐는 아래 그림과 같이 선형적인 구조를 가지는 반면 우선순위 큐는 트리 구조로 생각할 수 있다. 우선순위 큐의 동작 원리 일반적으로 우선순위 큐는 최대 힙(Max Heap)을 이용해 구현한다. 그래서 우선순위 큐의 동작 원리를 알아보기 전에 먼저 최대 힙에 대해 알아보자. 최대 힙은 부모 노드가 자식 노드 보다 값이 큰 완전 이진트리를 의미한다. 그렇기에 루트 노드는 전체 트리에서 가장 큰 값을 가진다. 이제 우선..