2.5.2 연습 문제 10: 중앙값 구하기

이번 연습 문제에서는 머신 러닝(machine learning), 데이터 분석 응용 프로그램에서 접할 수 있는 문제를 풀어보려고 합니다. 어떤 소스로부터 한 번에 하나의 데이터를 연속적으로 받는다고 가정합시다. 그리고 매번 데이터를 받을 때마다 지금까지 받은 데이터의 중앙값(median)²을 계산해야 한다고 가정하겠습니다. 간단한 방법은 매번 데이터를 받을 때마다 모든 데이터를 정렬하고, 그 중 가운데 원소를 반환하는 것입니다. 그러나 이러한 작업은 정렬 연산 때문에 O(N log N)의 시간 복잡도를 갖습니다. 들어오는 데이터양이 늘어날수록 이 방식은 매우 많은 리소스를 사용하게 됩니다. 여기서는 힙을 이용하여 최적화하는 방법을 알아보겠습니다.

  1. 먼저 필요한 헤더 파일을 포함합니다.

#include <iostream>
#include <queue>
#include <vector>

  2. 현재까지 받은 데이터를 저장할 컨테이너를 정의하겠습니다. 여기서는 두 개의 힙을 사용하여 데이터를 저장할 것입니다. 하나는 최대 힙이고, 다른 하나는 최소 힙입니다. 새로 들어오는 데이터가 기존 데이터의 중앙값보다 작으면 최대 힙에 저장하고, 크면 최소 힙에 저장할 것입니다. 이런 방식을 사용하면 두 힙의 최상단 원소를 이용하여 중앙값을 계산할 수 있게 됩니다.

struct median
{
    std::priority_queue<int> maxHeap;
    std::priority_queue<int, std::vector<int>, std::greater<int>> minHeap;