CS 기초·알고리즘
가장 가까운 K개 장소
수만 개 장소의 id와 좌표(위도·경도)가 있습니다. 사용자의 현재 위치가 주어지면 가장 가까운 10개 장소를 찾아 그 중심 좌표를 돌려주는 함수를 설계해 주세요. 어떤 알고리즘과 자료구조를 쓰고 복잡도는 얼마인가요?
면접관은 이 답을 어떻게 들을까요? 넘어갈지, 더 물어볼지, 떨어뜨릴지 알려 주고, 걸리는 문장은 콕 집어 줘요. 점수는 그대로예요.
짧은 답 보기
n개 전부에 대해 거리를 계산하며 크기 10의 최대 힙을 유지하면 O(n log k), 공간 O(k). 한 번이면 quickselect로 O(n)도 가능하다. 거리는 위경도를 그대로 유클리드로 쓰지 말고 haversine이나 위도 보정 근사를 쓴다.