모든 좌표까지 맨해튼 거리 합이 최소가 되는 위치를 구하는 방법

1. 모든 점까지 맨해튼 거리의 합이 최소가 되는 점의 위치? m차원의 n개의 점들 $P_{1}(x_{11},x_{12},...,x_{1m}), ... P_{n}(x_{n1},x_{n2},...,x_{nm})$에 대하여, 이들까지 맨해튼 거리의 합이 최소가 되는 점 X의 좌표를 구하라고 한다면, 어떻게 구할 수 있을까? 정답은 n개의 점들을 1,2,...,m차원의 좌표 값에 대하여 정렬한 다음, 중앙값에 해당하는 점의 좌표 $P_{median}$이 된다. 직관적으로 쉽게 눈치챌 수 있기는 한데, 왜 그런지 생각해보자. 2. 증명 먼저 점들의 좌표가 합에 서로 영향을 주지 않는다는 점을 관찰하자. 예를 들어 (3,5), (4,2), (5,1)에 대하여 (x,y)까지 맨해튼 거리의 합은.. $|x-3| + ..