알고리듬과 데이터 구조를 활용해 컴퓨터 문제를 해결하는 데 초점을 맞춘 책이다. 세계적인 프로그래밍 대회에 출제된 문제들 중 도전적이고 배울 점이 많은 문제를 엄선해 저자만의 알고리듬 설계 방법을 가르친다. 문제 분류, 데이터 구조 선택, 알고리듬 식별뿐만 아니라 해시 테이블, 힙, 트리와 같은 구조의 선택이 실행 시간에 미치는 영향과 최적화 방법도 다룬다. 또한 재귀, 동적 프로그래밍, 이진 탐색과 같은 전략을 통해 도전적인 문제를 해결하는 방법을 소개하며 코드 라인별 분석 및 다양한 알고리듬과 데이터 구조 사용법을 설명한다. 각 문제의 해법은 실제로 프로그래밍 판정 시스템(온라인 저지) 웹 사이트에서 직접 결과를 확인할 수 있다.

처음 테니스를 배울 때는 코트로 넘어온 공을 받아치기가 정말 어렵다. 게다가 백핸드 쪽으로 넘어오면 실수하기 일쑤다. 이후 몇 달 동안 꾸준히 연습을 하고 어느 정도 랠리가 될 정도의 기술이 몸에 익으면, 그 재미에 시간 가는 줄 모르고 빠져든다. 상위 기술인 슬라이스 백핸드, 킥 서브, 드롭 발리 등을 배우게 된다. 어느 정도 기술이 갖춰지면 서브와 발리, 칩 앤 차지, 베이스라인 공략처럼 중요하지만 눈에 보이지 않는 전략을 연구한다. 그리고 상대편 선수에 따라 어떤 기술과 전략이 가장 효과가 있는지를 알아내는 직관력을 계속 키운다. 누구에게나 무조건 통하는 만능 기술은 없다.
프로그래밍도 테니스와 마찬가지다. 코딩을 처음 배울 때는 주어진 문제를 컴퓨터에서 실행시키는 것도 상당히 어렵다. 그러나 초보를 벗어나면 진짜로 문제를 푸는 재미를 느끼게 된다. 문제 풀이를 잘 하려면 어떻게 해야 할까? 프로그래밍 분야도 다른 분야와 마찬가지로 모든 문제를 한 번에 해결해주는 만능 기법은 없다. 그러나 해시 테이블, 검색 트리, 반복, 메모이제이션, 동적 프로그래밍, 그래프 검색 등 유용한 고급 기법과 전략을 언제든 활용할 수 있다. 또한 충분한 훈련을 통해 많은 문제와 알고리듬에 딱 맞는 기법이 무엇인지를 알 수 있다. 즉, 반복 검색을 하거나 최소 연산 알고리듬이 필요하다면, 해시 테이블과 최소 힙으로 속도를 높일 수 있다는 것을 알 수 있다. 어떤 문제를 좀 더 작은 하위 문제로 반복 분할해서 해법을 찾으려면 재귀 기법을 사용하면 되고, 하위 문제가 중복될 때는 메모이제이션으로 속도를 높일 수 있다는 점도 알 수 있다.
테니스든 프로그래밍이든 상위 단계로 가려면 반복 연습과 좋은 선생님이라는 두 가지 요소가 필요한데, 바로 이 책이 그 기회를 제공한다. 이 책은 앞에서 말한 개념을 다루기만 하는 단순한 문제집이 아니다. 경진대회 기출 문제에 꼭 맞는 알고리듬을 찾아내고, 그것을 이용해서 문제를 해결하는 연습법도 제시한다. 부디 행복한 문제 풀이 시간이 되길 바란다.

◆ 체스 게임을 하는 최적의 방법과 책을 번역하는 최적의 방법을 찾기 위한 너비 우선 검색 알고리듬
◆ 미로를 빠져나갈 수 있는 생쥐의 수 또는 두 위치 사이의 가장 빠른 경로의 수를 결정하는 다익스트라 알고리듬
◆ 소셜 네트워크의 연결 여부 또는 친구 여부를 결정하기 위한 유니온-파인드 데이터 구조
◆ 매장 판촉에서 제공되는 금액을 결정하기 위한 힙 데이터 구조
◆ 눈송이가 고유한지 여부를 확인하거나 사전에서 복합어를 식별하기 위한 해시 테이블 데이터 구조

난이도 높은 문제를 해결하는 학습법을 배우려는 모든 프로그래머를 위한 책이다. 이 책을 통해 다양한 데이터 구조와 알고리듬, 문제 풀이에 도움이 되는 유형 및 구현 방법을 배울 수 있다.
이 책의 코드는 전부 C언어로 작성됐으나 C언어의 기초는 다루지는 않는다. 독자가 C/C++에 익숙하다면 바로 시작하는 데 어려움이 없을 것이다. 그 외에 자바나 파이썬 등 다른 언어로 프로그래밍한 경험이 있다면 대부분의 내용은 읽으면서 대략 이해할 수 있을 것이다. 그래도 1장을 시작하기 전에 C언어의 개요를 복습한다면 좀 더 도움이 될 것이다. 특히, 포인터와 동적 메모리 할당에 대해서는 기존의 프로그래밍 경험에 관계없이 숙지해 둘 필요가 있다. 독자에게 추천하는 C언어 책은 K. N. 킹의 『C Programming: A Modern Access, 2nd Edition』(W. W. Norton & Company, 2008)으로, C언어에 익숙한 사람에게도 참고용으로서 유용한 책이다.

기획 단계에서 최신의 멋진 알고리듬을 설명하고 기존의 기법들과 비교하는 구성도 고민했었다. 설명을 위주로 하고 실제 알고리듬 문제를 접하지 않으면 금방 기억에서 잊힌다는 단점을 떠올릴 수밖에 없었다.
이 책은 알고리듬 기법을 먼저 설명하지 않고, 문제를 먼저 제시하는 방식을 사용한다. 게다가 제시되는 문제도 상당히 어려워서 기존의 방법으로는 쉽게 풀 수 없다. 즉, 독자들이 어려운 문제를 접하면서 이미 알고 있는 경험과 문제 해결에 필요한 지식을 연결시키는 방식으로 기술을 습득할 수 있다.
아마도 기존의 교과서에서 봤던 문제는 찾을 수 없을 것이다. 행렬을 곱하거나 피보나치 수열을 계산하는 최적 방법에 대한 내용도 없다. 또한, 하노이 탑 문제를 풀 일도 없을 거라고 장담한다. 다른 많은 훌륭한 교과서들이 이런 문제를 다루고 있는 것이 현실이지만, 과연 그런 종류의 문제에 흥미를 느끼는지는 의문이다.
오히려 독자들이 접해 보지 못한 새로운 문제를 활용하려고 한다. 해마다 수천 명의 사람들이 프로그래밍 경진대회에 참가한다. 대회를 준비하는 주최측은 참가자들이 기존 답안을 다시 쓰거나 구글 검색만 이용해서 풀 수 없도록 새로운 문제를 준비한다. 새로운 문제는 기존의 문제를 새로운 상황에 맞도록 변형하며, 참가자들이 새로운 해법을 찾아내도록 도전하고 흥미를 유발한다. 이런 문제를 푸는 데 필요한 프로그래밍과 컴퓨터 지식은 끝이 없다. 제대로 된 문제를 고를 수만 있다면 실컷 배울 수 있다.
가장 기초적인 정의를 떠올려보자. 자료 구조, 즉 데이터 구조란 데이터를 구조화해 연산을 빠르게 하는 방법을 말한다. 알고리듬은 문제 해결 방법을 순서대로 나열한 것이다. 가끔은 정교한 데이터 구조 없이도 빠른 알고리듬을 만들어 낼 수 있다. 그러나 올바른 데이터 구조를 사용한다면 알고리듬의 속도를 획기적으로 향상시킬 수 있다.
이 책을 열심히 공부하면 실력 있는 프로그래머가 될 수는 있지만, 그것이 필자의 목표는 아니다. 프로그래밍 경진대회의 문제 풀이를 통해 데이터 구조와 알고리듬을 재미있게 가르치고 배우는 것을 마음에 두고 썼다. 이 책에서 배울 만한 것이나, 재미난 것을 찾았다면 소감을 이메일로 보내주길 바란다.

다니엘 진가로(Daniel Zingaro)

토론토 대학의 컴퓨터 과학과 조교수이며 토론토 대학의 교육상을 수상했다. 주요 연구 분야는 컴퓨터 과학 교육 연구로써, 컴퓨터 과학 교재를 통한 학습 방법을 연구한다.

이정표

모바일 브라우저 개발부터 클라우드 서비스 기획까지 20년간 다양한 개발 프로젝트에 참여했으며, 현재는 SW와 IT 분야의 기술조사평가 업무를 하고 있다. 옮긴 책으로는 에이콘출판사에서 펴낸 『난독화, 디지털 프라이버시 생존 전략』(2017), 『젠킨스 마스터』(2018), 『젠킨스 블루오션 시작하기』(2019), 『린 모바일 앱 개발』(2019), 『알고리즘 윤리』(2021), 『배포 자동화와 지속적 인도』(2022) 등이 있다.