02. 도서관에서의 정리 문제
<알고리즘 행성 여행자들을 위한 안내서>
일상의 지혜 속에는 우리가 생각하는 것보다 훨씬 더 많은 알고리즘이 숨어 있다. 그런데 일상의 지혜에 모든 걸 맡겨두고 손 놓고 그냥 가만히 있기만 해도 된다면, 이렇게 굳이 알고리즘에 대해 설명할 필요가 뭐 있겠는가? 사실 일상의 지혜는 지나치게 세밀하다.
당신과 함께 살던 친구가 이사를 갔다. 그 친구는 성격이 좋긴 하지만 정리하는 데는 젬병이다. 당신은 아무렇게 꽂혀 있는 책들을 정리하려고 한다. 이 책들을 어떻게 분류해서 정리해야 할까? 책 분류에 적용할 수 있는 일상의 지혜가 있을까?
사진: pakutaso.com
이렇게 해보면 어떨까? 일단 책을 모두 책장 앞바닥에 놓는다. 그런 다음 책장에서 제일 위쪽 제일 왼쪽에 꽂아야 할 책, 이른바 ‘첫 번째 책’을 찾는다. 찾은 책을 책장에 꽂은 후, 바닥에 놓여 있는 책 중에서 다시 그다음에 꽂을 ‘첫 번째 책’을 찾는다. 이런 식으로 계속 반복한다. 책을 꽂을 때마다 현재 바닥에 남아 있는 책에서 ‘첫 번째 책’을 찾아야 한다. 그런데 찾는 시점에 ‘첫 번째 책’을 찾으려면, 모든 책을 일일이 다시 살펴봐야 한다. 즉, 책을 분류하면서 하나씩 꽂을 때마다 남아 있는 모든 책을 한 번씩 살펴봐야 하는 것이다. 책이 500권이면, 첫 번째 책을 선택하기 위해 499번을 비교하고, 두 번째 책을 위해 498번을 비교하고…… 이렇게 해서 대충 250 곱하기 500번을 비교해야 한다. 만약 (고스란히 다 비교해서) 500 곱하기 500번이라고 하면 무려 총 25만번을 비교해야 한다. 이 경우, 절반을 처리하고 이제 절반밖에 안 남았더라도 당신은 아마 미쳐버릴 지경일 것이다.
당신은 이 방법보다 다음과 같은 방법을 더 선호할 수도 있다. 일단 책을 모두 책장에 꽂는다. 순서에 상관없이 아무렇게나 꽂으면 된다. 그런 다음 제일 뒤쪽(맨 아래, 맨 오른쪽)에서부터 나란히 꽂혀 있는 책 두 권의 순서가 잘못돼 있으면 그 두 권의 순서를 바꾼다. 이런 식으로 책 500권을 한 번만 쭉 다 훑는다. 이 방법은 물론 첫 번째 방법보다 쉽기는 하지만, 이것만으론 책이 잘 분류되었다고 하기 어렵다. 이제 두 번째로 다시 뒤쪽부터 동일한 작업을 하고, 그런 다음에 또 한 번, 또 한 번 실시한다. 이런 식으로 500번 정도 하면 대충 분류가 끝날 것이다. 이렇게 하는 과정에서 책들이 샤워기에서 솟구치는 물거품처럼 책장 위쪽으로 끓어오르는 듯한 상황이 연출된다. 이 때문에 이 방법은 ‘버블 정렬(bubble sort)’이라고 불린다. 책 500권의 버블 정렬 비용도 역시 500 곱하기 500 정도이다.
이것 말고도 분류 알고리즘은 많다. 어떤 것들은 실용적이고, 어떤 것들은 번거롭다. 앞에서 소개한 두 가지 분류 방법은 후자에 속한다. 분류를 위한 아주 좋은 방법으로 다음과 같은 것이 있다. 일단 아무 데서나 시작한다. 알고리즘에 관한 책 한 권을 찾아낼 때까지, 먼저 제목이 ‘A’로 시작되는 책들만 계속 주시한다. 그런 다음 이제 그 책을 읽기 시작한다. 어떻게 신속하게 분류할 수 있는지 알게 될 때까지 말이다. 일단 책을 읽은 다음에는 버블 정렬보다 더 빨리 분류할 수 있을 것이다.
가장 실용적인 분류 방법 중 하나를 소개하겠다. 일단, 당신이 이사를 하는 것뿐만 아니라 누군가와 함께 살려고 한다고 가정해보자. 당신과 상대는 각자 엇비슷한 양의 책을 가지고 있다. 합쳐서 500권쯤 된다. 두 사람은 제목 순서대로 잘 정리해놓은 각자의 책들을 책장 앞바닥에 쌓아놓았다. 이렇게 분류되어 있는 책 두 무더기를 어떻게 합쳐야 할까?
[왼쪽부터]언제나 뒤에서 앞으로 진행해 나가면서 인접한 두 데이터를 정렬한다(버블 정렬). 아니면 이미 분류되어 있는 두 개의 데이터를 하나로 합칠 수도 있다(병합 정렬).
당신은 당신 쪽에 있는 책 무더기에서 첫 번째 책을 집어 든다. 이 책의 제목을 ‘아헨 여행안내서(Aachen. Ein Reiseführer)’라고 하자. 그리고 상대방의 첫 번째 책 제목은 ‘글래디에이터 아스테릭스(Asterix als Gladiator)’라고 하자. 이제 어떤 책을 책장 맨 위의 칸 제일 왼쪽에 두어야 할지 비교한다. 이 경우에는 제목이 ‘A’로 시작하는 ‘아헨 여행안내서’일 것이다. 이 책을 책장 맨 위의 칸 가장 왼쪽에 꽂는다. 이제 이 책의 위치는 제대로 설정됐다. 당신 쪽의 책 무더기에서 가장 위쪽에 있던 이 책이 알파벳 순서상 ‘글래디에이터 아스테릭스’보다 앞서기 때문이다. 즉, 당신의 새로운 동거인이 가지고 온 다른 모든 책들보다도 그 책이 더 앞선다는 뜻이다. ‘글래디에이터 아스테릭스’가 몇 번째로 꽂힐지는 아직 모르지만, 다만 아직까진 당신의 동거인이 쌓아놓은 책 무더기의 가장 위쪽에 얹혀 있게 된다.
이제 똑같은 과정을 다시 한 번 반복한다. 바닥에 쌓인 책 무더기들의 첫 번째 책 두 권을 비교하는 것이다. 이번에 당신 쪽 책 무더기의 첫 번째 책 제목은 ‘아헨의 또 다른 여행안내서(Aachen. Noch ein Reiseführer)’이다. 이 책이 두 번째로 책장에 꽂히고, ‘글래디에이터 아스테릭스’는 상대방 책 무더기의 맨 위쪽에 계속 그대로 얹혀 있게 된다. 세 번째에는 이 책이 책장에 꽂힐 수도 있다. 이런 식으로 계속해 나간다. 언젠가는 한쪽 책 무더기가 없어질 것이고, 남은 무더기의 책은 원래 분류되어 있는 상태 그대로 꽂히게 될 것이다. 그리 어렵게 들리지 않는다. 실제로도 어려운 일은 아니다.
거의 모든 알고리즘이 이처럼 단순하다. 문제는 이 단순한 알고리즘 가운데 어떤 것이 잘 먹히느냐 하는 것이다. 두 무더기의 책을 합치는 일에 얼마나 많은 힘과 노력을 쏟아부을 것인가? 책장에 책을 하나씩 꽂을 때마다 당신은 최대 한 번 비교를 해야 한다. 즉, 책이 500권이면 최대 500번 비교해야 한다. 이보다 더 간단하게 되지는 않을 것이다.
이미 분류되어 있는 두 개의 데이터를 합치는 일은 그다지 어렵지 않다. 다만, 우리가 어떻게 사전에 두 무더기로 분류할 것인가 하는 문제가 남는다. 이때 해결사 단어는 바로 ‘시키는 것’이다. 가령 누군가가 도서관을 온전히 완벽하게 분류해야 한다면, 먼저 책들을 가능한 한 똑같이 절반으로 나누도록 한다. 이 경우에도 책의 수는 500권으로 가정하자. 그러고는 부하직원들에게 절반으로 나뉜 그 책들을 분류하도록 부탁한다. 단, 한 사람에게 전부 다 분류하라고 시켜서는 안 된다. 그건 가장 높은 사람들이나 시킬 수 있는 일이다. 그냥 한 사람이 한 무더기씩만 정리하도록 시키면 된다. 부하직원들은 다시 좀 전의 그 상사처럼 한다. 즉 할당받은 분량을 반으로 나눈 후에 자기보다 아래 서열의 사람들에게 시키는 것이다. 이 아래 아래 서열의 사람들 총 네 명이 어떤 식으로든 맡은 바 과제를 수행해내면, 이제 둘로 분류되어 있는 1/4 분량의 책들을 합쳐서 각각 1/2로 만든다. 이 1/2 분량의 책은 어쩌면 완벽하게 절반으로 나뉘어 있지 않고 244권일 수도 있는데, 최악의 경우이 책들로 244번 비교해야 할지도 모른다. 그렇다면 나머지 무더기의 책은 256권이 되고, 그래서 256번 비교하게 된다. 아래 아래 서열의 사람들이 비교하는 총 횟수는 아무리 많아봤자 그래도 500번이다. 첫 번째 서열의 경우와 정확히 일치하는 횟수다. 그리고 세 번째, 네 번째, 다섯 번째 서열도 이와 다르지 않다(그럴듯한 방법처럼 들리지만, 이는 사실 문제가 점점 아래로 미뤄지는 것에 불과하다. )
분류 작업을 위해 얼마나 많은 서열, 단계가 필요할까? 책 500권을 가능한 한 똑같은 분량의 무더기 둘로 나누어 나갈 경우, 아홉 번째 단계에서 나뉘는 책 무더기는 각각 책 1권 또는 2권이 된다. 왜냐하면 절반으로 나누고 다시 절반으로 나누고…… 이런 식으로 계속해서 총 아홉 번을 나누다 보면, 즉 2를 아홉 번 곱하면 벌써 512가 나오기 때문이다.
밑이 2인 로그 9, 즉 log29는 log500과 대략 맞아떨어진다. 이게 바로 로그다. 다시 말해, 책 500권에는 9개의 서열이 필요하다는 이야기다. 각 서열마다 500번 비교하니까, 총 4500번 비교하게 된다. 그래도 한 번에 모든 책을 일일이 비교해볼 때의 경우의 수인 25만 번보다는 훨씬 적다. 비교한 후에 책을 꽂는 데 매번 5초씩 소요된다고 하면, 이 서열 방식으로 책을 다 정리하는 데는 총 6시간 30분이 걸린다. 일일이 비교해보는 방법이라면 밤낮으로 작업하더라도 꼬박 14일이 걸릴 것이다. 이 서열 방식은 보통 ‘병합 정렬(merge sort)’이라고 불린다. 영어의 ‘머지(merge)’에서 비롯된 것으로, 병합하고 합병한다는 뜻이다. 엄청나게 대단한 비즈니스에서나 사용할 법한 용어처럼 들리지만, 일반 가정에서도 잘 사용되고 있는 방법이다.
알고리즘적 사고는 인간적 사고의 한 부분으로서, 이런 근본적인 인간 성향을 더 나은 방향으로 키워 나가는 것은 중요한 일이다. 또한 이런 성향을 계발하기 위해 자신의 능력을 자각하는 것 역시 인간의 본성이라고 할 수 있다.
