모르는 길 앞에서 스마트폰을 켜는 것은 이제 본능에 가까운 일상이 되었다. 보이지 않는 위성이 내 위치를 속삭여주고, 복잡한 알고리즘이 최적의 경로를 그려낸다. 하지만 이 편리함의 이면에는 냉전 시대의 비극과 한 천재 수학자가 커피 한 잔을 마시며 써내려간 20분의 직관이 숨어 있다. 길 찾기의 설움을 기술의 축복으로 바꾼 수학사의 드라마라고 할 만하다.

예전의 ‘길치’들은 여러 번 간 길도 기억하지 못해 집 근처만 맴도는 설움을 겪곤 했지만, 목적지만 입력하면 손바닥 안의 지도가 길을 인도하는 시대가 도래하자 모든 게 바뀌었다. 요즘의 젊은이들은 ‘길을 헤맨다’는 말을 아예 이해하지 못한다.

이러한 시대가 오기까지는 두 가지 기술의 진보가 필요했다. 하드웨어 측면에서는 지구상의 내 위치를 위성으로 파악하는 GPS 기술이 등장했고, 소프트웨어 측면에서는 내 위치에서 목적지까지 가는 가장 빠른 경로를 파악하는 수학 알고리즘이 출현했다.

지구상의 내 위치를 위성으로 파악하는 기술은 본래 군사적 목적으로 탄생했다. 1960년대 미국은 ‘트랜싯(TRANSIT)’이라는 위치추적 시스템을 군사적 목적으로 운용 중이었다. 이 기술이 민간에 개방된 계기는 역설적이게도 269명의 소중한 목숨을 앗아간 1983년 ‘대한항공 007기 격추 사건’이었다. 민간 항공기가 소련 영공에 진입한 것이 항로 착오 때문이었다는 정황이 드러나자, 당시 로널드 레이건 미국 대통령은 이런 비극의 재발을 막기 위해 GPS 정보를 민간에게 무료로 공개하기로 결단했다.

수조개의 경로 중 딱 하나를 찾는 법

군사 목적의 보안 필요 등으로 초기에는 정확도를 떨어뜨리는 인위적 혼선 신호(SA)를 섞었으나, 2000년 빌 클린턴 대통령이 이를 제거하면서 본격적인 민간 GPS 시대가 열렸다. 1989년 마젤란사가 내놓은 최초의 상업용 GPS 수신기는 2900달러라는 거금에도 성능은 미비했고, 1995년 GM이 도입한 초기 차량 내비게이션 역시 2000달러의 고가 옵션이었음에도 엉뚱한 길을 알려주기 일쑤였다.

초기 GM 내비게이션의 난항은, 내 위치를 아는 것이 해결되었더라도 목적지까지 가는 최선의 길을 찾는 것은 전혀 다른 차원의 문제이기 때문이다. 이미 1950년대에 수학적으로 해결되었던 문제이지만, 오랫동안 잊힌 상태였다.

단순히 도시 10개가 복잡하게 얽힌 지도만 보더라도, 출발지에서 목적지까지 가는 경로는 기하급수적으로 늘어난다. 수학자들이 흔히 ‘여행하는 외판원 문제’라고 부르는 이 최단 경로 문제는 가능한 모든 경로를 일일이 비교해야 하는데, 도시 수가 조금만 늘어나도 슈퍼컴퓨터조차 계산 불능에 빠지는 이른바 ‘조합 폭발’이 일어난다.

택배회사가 전국 도처에 물류창고를 구축할 때도, 고객의 주문 패턴을 모은 빅데이터를 가지고 총 배달 소요 시간을 최소화하는 배치를 결정해야 하는데, 이것도 유사한 복잡도를 갖는 난해한 문제이다. 이처럼 계산 복잡도가 몹시 높은 어려운 문제를 수학에서는 흔히 ‘NP 문제’의 범주에서 다룬다.

다행히 인류에게는 에츠허르 데이크스트라라는 선구자가 있었다. 1956년, 26세의 젊은 전산학자였던 그는 카페에서 커피를 마시다 이 문제에 몰입했다. 마침 수중에 펜과 종이가 없었던 것이 오히려 신의 한 수였다. 복잡한 수식을 쓸 수 없게 되자 그는 가장 단순하고 직관적인 논리 구조를 고민했고, 단 20분 만에 그 유명한 ‘데이크스트라 알고리즘’을 창안했다.

단순함이 이긴 복잡함의 미학

데이크스트라의 해법은 현재 위치에서 가장 가까운 지점부터 차례로 탐색하며 최단 거리를 확정 짓는 방식이다. 모든 경로를 비교하지 않지만 최적의 가까운 경로를 빠르게 찾아내는 이 알고리즘은 1959년 논문으로 세상에 나왔고, 훗날 구글 지도는 이 방식을 변형해 목적지 방향으로의 탐색 효율을 높인 ‘A*(A-star) 알고리즘’을 통해 우리에게 실시간 경로를 제공하고 있다.

정작 데이크스트라 자신은 훗날 내놓은 수많은 심오한 연구 결과보다, 젊은 시절 잠시 생각해서 얻은 이 결과가 자신의 가장 위대한 업적으로 기억되는 것을 신기해했다. 하지만 그의 직관이 없었다면, 아무리 많은 GPS 위성을 쏘아 올렸어도 우리는 오늘 수원 월드컵경기장에서 대전시청까지 가는 가장 빠른 길을 찾지 못하고 있을 것이다.

박형주 아주대 수학과 석좌교수