크기가 n인 배열이 주어졌을 때, 카운팅 정렬(counting sort) 기법을 활용하면 중앙값(median)과 최빈값(mode)을 효율적으로 구할 수 있습니다. 이 방법은 배열 원소의 값 범위가 제한적일 때 특히 유용합니다. 예를 들어 배열이 {1, 1, 1, 2, 7, 1}이라면 가장 자주 등장하는 값인 1이 최빈값이 됩니다.
중앙값과 최빈값이란?
- 중앙값(Median): 숫자들을 오름차순으로 정렬했을 때 정확히 가운데에 위치하는 값입니다.
- 최빈값(Mode): 데이터 목록에서 등장 횟수가 가장 많은 값입니다.
알고리즘 접근 방법
- 입력 배열의 크기를 n이라고 가정합니다.
- 각 값의 등장 횟수를 저장하는 카운트 배열을 만듭니다. 누적 합을 계산하기 전 상태에서 카운트가 가장 큰 인덱스가 곧 최빈값입니다.
- 최대 빈도를 가진 값이 여러 개라면 그중 하나를 선택해도 됩니다.
- 선택한 값을 별도의 변수 mode에 저장합니다.
- 이후 일반적인 카운팅 정렬 과정(카운트 배열의 누적 합 계산과 원소 배치)을 그대로 진행합니다.
- 정렬된 배열에서 n이 홀수이면 가운데 원소 하나가 중앙값이고, n이 짝수이면 가운데 두 원소의 평균이 중앙값입니다.
- 계산된 값을 별도의 변수 median에 저장합니다.
C++ 구현 예제
#include <iostream>
#include <vector>
using namespace std;
const int MAX_VAL = 100; // 원소 값의 범위: 0 ~ 99
void findMedianAndMode(int arr[], int n) {
int count[MAX_VAL] = {0};
// 1단계: 각 원소의 등장 횟수 카운트
for (int i = 0; i < n; i++)
count[arr[i]]++;
// 2단계: 누적 합 계산 전에 최빈값(mode) 결정
int maxCount = 0, mode = 0;
for (int i = 0; i < MAX_VAL; i++) {
if (count[i] > maxCount) {
maxCount = count[i];
mode = i;
}
}
// 3단계: 누적 합 계산으로 카운팅 정렬 준비
for (int i = 1; i < MAX_VAL; i++)
count[i] += count[i - 1];
// 4단계: 뒤에서부터 원소를 배치해 정렬된 배열 생성
vector<int> sorted(n);
for (int i = n - 1; i >= 0; i--)
sorted[--count[arr[i]]] = arr[i];
// 5단계: 중앙값(median) 계산
double median;
if (n % 2 == 1)
median = sorted[n / 2];
else
median = (sorted[n / 2 - 1] + sorted[n / 2]) / 2.0;
cout << "Mode: " << mode << endl;
cout << "Median: " << median << endl;
}
int main() {
int arr[] = {1, 2, 2, 3, 4, 5};
int n = sizeof(arr) / sizeof(arr[0]);
findMedianAndMode(arr, n);
return 0;
}출력 결과
Mode: 2
Median: 2.5동작 설명
입력 배열 {1, 2, 2, 3, 4, 5}에서 값 2가 두 번 등장하므로 최빈값은 2입니다. 정렬 결과는 {1, 2, 2, 3, 4, 5}이며, 원소 개수가 6개(짝수)이므로 가운데 두 원소인 2와 3의 평균 2.5가 중앙값이 됩니다.
시간 복잡도
이 방법의 시간 복잡도는 O(n + k)이며, k는 원소 값의 범위 크기입니다. 공간 복잡도 역시 O(k)로, 값의 분포 범위가 좁을 때 일반적인 정렬 기반 방법보다 훨씬 효율적으로 중앙값과 최빈값을 얻을 수 있습니다.