개요
이 튜토리얼에서는 요소를 삽입할 때마다 K번째로 작은 요소를 찾는 방법을 알아보겠습니다.
이 문제는 최소 힙(min-heap)을 활용하면 효율적으로 해결할 수 있습니다. 최소 힙의 루트에는 항상 가장 작은 값이 위치하기 때문에, 힙의 크기를 K로 유지하면 루트 값이 곧 현재까지 삽입된 요소들 중 K번째로 작은 값이 됩니다.
알고리즘 접근 방식
프로그램을 완성하기 위한 단계는 다음과 같습니다.
- 임의의 데이터로 배열을 초기화합니다.
- 우선순위 큐(priority queue)를 초기화합니다.
- 첫 번째부터 k-1번째 요소까지는 아직 k번째로 작은 요소가 존재하지 않으므로, 원하는 기호(예: '-')를 출력합니다.
- k번째부터 n번째까지 반복하는 루프를 작성합니다.
- 최소 힙의 루트 값을 출력합니다.
- 새로운 요소가 힙의 루트보다 크다면, 루트를 제거(pop)하고 해당 요소를 삽입(push)합니다.
이 방식은 힙의 크기를 항상 k로 유지하므로, 각 삽입 연산의 시간 복잡도는 O(log k)입니다. 전체 시간 복잡도는 O(n log k)가 되어 정렬을 사용하는 O(n log n)보다 효율적입니다.
예제 코드
C++ 코드로 살펴보겠습니다.
#include <bits/stdc++.h>
using namespace std;
void findKthSmallestElement(int elements[], int n, int k) {
priority_queue<int, vector<int>, greater<int>> queue;
for (int i = 0; i < k - 1; i++) {
queue.push(elements[i]);
cout << "- ";
}
queue.push(elements[k-1]);
for (int i = k; i < n; i++) {
cout << queue.top() << " ";
if (elements[i] > queue.top()) {
queue.pop();
queue.push(elements[i]);
}
}
cout << queue.top() << endl;
}
int main() {
int arr[] = {3, 5, 6, 2, 7, 8, 2, 3, 5, 9};
findKthSmallestElement(arr, 10, 5);
return 0;
}코드 설명
priority_queue<int, vector<int>, greater<int>를 사용하여 최소 힙을 생성합니다. C++의 기본 우선순위 큐는 최대 힙이므로,greater<int>비교자를 지정해야 최소 힙으로 동작합니다.- 처음 k-1개의 요소는 힙에 넣기만 하고 '-'를 출력합니다. 이 시점에는 아직 k번째로 작은 요소가 존재하지 않기 때문입니다.
- k번째 요소부터는 힙의 루트(현재 k번째로 작은 값)를 출력하고, 새 요소가 루트보다 크면 교체합니다.
실행 결과
위 코드를 실행하면 다음과 같은 결과를 얻을 수 있습니다.
- - - - 2 3 3 3 5 5
출력을 살펴보면, 처음 4개의 삽입에서는 k=5이므로 아직 5번째로 작은 요소가 없어 '-'가 출력됩니다. 이후 삽입될 때마다 그 시점까지의 5번째로 작은 값인 2, 3, 3, 3, 5, 5가 순서대로 출력되는 것을 확인할 수 있습니다.
마무리
지금까지 최소 힙을 활용해 스트림 데이터가 삽입될 때마다 k번째로 작은 요소를 실시간으로 찾는 방법을 살펴보았습니다. 이 기법은 데이터 스트림 처리나 실시간 통계 계산에 유용하게 활용될 수 있습니다. 튜토리얼에 대해 궁금한 점이 있다면 댓글로 남겨주세요.