알고리즘과 여친 이름

컴퓨터에서 문제를 해결하는 단계와 절차를 기술해 놓은 것을 알고리즘(algorithm)이라고 부른다. 알고리즘이란 용어는 9세기에 활약한 아랍의 수학자인 무하마드 이븐 무사 알콰리즈미(Muhammad ibn Musa Al’Khwarizmi)의 이름에서 유래한 것으로 알려져 있다. 아랍인과 유럽인에게 인도의 기수법을 소개했다고 전해지는 이 수학자의 마지막 이름인 ‘알콰리즈미’에서 ‘알고리즘’이 된 것이다.

 

컴퓨터 알고리즘에 대해 이야기할 때 가장 먼저 떠오르는 사람은 네덜란드의 컴퓨터과학자인 에스커 다익스트라(Edsger W. Dijkstra)이다. 다익스트라는 1930년생으로 29살이 되던 1959년 ‘Numerische Mathematik’이라는 학술지에 ‘A note on two problems in connexion with graphs’라는 3페이지짜리 짧은 논문을 발표하는데, 이 논문은 지금까지 9600번이 넘게 인용되면서 컴퓨터과학 역사상 가장 유명한 논문 중의 하나가 되었다.

 

컴퓨터과학 분야에서 매년 발표되는 수많은 논문 중에서 1000회 넘게 인용된 논문을 찾기가 어려운데, 지금까지 1만회 가까이 인용이 되었다는 것은 그야말로 전설적인 기록이라 할 수 있다. 이 논문에서는 한 지점에서 다른 지점으로 가는 최단 경로를 결정하는 알고리즘을 제안하고 있다.

 

알고리즘을 기하학적 추상화로 표현한 미술작품 ㅣ 출처:경향DB

 

예를 들어 서울에서 출발하여 부산으로 가는 경로가 여러 개 있을 때 그 중에서 어떤 길로 가는 것이 최단 경로인지를 알아내는 것이다. 아이나비와 같은 내비게이션 시스템에서 최단 경로를 결정하는데 사용하는 것이 바로 이 알고리즘이다. 다익스트라는 이러한 공로를 인정받아 1972년 컴퓨터과학 분야의 노벨상이라 할 수 있는 튜링상을 수상하였다.

 

컴퓨터 알고리즘 중에는 사용자가 참을 수 있는 시간 내에 결과를 확인할 수 있는 빠른 알고리즘도 있지만, 아무리 빠른 컴퓨터를 사용하여도 생전에는 결과를 보기 힘든 느린 알고리즘도 있는데, 데이터의 수가 100개만 되어도 살아 있는 동안에는 최종 결과를 확인하기 어려운 문제 중에 대표적인 것이 하노이의 탑이다. 하노이의 탑에 관한 전설을 요약하면 다음과 같다.

 

인도에 있는 한 사원에는 세상의 중심을 나타내는 큰 돔이 있고 그 안에는 세 개의 기둥이 있는데, 기둥 가운데 하나에 신이 가장 큰 원판을 바닥에 놓고 위로 올라갈수록 점점 작아지도록 64개의 순금 원판을 끼워 놓았다고 한다. 신의 지시에 따라 승려들은 모든 원판을 다른 기둥으로 옮기기 위해 밤낮 없이 일하는데, 원판을 이동하는 규칙은 원판을 한 번에 하나씩만 옮겨야 하며, 큰 원판을 작은 원판 위에 올려놓으면 안 된다는 것이다. 승려들이 모든 원판을 다른 기둥으로 옮기는 날 탑은 무너지고 세상은 종말을 맞이하게 된다고 한다.

 

일반적으로 원판의 개수를 n이라고 했을 때 정확히 2n-1번 만에 모든 원판을 옮길 수 있다. 필자의 집에는 8개의 원판을 가지고 있는 하노이의 탑이 있는데, 8개의 원판을 모두 옮기기 위해서는 28이 256이므로 최소 255번의 이동이 필요하게 된다. 그러면 64개의 원판을 모두 옮기기 위해서는 얼마 정도의 시간이 필요할까? 계산에 따르면 64개의 원판을 모두 옮기기 위해서는 약 1844경6744조번의 이동이 필요하고, 한번 옮길 때 시간을 1초로 가정하면 약 5849억4241만년이 걸린다고 한다. 이 정도의 시간이 흐른다면 전설에서 이야기하는 것처럼 세상은 종말을 맞이하지 않을까?

 

다른 과학 분야와 마찬가지로 컴퓨터과학 분야에서도 알고리즘의 이름을 지을 때 개발자의 이름을 따서 짓는 경우가 많이 있다. 예를 들어, 한글이나 워드와 같은 문서 편집기에서 사용자가 찾고 싶은 문자열을 찾을 때 사용하는 문자열 탐색 알고리즘의 경우 개발자의 이름을 따서 Knuth-Morris-Pratt 알고리즘이나 Boyer-Moore 알고리즘 등으로 부르고 있다. 그런데 알고리즘을 공부하던 중 개발자의 이름을 따서 짓지 않은 것으로 보이는 특이한 알고리즘을 하나 알게 되었는데, 패트리샤(Patricia)라는 알고리즘이 바로 그것이다. 이 알고리즘은 Practical Algorithm To Retrieve Information Coded In Alphanumeric의 약자라고 하는데, 이 이름을 보면 패트리샤라는 이름을 먼저 지어 놓고 나중에 억지로 끼워 맞춘 것 같은 느낌이 강하게 든다.

 

필자는 이 이름을 볼 때마다 알고리즘 개발자가 자신의 여자 친구 이름을 붙인 것이 아닌지 의심하곤 하는데, 심증은 가지만 확실한 물증은 없다. 그렇기는 하지만 만일 필자의 추측대로 이것이 사실이라면 딱딱하고 어렵기만 한 컴퓨터 알고리즘의 역사에서 재미있고 유쾌한 일화가 될 것이다. 필자는 지금도 강의 시간에 이 부분을 설명할 때마다 패트리샤라는 예쁜 이름을 가진 여자 친구가 어떤 모습이었을지 상상하며 미소 짓곤 한다.