정렬된 두 배열의 중앙값 구하기 – C++ 분할 정복 알고리즘

중앙값(median)은 자료를 크기순으로 정렬했을 때 정확히 가운데에 위치하는 값을 의미합니다. 즉, 전체 데이터의 누적 백분율 50% 지점에 해당하는 관측치라고 할 수 있습니다.

이 알고리즘은 두 배열의 크기가 같다(n1 = n2)는 전제 조건을 필요로 합니다. 기본 아이디어는 각 배열의 중앙값을 먼저 구한 뒤, 두 중앙값을 서로 비교하면서 탐색 범위를 절반씩 줄여 나가 최종적으로 두 리스트 전체의 실제 중앙값을 찾는 것입니다.

입력 및 출력

입력:
크기가 같은 정렬된 두 배열이 주어집니다.
배열 1: {1, 2, 3, 6, 7}
배열 2: {4, 6, 8, 10, 11}

출력:
두 배열로부터 구한 중앙값. 이 예제에서 중앙값은 6입니다.
두 리스트를 하나로 병합하면 {1, 2, 3, 4, 6, 6, 7, 8, 10, 11}이 됩니다.
병합된 리스트에서 가운데 두 원소의 평균을 구하면 (6 + 6) / 2 = 6입니다.

알고리즘

median(list, n)

입력: 데이터 목록과 데이터의 개수 n

출력: 주어진 목록의 중앙값

시작
    만약 목록의 데이터 개수가 짝수라면
        (list[n/2] + list[n/2 - 1]) / 2를 반환
    아니면 (홀수 개라면)
        list[n/2]를 반환
종료

findMedian(list1, list2, n)

입력: 정렬된 두 개의 리스트와 리스트의 크기 n

출력: 두 정렬된 리스트의 중앙값

시작
    만약 n <= 0이면
        유효하지 않은 입력이므로 오류 값 반환
    만약 n = 1이면
        (list1[0] + list2[0]) / 2를 반환
    만약 n = 2이면
        ((max(list1[0], list2[0])) + (min(list1[1], list2[1]))) / 2를 반환

    med1 := median(list1, n)   // 첫 번째 배열의 중앙값
    med2 := median(list2, n)   // 두 번째 배열의 중앙값

    만약 med1 = med2이면
        med1을 반환   // 두 중앙값이 같으면 그것이 곧 전체 중앙값
    만약 med1 < med2이면
        만약 n이 짝수이면
            list1의 n/2 - 1 인덱스 이후 부분으로 findMedian(list1 + n/2 - 1, list2, n - n/2 + 1)을 재귀 호출
        list1의 n/2 인덱스 이후 부분으로 findMedian(list1 + n/2, list2, n - n/2)을 재귀 호출
    // med1 > med2인 경우에는 list1과 list2의 역할을 바꾸어 동일하게 수행
종료

핵심 원리는 다음과 같습니다. 두 배열의 중앙값을 비교했을 때, 전체 중앙값은 반드시 작은 중앙값과 큰 중앙값 사이에 존재합니다. 따라서 med1 < med2라면 첫 번째 배열의 앞쪽 절반과 두 번째 배열의 뒤쪽 절반에는 정답이 없으므로 이들을 제거하고, 남은 부분에 대해 같은 과정을 재귀적으로 반복하면 됩니다.

예제 코드 (C++)

#include<iostream>
using namespace std;

int median(int list[], int n) {
    if (n % 2 == 0)      // 배열에 짝수 개의 데이터가 있을 때
        return (list[n/2] + list[n/2 - 1]) / 2;
    else                 // 홀수 개의 데이터일 때
        return list[n/2];
}

int findMedian(int list1[], int list2[], int n) {
    if (n <= 0)
        return -1;       // 리스트 길이가 유효하지 않음
    if (n == 1)
        return (list1[0] + list2[0]) / 2;   // 원소가 하나씩이면 두 값의 평균 반환
    if (n == 2)
        return (max(list1[0], list2[0]) + min(list1[1], list2[1])) / 2;

    int med1 = median(list1, n);   // 첫 번째 배열의 중앙값 계산
    int med2 = median(list2, n);   // 두 번째 배열의 중앙값 계산

    if (med1 == med2)              // 두 중앙값이 같으면 그것이 최종 중앙값
        return med1;
    if (med1 < med2) {
        if (n % 2 == 0)
            return findMedian(list1 + n/2 - 1, list2, n - n/2 + 1);
        return findMedian(list1 + n/2, list2, n - n/2);
    }

    if (n % 2 == 0)                // med1 > med2인 경우
        return findMedian(list2 + n/2 - 1, list1, n - n/2 + 1);
    return findMedian(list2 + n/2, list1, n - n/2);
}

int main() {
    int list1[] = {1, 2, 3, 6, 7};
    int list2[] = {4, 6, 8, 10, 11};

    int n1 = 5;
    int n2 = 5;

    if (n1 == n2)
        cout << "Median is " << findMedian(list1, list2, n1);
    else
        cout << "Doesn't work for lists of unequal size";
}

실행 결과

Median is 6

시간 복잡도

매 재귀 호출마다 탐색 대상 원소의 개수가 절반으로 줄어들기 때문에, 이 알고리즘의 시간 복잡도는 O(log n)입니다. 두 배열을 실제로 병합한 뒤 중앙값을 찾는 단순한 방식(O(n))에 비해 훨씬 효율적이며, 배열의 크기가 클수록 그 차이가 더욱 커집니다.