알고리즘 비밀의 문을 열다

▣ 출판사서평

★ 이 책에서 다루는 내용 ★

■ 컴퓨터 알고리즘의 기초 개념과 기술 및 평가 방법
■ 컴퓨터에서 정보를 찾아내는 간단한 방법
■ 컴퓨터에서 정보를 정해진 순서에 따라 재정렬하는 방법
■ 컴퓨터에서 그래프로 일컬어지는 수학적 구조로 모델링 가능한 문제를 해결하는 기본 방법
■ 일련의 문자로 이뤄진 텍스트 형식의 문자열에 관련된 문제를 푸는 방법
■ 암호학의 배경이 되는 기본 원리
■ 데이터 압축의 기본적인 아이디어
■ 컴퓨터를 이용해 합리적인 시간 안에 풀기 어려운 문제들


★ 이 책의 대상 독자 ★

앞에서 말했듯이 이 책은 약간의 수학을 포함한다. 수학 공포증을 앓고 있는 사람이라면 수학이 나오는 부분을 건너뛰거나, 덜 기술적인 책을 선택해도 좋다. 물론 여러분이 수학을 쉽게 이해할 수 있도록 최선을 다할 것이다.
여러분에게 컴퓨터 프로그램을 작성해보거나 읽어본 경험을 요구하지도 않는다. 요약된 형태의 안내문을 따라 할 수 있는 정도라면, 앞으로 설명할 알고리즘의 각 단계와, 그 단계들이 모여 이뤄지는 알고리즘도 분명 이해할 수 있을 것이다.


★ 지은이의 말 ★

컴퓨터는 어떻게 문제를 해결하는가? 여러분의 조그만 GPS는 수없이 많은 가능한 경로 중에서 어떻게 목적지에 이르는 가장 빠른 길을 수 초 만에 찾아내는가? 여러분이 인터넷에서 물건을 구입할 때 누군가가 여러분의 신용카드 번호를 가로채지 못하도록 보호하는 방법은 무엇인가? 이를 비롯한 수많은 질문의 답이 바로 알고리즘(algorithm)이며, 이 알고리즘의 신비를 여러분에게 밝히고자 한다.
나는 예전에 『Introduction to Algorithms』(한빛아카데미, 2014)라는 훌륭한(물론 주관적인 생각이지만) 교재도 저술했지만, 다분히 기술적인 관점에서 저술한 책이었다.
여러분이 읽는 이 책은 입문서가 아니며, 교재용으로 쓰인 책도 아니다. 컴퓨터 알고리즘 분야를 광범위하게 다루거나 심도 있게 파고들지 않는다. 컴퓨터 알고리즘을 설계하는 기술을 정확하게 가르치거나, 독자가 풀어야 할 연습문제를 제공하지도 않는다.
그렇다면 이 책의 목적은 무엇인가? 여러분이 다음과 같은 경우에 해당한다면 이 책이 출발점이 될 수 있다.
■ 컴퓨터가 문제를 해결하는 방법을 알고 싶다.
■ 그러한 해법들의 우수성을 평가하는 방법을 알고 싶다.
■ 컴퓨팅 분야의 갖가지 문제들과 이러한 문제를 해결하는 방법들이 컴퓨터 밖의 실제 세상과 어떻게 관련되는지 알고 싶다.
■ 수학을 조금 할 줄 안다.
■ 컴퓨터 프로그램을 한 번도 작성해본 적이 없다(그래도 여러분의 뇌를 학습시킬 프로그램을 돌리는 데는 아무 문제가 없다).
컴퓨터 알고리즘을 다루는 책은 많다. 그중에는 기술적 세부사항을 최소화한 개념서도 있고, 숨이 막힐 정도로 기술적인 정확성을 중요시하는 책도 있다. 물론 그 사이 어딘가에 위치한 책도 있으며, 각각은 나름의 위치를 지킨다. 이 책은 ‘그 사이 어딘가’에 위치한 책이다. 약간의 수학을 포함하며 때로는 좀 더 자세한 내용을 다루지만, 너무 깊은 세부사항을 다루지는 않는다(책의 후반부에 가까워지면서 나 스스로를 통제할 수 있을지 모르겠지만 말이다).
이 책을 일종의 애피타이저로 생각해도 좋다. 여러분은 이탈리안 레스토랑에서 애피타이저를 주문했고, 나머지 요리는 애피타이저를 맛본 후에 주문할 생각이다. 자, 이제 애피타이저가 나왔고 맛을 보기 시작한다. 애피타이저가 맘에 들지 않는다면 다른 요리는 주문하지 않는다. 애피타이저가 맘에 들어도 배가 부르다면 다른 요리를 주문하지 않는다. 애피타이저가 맘에 들고 여전히 배가 고프다면 다음 요리를 찾기 시작한다. 이 책이 애피타이저라면 나는 여러분의 이야기가 앞의 세 가지 결말 중에서 두 번째나 세 번째 결말로 끝나길 바란다. 책을 만족스럽게 읽었지만 알고리즘의 세계를 더 깊이 들여다볼 필요를 느끼지 못하거나, 책에서 읽은 내용이 너무 흥미로워서 더 많은 내용을 배우고 싶기를 바란다. 각 장의 끝에서는 ‘더 읽을거리’를 제공하는데, 이를 바탕으로 각 주제를 자세히 다루는 책이나 문서를 만나볼 수 있다.

★ 옮긴이의 말 ★

알고리즘이라… 컴퓨터를 전공한 사람에게는 골치 아픈 단어일 것이고, 그렇지 않은 사람에게는 뜻 모를 이상한 단어로 들릴 것이다. 하지만 알고리즘은 오늘날 우리의 일상생활 곳곳에 녹아들어 있으며, 컴퓨터를 이용하는 거의 모든 일이 알고리즘 없이는 불가능할 것이다.
매일 아침 출근길에 자동차 내비게이션을 이용할 때, 회사 업무에 필요한 자료를 인터넷에서 다운로드할 때, 친구와의 저녁 약속을 위해 지하철 노선을 검색할 때, 우리는 알게 모르게 ‘최단 경로 찾기’ 알고리즘을 사용한다. 그리고 그 덕분에 가장 빠른 출근길을, 가장 빠른 라우팅 경로를, 가장 빠른 지하철 노선을 찾을 수 있다. ‘최단 경로 찾기’ 알고리즘이 없다면 우리는 내비게이션을 이용할 수도 없고, 인터넷도 사용할 수 없으며, 커다란 종이에 인쇄된 지하철 노선도를 지니고 다녀야 할 것이다.
하지만 ‘최단 경로 찾기’는 우리가 사용하는 수많은 알고리즘 중에 하나일 뿐이다. 컴퓨터가 문제를 해결하는 방법을 규정하는 것이 바로 알고리즘이며, 컴퓨터로 하는 상당수의 작업을 알고리즘으로 설명할 수 있기 때문이다. 따라서 컴퓨터가 없는 현대 문명을 상상할 수 없듯이, 알고리즘이 없는 현대 문명도 상상할 수 없다.
이처럼 알고리즘은 우리의 일상을 지탱하는 중요한 역할을 하기에 오늘날을 살아가는 거의 모든 사람은 좋든 싫든 알고리즘과 관계를 맺고 살아간다. 물론 골치 아픈 알고리즘에 신경을 쓰지 않고도 그 혜택을 누릴 수 있지만, 컴퓨터화된 세상을 살아가는 인간으로서 컴퓨터 알고리즘이 무엇인지를 이해한다면 우리가 살아가는 세상을 더 잘 이해할 수 있을 것이다.
컴퓨터를 공부하는 학생이나 컴퓨터를 업으로 삼는 사람이라면, 더욱이 알고리즘적 소양을 갖춰야 한다. 사람이 하기 어렵거나 너무 오랜 시간이 걸리는 일을 컴퓨터에게 시키려면, 당연히 컴퓨터의 언어와 사고방식을 이해해야 효과적이고 효율적으로 컴퓨터를 부려먹을(?) 수 있다. 여기서 컴퓨터의 언어가 프로그래밍 언어라면, 컴퓨터의 사고방식이 바로 알고리즘이라고 할 수 있다. 사고방식에 대한 이해 없이 언어만 대충 이해한 채로 컴퓨터에게 일을 시킨다면 어떻게 될까? 복잡하고 고차원적인 일은 아예 시키지도 못하거나, 잘못된 일을 시키거나, 1분이면 될 일을 1시간 동안 하게 만들 것이다.
이 책은 알고리즘 분야의 대가이자 전 세계에서 가장 널리 쓰이는 알고리즘 교재 『Introduction to Algorithms』(한빛아카데미, 2014)의 저자 토마스 코멘의 또 다른 명저로, 컴퓨터를 전공하는 사람은 물론 우리의 일상을 지탱하는 컴퓨터 알고리즘을 이해하고 싶은 일반 대중에게도 알고리즘의 기본 개념을 쉽게 설명한다. 주로 사용되는 알고리즘을 일상적인 예로 설명함으로써 복잡한 알고리즘 이론에 친근하게 다가설 수 있도록 도움을 주며, 그러한 알고리즘의 기저에 깔린 사고방식을 차근차근 설명한다. 그리고 이를 바탕으로 알고리즘을 이해하고 평가하는 것은 물론, 좋은 알고리즘을 설계하고 싶은 독자에게 훌륭한 출발점을 제공한다. 부디 많은 독자가 이 책을 읽고, 어렵고 복잡하게만 느껴지는 컴퓨터 알고리즘에 조금이라도 친숙해지기를 바란다.

▣ 작가 소개

저자 : 토마스 코멘
다트머스 대학(Dartmouth College)의 컴퓨터 과학부 교수이자 저술/작문원의 전임 책임자다. 찰스 E. 레이서손(Charles E. Leiserson)과 로널드 L. 리베스트(RonaldL. Rivest), 클리포드 스타인(Clifford Stein)과 함께 『Introduction to Algorithms』(제3판, MIT Press, 2009)를 저술하기도 했다.

역자 : 최광민
한양대학교 컴퓨터 전공을 마치고 현재 삼성SDS 연구소 알고리즘 연구팀에서 책임 연구원으로 재직 중이다. 회사에서든 일상에서든 새롭고 흥미로운 기술이라면 무엇이든 배우고 즐길 준비가 돼있으며 백발노인이 돼서도 끝없이 탐구하고 창조하는 사람이 되는 것을 인생의 목표로 삼고 있다.

▣ 주요 목차

1장. 알고리즘이란 무엇이며, 왜 배워야 하는가?
2장. 컴퓨터 알고리즘을 기술하고 평가하는 방법
3장. 정렬 알고리즘과 탐색 알고리즘
4장. 정렬의 하한계 뛰어넘기
5장. 방향성 비순환 그래프
6장. 최단 경로
7장. 문자열 처리 알고리즘
8장. 암호학의 기초
9장. 데이터 압축
10장. 어려운 문제들