이 글에서는 n개의 숫자로 구성된 집합 S가 주어졌을 때, S의 중앙값(Median)에 가장 가까운 k개의 숫자를 찾는 C++ 프로그램을 소개합니다.
핵심 아이디어는 간단합니다. 먼저 퀵 정렬(Quick Sort)을 사용해 데이터를 오름차순으로 정렬한 뒤, 중앙값을 기준으로 왼쪽과 오른쪽 요소를 비교하여 중앙값에 더 가까운 요소부터 차례대로 선택하는 방식입니다. 데이터 개수가 홀수이면 가운데 하나의 값이 중앙값이 되고, 짝수이면 가운데 두 값의 평균이 중앙값이 됩니다.
알고리즘
시작 partition() 함수 — high 위치의 값을 피벗(pivot)으로 삼아 배열을 분할: 매개변수: a[] = 배열 l = low (낮은 인덱스) h = high (높은 인덱스) 함수 본문: 변수 pivot, in, i 선언 in = l 로 초기화 pivot = h 로 설정 i를 l부터 h-1까지 반복 만약 a[i] < a[pivot]이면 a[i]와 a[in]을 교환 in 값을 1 증가 a[pivot]과 a[in]을 교환 in 반환 끝 시작 QuickSort() 함수 — 퀵 정렬 알고리즘으로 데이터 요소를 정렬: 매개변수: a[] = 배열 l = low h = high 함수 본문: pindex 선언 만약 l < h이면 index = Partition(a, l, h) QuickSort(a, l, pindex-1) 호출 QuickSort(a, pindex+1, h) 호출 0 반환 끝 시작 main() 함수, 데이터 요소 개수가 홀수라면: 가운데 인덱스를 low로, 그다음 인덱스를 high로 지정한 뒤 중앙값 계산 k번 반복하면서 중앙값에 더 가까운 요소를 출력 그렇지 않다면(짝수): 중앙값은 가운데 두 값의 평균이 됨 k번 반복하면서 중앙값에 더 가까운 요소를 출력 끝
예제 코드
#include<iostream>
using namespace std;
void swap(int *x, int *y) { // 두 값 교환
int tmp;
tmp = *x;
*x = *y;
*y = tmp;
}
int Partition(int a[], int l, int h) {
int pivot, in, i;
in = l;
pivot = h;
for(i=l; i < h; i++) {
if(a[i] < a[pivot]) {
swap(&a[i], &a[in]);
in++;
}
}
swap(&a[pivot], &a[in]);
return in;
}
int QuickSort(int a[], int l, int h) {
int pindex;
if(l < h) {
pindex = Partition(a, l, h);
QuickSort(a, l, pindex-1);
QuickSort(a, pindex+1, h);
}
return 0;
}
int main() {
int n, i, h, l, k;
double d1,d2, median;
cout<<"데이터셋의 요소 개수 입력: ";
cin>>n;
int a[n];
for(i = 0; i < n; i++) {
cout<<"\n"<<i+1<<"번째 요소 입력: ";
cin>>a[i];
}
cout<<"\n중앙값에 가장 가까운 요소의 개수(k) 입력: ";
cin>>k;
QuickSort(a, 0, n-1);
cout<<"중앙값에 가장 가까운 k개의 요소: ";
if(n%2 == 1) { // 요소 개수가 홀수인 경우
median = a[n/2];
h = n/2+1;
l= n/2;
while(k > 0) {
if((median-a[l] <= a[h]-median) && l >= 0) {
cout<<" "<<a[l];
l--;
k--;
} else if((median-a[l] > a[h]-median) && h <= n-1) {
cout<<" "<<a[h];
h++;
k--;
}
}
} else { // 요소 개수가 짝수인 경우
d1 = a[n/2];
d2 = a[n/2-1];
median = (d1+d2)/2; // 가운데 두 값의 평균이 중앙값
h = n/2;
l = n/2-1;
while(k > 0) {
d1 = a[l];
d2 = a[h];
if((median-d2 <= d1-median) && l >= 0) {
cout<<" "<<a[l];
l--;
k--;
} else if((median-d2 > d1-median) && h <= n-1) {
cout<<" "<<a[h];
h++;
k--;
}
}
}
return 0;
}실행 결과
데이터셋의 요소 개수 입력: 7 1번째 요소 입력: 7 2번째 요소 입력: 6 3번째 요소 입력: 5 4번째 요소 입력: 4 5번째 요소 입력: 3 6번째 요소 입력: 2 7번째 요소 입력: 1 중앙값에 가장 가까운 요소의 개수(k) 입력: 2 중앙값에 가장 가까운 k개의 요소: 4 3
위 실행 결과에서 입력된 데이터 {7, 6, 5, 4, 3, 2, 1}을 정렬하면 {1, 2, 3, 4, 5, 6, 7}이 되고, 중앙값은 4입니다. 여기서 k=2이므로 중앙값에 가장 가까운 두 개의 요소인 4와 3이 출력됩니다.