빠르고 좋은 ‘선택’을 위해 필요한 알고리즘
- 알리 알모사위, 『알고리즘 라이프』
알고리즘은 ‘한정된 시간에 유의미한 목적을 달성하는 명확한 단계들의 연쇄’를 의미한다. ‘한정된 시간’과 ‘유의미한 목적을 달성’에 초점을 맞춰 읽으면, 알고리즘은 주어진 시간에 어떤 일을 효율적으로 마무리하는 걸 가리킨다. 효율성이 알고리즘에서는 아주 중요한 말이 된다는 얘기다. 알리 알모사위가 지은 『알고리즘 라이프』(정주연 옮김, 생각정거장, 2017)는 이러한 알고리즘이 일상생활에는 어떻게 적용될 수 있는지 이야기하고 있다. 일상을 영위하다 보면 우리는 짧은 시간에 많은 일을 해야 하는 상황에 직면한다. 시간이 좀 있어도 되도록 빨리 일을 끝마치려고 한다. 남는 시간을 다른 일(놀이라고 해도 상관없다)에 사용할 수 있기 때문이다. 시간은 금이라는 말이 진리처럼 받아들여지는 자본주의 사회라면, 알고리즘이라는 말에는 이미 우리가 외면하기 힘든 어떤 진리가 담겨 있다.
이 책에서 지은이는 거실, 양복점, 백화점 같은 익숙한 장소에서 우리가 맞닥뜨릴 수 있는 12가지 상황을 제시한다. 각 상황마다 두 가지 해결 방법이 나온다. 하나의 방법이 다른 방법보다 더 효율적인데, 지은이는 그 이유를 ‘알고리즘’으로 풀어내고 있다. 이 책의 원제는 『나쁜 선택들Bad Choices』이다. 상황에 따라 제시된 두 가지 방법 중 어느 게 좋은 선택이고, 어느 게 나쁜 선택인지 구분해야 한다는 의미가 이 제목에는 들어 있다. 곧 지은이는 우리가 일상에서 직면하는 상황을 빠르게 해결하는 방법을 우리에게 알려주려고 한다. 그러나 지은이는 이러한 효율적인 방법이 실제 상황에 반드시 적용되는 건 아니라고 분명히 이야기한다. 우리가 사는 일상이라는 게 그렇지 않은가? 효율성만으로 일상의 모든 문제가 해결된다면, 우리가 사는 삶은 지금보다 훨씬 더 편안하고 안정적으로 이루어질 테니까 말이다.
이 책에 나온 첫 번째 예시에는 ‘산더미처럼 쌓인 양말 짝을 맞춰라’라는 제목이 붙어 있다. 식구들 발 크기와 양말색이 다 제각각인 양말 짝을 어떻게 하면 빠르게 맞출 수 있을까? 두 가지 방법이 제시된다. ① 양말 한 짝을 꺼낸 후 빨래더미에서 짝을 찾아 한쪽에 놓는다. 그 다음 다른 양말을 꺼낸다. 짝을 찾고 한쪽에 놓는다. 이런 식으로 계속한다. ② 양말 한 짝을 꺼내 한쪽에 놓은 다음 다른 양말을 꺼낸다. 그 양말이 놓아둔 것과 짝이 맞으면 맞춰 놓는다. 안 맞으면 짝 없는 양말 줄에 따로 놓되 색깔이나 크기가 같은 것들을 모아둔다. 두 가지 방법 중 우리는 ②가 효율적이라는 걸 ‘직관적으로’ 판단한다. 실제 지은이도 ②를 효율적이라고 생각한다. 다만 설명하는 방식이 다를 뿐이다.
지은이는 검색표lookup table 즉 캐시cache를 이야기한다. “검색표란 독특한 식별자Key의 모의 모음이라고 생가하면 이해하기 쉽다. 그 식별자들 각각이 데이터의 연관항목value을 가리키고 우리는 그 항목에서 키의 값을 검색한다.”(25쪽) 위 예시의 경우 키는 ‘색깔’이다. 키를 설정하면 양말들을 배열array하기가 쉽다. 문제는 물건들이 상당히 많으면 시간 또한 그만큼 많이 걸릴 수 있다는 점에 있다. 알고리즘은 효율성을 따지는 원리라고 했다. 효율성은 결국 시간 싸움이다. 두 번째 예시로 나온 ‘폭탄세일 셔츠를 쓸어 담아라’는 많은 물건들 중에서 어떻게 하면 빠르게 자기가 원하는 물건을 찾을 수 있는지 설명한다.
우선 선형시간linear function이란 개념이 있다. 물건이 100개 있는데 100개의 물건을 다 살펴보는 데 걸리는 시간을 의미한다. 로그시간logarithmic time도 있는데, 지은이는 “중앙에서 시작해서 왼쪽이나 오른쪽으로 이동하여 검색하고 매번 검색할 집합을 반으로 나누는 것이 바로 로그시간 알고리즘을 사용하는 전형적인 방법”(37쪽)이라고 풀이하고 있다. 선형시간보다 로그시간은 천천히 증가한다. “천천히 증가한다는 말은 우리의 방법이 항목의 수에 아주 민감하게 반응하지 않는다는 뜻”(38쪽)이다. 이진검색binary search이라고도 하는 이 방법을 사용하면 선형검색linear search을 사용할 때보다 시간을 많이 절약할 수 있다고 지은이는 강조한다. 우리가 사는 일상은 이렇게 수많은 알고리즘으로 구성되어 있다고 할 수 있는 셈이다.
‘쏟아진 우편물을 주소에 따라 정리하라’는 과제가 붙은 다섯 번째 상황을 해결하기 위해 지은이는 이차시간quadratic-time 알고리즘을 끌어들인다. 인접 항목을 비교하여 정렬시킬 때 실행된다. “봉투의 개수가 n이라면 인접한 봉투들을 비교하여 원래의 순서로 되돌려놓는 함수는 ‘n2이 하한계’라고 할 수 있다. 즉 평균적으로(이 말이 중요하다) 결코 그보다 더 빨라질 수 없다는 뜻이다.”(67쪽) 이차미만subquadratic 정렬의 일반적인 방법은 분할정복법divide and conquer인데, 집합을 반으로 나누는 것은 로그시간이고, 그것들을 다시 합쳐놓는 것은 모든 항목에 한 번씩만 방문하므로 선형시간 작업이다. 여기서 선형로그linearithmic 시간이 나온다. 선형로그 시간은 이차시간보다 훨씬 빠르고 선형시간보다 약간 느리다. 전문용어가 사용돼서 다소 어려워 보이지만, “항목들의 집합을 더 작은 집합들로 쪼갠 후에 그 집합들을 정렬하는 방식”(68쪽)이라고 이해하면 되겠다.
지금까지 항목들의 집합을 저장하는 기본 방식인 배열에 관해 이야기했다. 6장에서는 행렬이라는 유용한 구조도 소개했다. 행렬도 배열처럼 항목의 집합을 저장하지만 배열과 달리 두 개의 차원에 저장한다. 두 구조가 유사한 것은 배열이 사실 행렬이 될 수 있기 때문이다. 즉 어떤 배열에 문자열literal(숫자나 글자 혹은 단어) 대신 다른 배열을 저장하면 행렬이 된다. 배열들로 이루어진 배열은 2차원 배열이라고 하며, 보통 다차원배열multidimensional array이라 부른다. (142쪽)
이 책에는 12가지 상황에 맞는 개념들이 나오고 있지만, 크게 보면 이 책은 배열과 행렬이라는 구조들을 중심으로 서술되고 있다. 12번째 과제로 제시된 ‘마트에서 최대한 빠르게 필요한 물건만 쓸어 담기’를 해결하기 위해 지은이는 앞서 이용한 방법들을 다양하게 적용하고 있다. 순서와 상관없이 빠르게 검색하는 해시표가 다시 나오고, 8장에서 이야기한 우선순위대기열도 나온다. 검색과 임의의 지점에 항목을 삽입하는 데 최적화된 구조들(각각 배열과 링크된 리스트)이 또 한 번 설명된다. 이진검색나무binary search tree로 각 물건의 순위를 한눈에 볼 수 있는 구조도가 제시되기도 한다. 다소 낯선 단어들이 여기저기서 튀어나와 읽는 속도가 느려지긴 했지만, 일상 속에서 알고리즘이 어떻게 실천되고 있는지 살피는 데는 큰 무리가 없었다.
지은이는 알고리즘을 계속 파고들다 보면 결국 인공지능을 만나게 된다고 이야기한다. “인공지능 분야에서 현실에 적용된 알고리즘 덕분에 병원이 더 빠르게 진단을 내리고 환자의 목숨을 구하거나 연구자들이 인간 게놈처럼 복잡한 것들을 더 잘 이해할 수 있”(154쪽)게 된다는 것이다. 어느 시대보다 인공지능에 대한 의존도가 커지는 시점에서 인공지능의 근원에 해당되는 알고리즘을 어느 정도 이해할 필요는 있어 보인다. 이 책 뒤에는 ‘증가율’과 ‘알고리즘 관계도’가 부록으로 실려 있다. 증가율은 문제를 해결하는 데 걸리는 시간을 가리키고, ‘알고리즘 관계도’는 이 책에 실린 12가지 과제(상황)를 알고리즘 관계도로 그린 것이다. 책의 내용을 다시 한 번 되살리는데 많이 도움이 되었다.
(이 리뷰는 예스24 리뷰어클럽을 통해 제작사로부터 상품을 제공받아 작성되었습니다.)