Algorithm Find a minimum distance in the array

알고리듬 Find a minimum distance in the array를 알아보겠습니다.

배열 안에서 어떤 지점에서 원소들 간의 거리가 최소인 경우를 알아봅시다.
1, 3, 9, 13, 105
이런 배열이 있다면 가장 최소가 되는 지점은 중앙값(Median)입니다.
위의 값은 9를 기점으로 각 원소의 거리를 측정하면 가장 짧습니다.

114가 가장 짧은 거리입니다.

만약 짝수 일 때는 어떻게 될까요?

가운데 양옆의 값의 평균을 구합니다. 그게 중앙값이 됩니다.

6이 중앙값이 되고, 거리는 18이 최소가 됩니다.

한 가지 재미있는 것은, 3~9 사이에 아무 값을 넣어도 거리는 최소라는 겁니다.

그 이유는 바로 6이 중앙값이지만, 3과 9 사이에 값들은 3 하고 가까워지면 동일하게 9에서 멀어지므로 값이 유지되고, 반대로 9와 가까워지면, 3 하고 멀어지면서 동일하게 유지됩니다.

코드로 봅시다.

3 번째 줄에서 중앙값을 구합니다.

끝.

카테고리: Algorithm