[박형주의 과학에세이] 어느 젊은이의 20분

위성을 통해서 지구상의 내 위치를 파악한다는 개념은 군사적 목적에서 시작됐다. 1960년대 미국은 TRANSIT이라는 인공위성 위치추적 시스템을 운용했다. 이걸 민간 영역에서 사용하게 된 계기는 269명의 민간인이 사망한 1983년의 대한항공 007기 격추 사건이었다. 항공기 위치 파악 오류 탓에 옛소련 영공으로 진입했다는 정황 증거가 나오자, 당시 레이건 미국 대통령은 미국이 보유한 GPS 인공위성의 정보를 제한적으로 민간에게 무료로 공개하게 했다. 민간 사용 시에는 인위적인 혼선 신호를 더해 위치 정확도에 제한을 걸었지만, 2000년에 클린턴 대통령의 지시로 이 제한이 사라지면서 본격적인 민간의 GPS 사용이 시작됐다.

상업적으로 처음 판매된 GPS 수신기는 1989년 마젤란사(社)의 제품이다. 제한적인 GPS 신호를 수신해 대강의 위치를 파악하는 수준이었지만 가격은 2900달러에 달했다. 차량에 설치해 목적지까지 가는 방법을 가르쳐주는 차량 내비게이션은 1995년 GM이 처음 도입했다. 2000달러의 유상 옵션이었는데도 엉뚱한 길을 알려주곤 해서 불평도 많았다.

인공위성을 통해 내 위치를 알게 됐는데, 이걸 이용해 목표 지점까지 이동하는 경로를 찾는 건 왜 이리 힘들까. 10개의 도시가 이리저리 연결되어 있는 지도만 해도 한 도시에서 다른 도시로 가는 경로가 한둘이 아니다. ‘최단 경로 문제’로 불리는 이 문제를 풀려면, 가능한 경로를 모두 비교해 가장 빠른 경로를 찾아야 한다. 도시 숫자가 늘면 슈퍼컴퓨터로도 다 비교하지 못할 정도로 많은 경로가 출현한다. 이걸 어떻게 다 비교한단 말인가. 수학자들이 NP 문제라고 부르는, 계산이 몹시 어려운 문제다.

다행히도 답은 네덜란드의 수학자이자 전산학자인 에츠허르 데이크스트라(Edsger W. Dijkstra)가 1959년 출간한 논문에 이미 있었다. 지도상의 한 점에서 다른 점으로 가는 최단 경로를 찾는 빠른 알고리즘이다. 구글 지도는, 조금 돌아가는 길이라도 신속하게 찾는 걸 더 중시하는 방식으로 데이크스트라 알고리즘을 변형한 A* 방식을 사용한다.

데이크스트라는 젊은 시절에 잠시 생각해 얻은 이 결과가 자신의 가장 유명한 업적이 된 것을 신기해했다. 사람들은 그가 나중에 내놓은 심오한 연구 결과보다 이 결과만을 기억했으니까. 1956년 20대의 젊은이였던 그는 카페에서 커피를 마시며 이 문제를 생각했는데, 마침 펜과 종이가 없었다. 복잡한 계산을 할 수 없자 간단한 방법만 생각하다가 20분쯤 걸려서 답을 구했다.

이제는 구글 지도부터 스마트폰의 내비게이션 앱까지 이 방식 또는 그 변형을 사용한다. 아무리 많은 GPS 위성을 쏘고 내 위치를 정확하게 알아도, 26세 젊은이의 그 20분이 없었더라면, 오늘 대전에서 서울까지 어떤 경로로 가야 가장 빠를지 몰랐을 것이다.

“가장 단순한 방법을 생각해야만 하는 상황이 되면 그렇게 되더라”라고 말한 데이크스트라를 믿어볼까. 앞으로 정말 중요한 문제를 생각할 때는 종이와 연필을 치워야겠다.