배열 요소와의 절대 차이 합을 최소화하는 값 x 찾기

이번 글에서는 흥미로운 알고리즘 문제를 하나 살펴보겠습니다. N개의 요소를 가진 배열 'a'가 주어졌을 때, |a[0] - x| + |a[1] - x| + ... + |a[n-1] - x| 의 값을 최소화하는 요소 x를 찾고, 그 최소화된 합계를 구하는 것이 목표입니다.

예를 들어 배열이 {1, 3, 9, 6, 3}이라면 x는 3이 됩니다. 이때 합계는 다음과 같이 계산됩니다.
|1 - 3| + |3 - 3| + |9 - 3| + |6 - 3| + |3 - 3| = 11

이 문제의 핵심은 배열의 중앙값(median)을 x로 선택하는 것입니다. 중앙값은 모든 요소와의 절대 거리 합을 수학적으로 최소로 만드는 지점이기 때문입니다. 만약 배열의 크기가 짝수라면 두 개의 중앙값이 존재하는데, 어느 쪽을 선택하더라도 최적의 결과를 얻을 수 있습니다.

알고리즘

문제 해결 절차는 매우 간단합니다. 먼저 배열을 오름차순으로 정렬한 뒤 중앙값을 구하고, 각 요소와 중앙값 사이의 절대 차이를 모두 더하면 됩니다.

minSum(arr, n)

begin
    sort array arr
    sum := 0
    med := median of arr
    for each element e in arr, do
        sum := sum + |e - med|
    done
    return sum
end

C++ 구현 예제

다음은 위 알고리즘을 C++로 구현한 코드입니다. 정렬에는 표준 라이브러리의 sort 함수를 사용하며, 시간 복잡도는 정렬에 의해 결정되어 O(N log N)입니다.

#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;
int minSum(int arr[], int n){
    sort(arr, arr + n);
    int sum = 0;
    int med = arr[n/2];
    for(int i = 0; i<n; i++){
        sum += abs(arr[i] - med);
    }
    return sum;
}
int main() {
    int arr[5] = {1, 3, 9, 6, 3};
    int n = 5;
    cout << "Sum : " << minSum(arr, n);
}

실행 결과

Sum : 11

배열 {1, 3, 9, 6, 3}을 정렬하면 {1, 3, 3, 6, 9}가 되고, 중앙값은 arr[5/2], 즉 arr[2]인 3입니다. 각 요소와 3 사이의 절대 차이를 모두 더하면 2 + 0 + 0 + 3 + 6 = 11로, 앞서 계산한 결과와 일치합니다.