백준 문제풀이(파이썬)/우선순위 큐

중간값을 찾는 문제이다. 매번 입력을 받을 때마다 지금까지 입력받은 수들의 중간값을 출력해주면 된다. 정렬을 한 뒤 중간 index의 값을 출력해주면 되겠지만, 입력 값이 100,000개이기 때문에, O(n^2)의 시간 복잡도를 생각하면 시간 초과가 뜰 것이다. 이번 단계가 우선순위 큐인 만큼 힙을 이용해야한다. 예를 들어 11개의 원소가 있고, 그 중 중간값의 특징을 생각해보자. 11개를 오름차순으로 정렬한다고 할 때 중간값을 포함한 왼쪽 6개중에서 중간값은 그들중에서 최댓값일 것이고, 오른쪽 5개의 원소들의 최솟값보다 작을 것이다. 짝수개일때도 마찬가지로, 만약 10개라고 가정한다면, 중간값을 포함한 왼쪽 5개중에서 최댓값이고, 오른쪽 5개의 원소들의 최솟값보다 작을 것이다. 꼭 정렬을 하여 최소 최..

11279번 문제는 최대 힙, 1927번 문제는 최소 힙을 이용하여 각각 최댓값, 최솟값을 구하는 문제이다. 두 문제 모두 등호만 다를 뿐 코드는 같기 때문에, 더 어려울 수 있는 최소 힙을 풀겠다. 그전에 힙에 대해 알아보자. 힙이란, 우선순위 큐를 위한 자료구조이자, 다른 알고리즘에 비해 최댓값, 최솟값을 빠르게 구하게 해준다. 또한 힙은 반 정렬 상태이다. 처음에 우선순위 큐와 힙에 대해서 혼동이 왔었다. 내가 알던 큐는 처음에 들어온 것이 제일 먼저 나가는 FIFO형태였는데, 우선순위에 따라 먼저 나간다는 개념이 낯설었다. 힙은 우선순위 큐를 구현하기 위한 도구(?)이고, 또한 힙은 반 정렬 상태라는 것을 알고 나니 이해가 됐다. 반 정렬 상태라는 건 트리안의 모든 수가 정렬이 되어있는 것이 아니..