절대 차이의 최소 합계가 있는 배열 요소?

여기서 우리는 한 가지 흥미로운 문제를 보게 될 것입니다. N개의 요소가 있는 하나의 배열 ''을 가져옵니다. |a[0] - x|와 같은 요소 x를 찾아야 합니다. + |a[1] - x|+ ... + |a[n-1] - x| 최소화됩니다. 그런 다음 최소화된 합계를 찾아야 합니다.

배열을 {1, 3, 9, 6, 3}이라고 합시다. 이제 x는 3입니다. 따라서 합계는 |1 - 3|입니다. + |3 - 3| + |9 - 3| + |6 - 3| + |3 - 3| =11.

이 문제를 해결하려면 배열의 중앙값을 x로 선택해야 합니다. 배열 크기가 짝수이면 두 개의 중앙값이 있습니다. 둘 다 x의 최적의 선택이 될 것입니다.

알고리즘

최소합(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

예시

#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