[PS] 중앙값
중앙값
- n개의 값을 정렬했을 때 $\frac{1}{2}$ 위치에 해당하는 값
- 홀수일 경우 $\frac{1}{2}$ , 짝수일 경우 $\frac{1}{2}$ 위치에 해당하는 값과 $\frac{1}{2}$ + 1 에 해당하는 값을 더하고 2로 나눠준다.
1. $n$개의 점과의 거리의 합이 최소가 되는 위치 $x$ 찾기
결론 : $ x = a_{\frac{n}{2}} $
- $n$ 이 홀수일 경우
중앙값을 기준으로 왼쪽에 있는 ( 중앙값보다 작은 값 ) 수의 개수를 $K$ 개라고 하자. $n$ 이 홀수라면 중앙값을 기준으로 왼쪽에 있는 수와 오른쪽에 있는 수의 개수는 같다. 따라서 오른쪽에 있는 수의 개수도 $K$ 개 이다.
$x =\frac{1}{2}$ 번째 수라고 두자.
예를 들어 $n = 5$ 이고, 수가 $ 100, 200, 300, 400, 500$ 이면 $x = \frac{5}{2} = 2 $ 이므로, $300$ 이다. (배열의 index는 0부터 시작하므로 0번째가 100이고 4번째가 500이다. 분수의 0.5 는 버림한다.)
값 x를 기준으로 왼쪽에 있는 수, 중앙값, 오른쪽에 있는 수는 아래와 같다.
Left : $ a_1, a_2, a_3… a_{\frac{n}{2} - 1} $
Middle : $ a_{\frac{n}{2}} $
Right : $ a_{\frac{n}{2} + 1}, … a_{n} $
여기서 $x$ 의 값을 $d$ 증가시키면, Left와 의 Middle의 모든 값들은 $x$와 거리가 $d$씩 증가하고, Right의 모든 값들은 거리가 $d$씩 감소한다.
Left, Middle : $ (K+1) \times d $ 증가
Right : $ K \times d $ 감소
원래의 총 거리가 $D_{sum}$ 이라면 결과적으로 아래와 같이 거리가 변한다. \(D_{sum} = D_{sum} + (K+1) \times d - K \times d = D_{sum} + d\)
따라서 거리가 원래 거리보다 무조건 $d$ 만큼 증가한다. 같은 방식으로 $x$를 $d$감소시켜도 거리가 증가함을 보일 수 있다.
- $n$ 이 짝수일 경우
$n$ 이 짝수라면 두 수 $ a_{\frac{n}{2} - 1}, a_{\frac{n}{2}} $ 를 통해 중앙값을 계산할 것이다.
( index = 0 부터 시작하는 배열을 기준으로 한다. )
여기서 $a_{\frac{n}{2} - 1}$ 보다 작은 수의 개수를 K개라고 두면, $a_{\frac{n}{2}}$ 보다 큰 수의 개수도 K개이다. 이 두 집합은 $ K_{1}, K_{2} $ 라고 하자.
다음으로 $x$의 위치를 아래와 같이 두자.
\(a_{\frac{n}{2} - 1} \leq x \leq a_{\frac{n}{2}}\)
홀수일 때와 마찬가지로 x의 값을 d만큼 변화시키면 집합 $ K_{1}, K_{2} $ 는 같은 크기 만큼 변하기 때문에 상쇄된다.
또한 $ a_{\frac{n}{2} - 1} $ 와 $ a_{\frac{n}{2}} $ 도 서로 d만큼 변하기 때문에 상쇄된다.
따라서 $x$ 의 범위는 $a_{\frac{n}{2} - 1} \leq x \leq a_{\frac{n}{2}}$ 이 된다.
결과적으로 1과 2에 따라 x = $a_{\frac{n}{2}}$ 로 두면 $n$ 개의 점과의 거리의 합이 최소가 된다.