[코테 유형별로 씹어먹기]우선순위 큐 어떤 문제에 사용될까?

개념

우선순위 큐는 항상 최소 / 최대 값이 가장 맨 앞에 오도록 하는 자료구조이다.

우선순위 큐의 내부는 힙이라는 자료구조로, 완전 이진 트리의 일종이다.

그에 따라 우선순위 큐에서 값의 삭제 및 삽입의 시간 복잡도가 LogN이다.

그럼 PS에서 우선순위 큐가 필요한 경우에 대해서 생각해보자,

자료구조의 특성을 생각해보면 우선순위 큐가 필요한 상황은 값의 삽입과 삭제가 빈번하게 일어나는 경우이다.

예시

만약 10만개의 원소가 있는 배열에서 아래와 같은 문제들을 푼다고 해보자.

1. 원소의 삽입 연산만 10만번 혹은 가장 작은/큰 값 삭제 연산만 10만번 주어진다. 연산 후의 가장 작은 값/ 가장 큰 값을 출력해라

만약 삽입만 일어나거나 삭제만 일어나는 경우에는 가장 작은 값, 가장 큰 값만 알고 있으면 된다. 이 경우에 가장 작은 값 / 큰 값은 기존의 가장 작은/ 큰값만 비교하면 되고, 삭제하는 경우에는 정렬해준 뒤 하나씩 삭제해주면 된다.

총 삽입의 경우 총 시간복잡도는 배열의 크기가 N이고, 연산 횟수가 Q이면 정렬 + 출력만 해주면 되므로 O(NlogN+Q)이다.

2. 원소의 삽입 혹은 가장 작은/큰 값삭제 연산이 10만번 주어진다. 연산 후 가장 작은 / 큰 값을 출력해라

매번 정렬해주기로 해보자, 일단 삭제는 마찬가지로 O(1)이다. 그 이유는 우리는 필요한 값을 정렬시켜놓았기 때문에 삭제해야할 위치를 알고 있다.

일단 간단하게 생각해서 새로운 값을 아무곳이나 넣어준 뒤 정렬해주는 방법이다. 이 경우에는 매번 삽입 될 때 마다 배열을 정렬해주므로 총 시간복잡도는 O(QNlogN)이다. N과 Q 모두 10만이므로 이 경우 시간초과가 뜰 것이다.

일단 여기서 더 줄일 수 있다. 이미 기존에 정렬되어있던 배열이라면 정렬 되어있는 곳에 해당 값이 들어갈 위치를 찾는 것이다. 위치를 찾는 것 자체는 O(N)으로 가능하다. i번째 원소를 a(i)라 했을 때, a(i), 넣으려는 값, a(i+1) 인 곳을 찾으면 되는 것이다 배열을 새로 만드는 것도 O(N)으로 가능하다. 이 경우에 O(QN) 일 것이다. 하지만 여전히 너무나 큰 숫자이다.

이럴 때 사용하는 것이, 우선순위 큐이다. 힙은 이진트리의 일종으로 항상 루트는 최소/최대 값을 유지한다. 삭제 연산의 시간 복잡도가 logN이 되기는 하지만, 삽입 또한 logN이 될 것이다. 이유는 완전 이진트리의 특성을 이해하고 있으면 된다.

맨 처음 우선순위큐에 다 넣는 시간복잡도NlogN에 삽입/삭제가 동일하게 logN이므로 이 경우에는 O(NlogN+QlogN)이다.