1980년대 미국 애틀랜타에 '밀스 온 휠스(Meals on Wheels)'라는 단체가 있었어요. 거동이 불편한 어르신들께 매일 도시락을 배달하는 자원봉사 단체인데요. 배달 지점이 200곳이 넘다 보니 경로를 어떻게 짜느냐가 큰 고민이었어요. 문제는 이 단체에 컴퓨터가 없었다는 거예요. 예산도 빠듯하고, 배달 대상자 명단은 계속 바뀌고요. 조지아텍의 존 바솔디(John Bartholdi) 교수가 이 문제를 풀었는데, 그 해법이 놀랍게도 '회전식 명함 정리함 두 개'였어요. 그리고 그 뒤에는 공간채움곡선(spacefilling curve)이라는 아름다운 수학이 숨어 있고요.
공간채움곡선이 뭐냐면요
한붓그리기로 정사각형 안을 빈틈없이 채우는 곡선이에요. 힐베르트 곡선(Hilbert curve)이 유명한데, 선을 재귀적으로 접고 또 접는 걸 극한까지 반복하면 평면의 모든 점을 지나가게 되거든요. 그러니까 0에서 1 사이의 숫자 하나가 평면 위의 한 점에 대응되는 거예요. 2차원 공간을 1차원 직선으로 '펴는' 방법인 셈이죠.
핵심 성질은 이거예요. 곡선 위에서 가까운 두 숫자는 평면에서도 가까운 두 점이 돼요. 이걸 지역성(locality)이라고 하는데요. 이 성질을 뒤집어 쓰면 강력한 도구가 돼요. 평면 위의 점들 각각에 '너는 곡선의 몇 번째쯤에 있니?'라는 값을 매겨서 그 값 순서로 정렬하면, 공간적으로 가까운 점들이 대체로 이웃하게 줄을 서게 되거든요.
외판원 문제를 정렬 한 번으로
이게 바로 순회 외판원 문제(TSP), 그러니까 '여러 지점을 최단 거리로 도는 경로 찾기'의 초고속 근사 해법이 돼요. 배달 지점 각각의 곡선상 위치값을 계산하고, 그 값으로 정렬해서, 그 순서대로 방문하면 끝이에요. 계산 복잡도는 정렬 비용인 O(n log n)이 전부고요. 바솔디 교수의 분석에 따르면 이렇게 만든 경로는 최적 경로보다 평균 25%쯤 길어요. 정교한 솔버에 비하면 투박하지만, 대신 얻는 게 엄청나요.
첫째, 미친 듯이 빨라요. 둘째, 배달 지점이 추가되거나 빠져도 정렬된 목록에 카드 한 장 끼워 넣거나 빼면 끝이에요. 경로 전체를 다시 계산할 필요가 없어요. 셋째, 컴퓨터가 아예 필요 없어요. 밀스 온 휠스에서는 각 주소의 곡선 위치값을 읽을 수 있는 지도를 만들어두고, 주소 카드마다 그 값을 적어서 명함 정리함에 순서대로 꽂았어요. 오늘 배달 갈 곳들의 카드를 앞에서부터 뽑으면 그게 곧 배달 경로인 거죠. 정리함이 두 개인 건 하나는 현재 운영용, 하나는 명단 갱신 작업용이었고요. 자원봉사자 누구나 유지보수할 수 있는, 말 그대로 '알고리즘의 물리적 구현'이었던 거예요.
40년이 지난 지금, 이 아이디어는 어디에나 있어요
이 발상이 요즘 어디에 쓰이냐면, 사실 여러분이 매일 쓰는 인프라 곳곳에 있어요. 지리 좌표를 짧은 문자열로 인코딩하는 지오해시(geohash)는 Z-order 곡선(힐베르트 곡선의 사촌)에 기반하고, 레디스(Redis)의 GEO 명령어가 바로 이걸 써요. 구글의 S2 라이브러리는 힐베르트 곡선으로 지구 표면을 인덱싱해서 지도 서비스들을 떠받치고 있고요. 분산 데이터베이스에서 다차원 데이터를 파티션 키 하나로 뭉갤 때도, GPU가 텍스처를 메모리에 배치하면서 캐시 효율을 높일 때도 같은 원리가 쓰여요. '가까운 것들을 가깝게 저장한다'는 문제는 어디에나 있으니까요.
경로 최적화 자체는 물론 구글 OR-Tools나 LKH 같은 솔버가 훨씬 좋은 해를 내요. 하지만 그런 솔버에 넣을 초기해를 빠르게 만들거나, 실시간으로 주문이 추가되는 상황에서 즉석 대응해야 할 때는 여전히 공간채움곡선 정렬이 훌륭한 첫수가 돼요.
한국 개발자에게는요
배달·물류 서비스가 유독 발달한 한국에서는 특히 와닿는 이야기인데요. 라이더 배차나 픽업 동선 문제에서 '완벽한 최적화'에 매달리기 전에, 힐베르트 정렬 같은 단순한 휴리스틱으로 기준선을 잡아보는 접근은 지금도 유효해요. 위치 기반 서비스를 만든다면 geohash나 S2를 쓰는 순간 이미 이 수학의 수혜자가 되는 거고요. 무엇보다 이 이야기의 진짜 교훈은 이거예요. 좋은 엔지니어링은 이론상 최고의 해를 찾는 게 아니라, 주어진 제약 안에서 충분히 좋은 해를 찾는 일이라는 것. 컴퓨터도 없는 자원봉사 단체라는 제약이 오히려 40년을 살아남은 우아한 해법을 낳았잖아요.
한줄 정리: 2차원을 1차원으로 펴는 곡선 하나면 경로 문제가 정렬 문제로 바뀐다 — 단순함이 곧 힘이라는 걸 보여주는 고전이에요. 여러분도 '정교한 알고리즘보다 단순한 휴리스틱이 이긴' 경험이 있다면 들려주세요!
🔗 출처: Hacker News