여러 좌표 점(집들의 위치)이 담긴 리스트가 주어졌다고 가정해 봅시다. 이때 모든 집에서 서비스 센터까지의 유클리드 거리(Euclidean distance)의 합이 최소가 되도록 센터를 (xc, yc)에 설치하려면, 그 최소 거리의 합을 구하는 것이 문제입니다.
예를 들어 입력이 positions = [(10,11),(11,10),(11,12),(12,11)]이라면, 출력은 4.0이 됩니다.
문제 해결 접근 방식: 삼분 탐색(Ternary Search)
거리의 합 함수는 볼록(convex)한 성질을 가지므로, x축과 y축 각각에 대해 삼분 탐색을 적용하면 최솟값을 효율적으로 찾을 수 있습니다. 전체 알고리즘은 다음과 같습니다.
- 반복 횟수 numIter := 50으로 설정합니다.
- total(cx, cy, positions) 함수: 중심점 (cx, cy)와 각 점 사이의 유클리드 거리를 모두 더한 값을 반환합니다.
- fy(x, positions) 함수: x좌표를 고정한 상태에서 y에 대해 삼분 탐색을 수행하여 최소 거리 합을 구합니다.
- fx(positions) 함수: x에 대해 삼분 탐색을 수행하며, 각 단계에서 fy()를 호출해 y 방향의 최솟값을 활용합니다.
삼분 탐색의 동작 원리
탐색 범위 [l, r] 내에서 두 개의 분할점 y1 = l + (r − l) / 3, y2 = r − (r − l) / 3을 정하고, 각 지점에서의 거리 합 t1, t2를 비교합니다.
- t1 < t2이면 최솟값은 왼쪽 구간에 있으므로 r := y2로 범위를 축소합니다.
- 그렇지 않으면 l := y1로 범위를 축소합니다.
이 과정을 50회 반복하면 탐색 범위가 충분히 좁혀져 매우 정확한 최솟값을 얻을 수 있습니다. 메인 메서드에서는 fx(positions)를 호출해 결과를 반환합니다.
구현 예제 코드
from math import sqrt
def solve(points):
numIter = 50
def total(cx, cy, positions):
total = 0.0
for p in positions:
x, y = p
total += sqrt((cx - x) * (cx - x) + (cy - y) * (cy - y))
return total
def fy(x, positions):
l, r = 0, 101
res = 0
for i in range(numIter):
y1 = l + (r - l) / 3
y2 = r - (r - l) / 3
t1 = total(x, y1, positions)
t2 = total(x, y2, positions)
res = min(t1, t2)
if t1 < t2:
r = y2
else:
l = y1
return res
def fx(positions):
l, r = 0, 101
res = 0
for i in range(numIter):
x1 = l + (r - l) / 3
x2 = r - (r - l) / 3
t1 = fy(x1, positions)
t2 = fy(x2, positions)
res = min(t1, t2)
if t1 < t2:
r = x2
else:
l = x1
return res
return fx(positions)
positions = [(10,11),(11,10),(11,12),(12,11)]
print(solve(positions))입력
[(10,11),(11,10),(11,12),(12,11)]
출력
4.0
정리
이 문제는 기하학에서 잘 알려진 기하 중앙값(Geometric Median) 문제와 유사합니다. 삼분 탐색을 x와 y 두 축에 중첩해서 적용하면 미분 없이도 볼록 함수의 최솟값을 근사적으로 구할 수 있으며, 반복 횟수를 늘릴수록 정밀도가 향상됩니다. 시간 복잡도는 O(numIter² × n)으로, 점의 개수가 많지 않다면 실용적인 속도로 동작합니다.