알고리즘은 알고 보면 재미있다

알고리즘은 문제를 해결하기 위한 단계적인 절차를 의미한다. 흔히 알고리즘을 요리법에 비유하기도 한다. 레시피에 따라 만들어진 요리는 맛도 좋고 시간도 절약된다. 이렇둣 알고리즘도 단계적인 절차를 따라 하면 주어진 문제를 쉽고도 빠르게 해결할 수 있다. 이 책은 이러한 알고리즘을 한 걸음 한 걸음 나아가듯이 단계를 따라 설명하고 있어 빠르고 쉽게 이해할 수 있다.
여러분도 이미 알고 있는, 종이에서 연필을 떼지 않고 그리는 한붓그리기 문제도 알고리즘을 통하면 쉽게 해결할 수 있다. 그리스 신화에 나오는 반수반인의 괴물 미노타우로스에게 잡아먹히지 않게 미로를 빠져나오기 위해서도 알고리즘은 필요하다. 다음은 독이 든 술 단지에 대한 옛날이야기로 이 역시 알고리즘을 통하면 쉽게 해결할 수 있다.

옛날 어느 먼 나라에 술을 매우 즐겨 마시는 임금님이 살고 있었다. 그래서 창고에는 많은 술 단지가 보관되어 있었다. 그런데 어느 날 이웃 나라의 간자가 창고에 들어가서 술 단지 하나에 독을 넣고 나오다가 붙잡혔다. 간자를 추궁하였더니 간자는 눈으로 확인할 수 없는 독을 사용하였고, 어떤 단지인지는 모르지만 하나의 단지에만 독을 넣었다고 실토하고는 스스로 목숨을 끊었다. 간자가 사용한 독의 특징은 독이 든 단지의 술을 아주 조금만 맛보아도 술을 맛본 사람은 정확히 일주일 후에 죽는다는 것이었다. 임금님은 독이 든 술 단지를 반드시 일주일 만에 찾아내라고 신하들에게 명하였다.

자, 여러분은 어떻게 해결할 것인가? 이처럼 이 책은 알고리즘이 재미있는 과목이라는 것을 알기 쉽고 재미있으며, 친절하게 소개하고 있다. 다양하고 재미있는 삽화와 그림을 곁들이면서 내용의 이해를 돕고 있는 것은 물론이다.

알고리즘을 단계적으로 완전 이해한다

컴퓨터를 전공하는 대부분의 학생들에게 알고리즘의 이해는 만만치 않은 어려움이다. 알고리즘의 어려움은 여러 다양한 경우들을 조목조목 ‘따져보는’ 논리적 검토 과정에서 비롯된다. 그러나 실제 알고리즘은 컴퓨터 분야뿐만 아니라 과학, 공학, 경영학 등 광범위한 분야에서 나타나는 많은 중요한 문제들을 해결하는 기본적인 방법들과 직간접적으로 관련되어 있어, 반드시 이해하고 숙달할 필요가 있다.
따라서 이 책은 알고리즘 이해에 있어 가장 기본적이고 공통된 부분을 발췌, 정리하였다. 또한 독자들이 쉽게 이해할 수 있도록 다음의 네 가지 단계를 염두에 두고 설명하였다.

- 주어진 문제에 대한 이해와 분석
- 알고리즘의 핵심 아이디어 유추
- 알고리즘 소개 및 단계별 설명
- 예제 따라 알고리즘 이해하기

주어진 문제가 어떤 특성을 가졌는지를 분석해보면 그 문제를 해결할 알고리즘을 고안하는 실마리를 찾을 수 있다. 이를 통해 알고리즘의 핵심 아이디어를 유추해보면, 알고리즘을 보다 쉽게 이해할 수 있다. 또한 예제를 통해 알고리즘의 수행과정을 상세히 step-by-step으로 보임으로써 알고리즘을 완전히 이해할 수 있도록 하였다. 아울러 시간복잡도를 분석하고, 알고리즘의 효용성을 위해 알고리즘이 실제로 활용되는 사례들을 설명하였다.

이 책의 내용

1장 ‘알고리즘의 첫걸음’에서는 이미 알고 있는 알고리즘들부터 수수께끼같이 재미있는 문제에 대한 알고리즘들을 살펴본다. 2장 ‘알고리즘을 배우기 위한 준비’에서는 알고리즘이란 무엇인가를 알아보고, 최초의 알고리즘인 유클리드의 최대공약수 알고리즘을 소개한다. 또한 3장부터 다루는 알고리즘들을 배울 준비를 위한 알고리즘의 표현 방법, 알고리즘의 분류, 알고리즘의 효율성 표현 방법, 복잡도의 점근적 표기를 소개하고, 마지막으로 왜 효율적인 알고리즘이 필요한가를 설명한다. 3장 ‘분할 정복 알고리즘’에서는 분할 정복(Divide-and-Conquer) 알고리즘으로 해결되는 문제들을 소개하고, 그에 대한 알고리즘들을 설명한다. 합병 정렬(Merge sort), 퀵 정렬(Quick sort), 선택(Selection) 문제, 최근접 점의 쌍(Closest Pair) 찾기 문제를 다룬다.
4장 ‘그리디 알고리즘’에서는 동전 거스름돈(Coin Change), 최소 신장 트리(Minimum Spanning Tree), 최단 경로(Shortest Path), 부분 배낭(Fractional Knapsack) 문제, 집합 커버(Set Cover), 작업 스케줄링(Task Scheduling), 허프만 압축(Huffman Encoding)에 대한 그리디 알고리즘을 각각 소개한다. 5장 ‘동적 계획 알고리즘’에서는 모든 쌍 최단 경로(All Pairs Shortest Paths), 연속 행렬 곱셈(Chained Matrix Multiplication), 편집 거리(Edit Distance) 문제, 배낭(Knapsack) 문제, 동전 거스름돈(Coin Change) 문제의 동적 계획 알고리즘을 소개한다. 6장 ‘정렬 알고리즘’에서는 기본적인 정렬 알고리즘인 버블 정렬(Bubble sort), 선택 정렬(Selection sort), 삽입 정렬(Insertion sort)을 다루고, 이보다 효율적인 쉘 정렬(Shell sort)과 힙 정렬(Heap sort)을 살펴보며, 특정 환경에서 사용되는 기수 정렬(Radix sort)과 외부정렬(External sort)을 소개한다.
7장 ‘NP-완전 문제’에서는 NP-완전 문제들을 이해하고, 그 문제들 간의 관계를 살펴본다. 8장 ‘근사 알고리즘’에서는 지수 시간복잡도를 가진 NP-완전 문제들에 대한 정확한 해보다는 근사 해(approximation solution)를 찾는 알고리즘들을 소개한다. 이를 위해 여행자 문제(Traveling Salesman Problem), 정점 커버(Vertex Cover) 문제, 통 채우기(Bin Packing) 문제, 작업 스케줄링(Job Scheduling) 문제, 클러스터링(Clustering) 문제의 근사 알고리즘을 각각 알아본다. 9장 ‘해 탐색 알고리즘’에서는 NP-완전 문제의 해를 탐색하기 위한 다양한 알고리즘을 소개한다. 백트래킹 (Backtracking) 기법, 분기 한정(Branch-and-Bound) 기법, 유전자 알고리즘(Genetic Algorithm), 모의 담금질(Simulated Annealing) 기법을 소개한다.

Chapter 01 알고리즘의 첫걸음
1.1 최대 숫자 찾기
1.2 임의의 숫자 찾기
1.3 동전 거스름돈
1.4 한붓그리기
1.5 미로 찾기
1.6 가짜 동전 찾기
1.7 독이 든 술단지
■ 요약
■ 연습문제
 
Chapter 02 알고리즘을 배우기 위한 준비
2.1 알고리즘이란
2.2 최초의 알고리즘
2.3 알고리즘의 표현 방법
2.4 알고리즘의 분류
2.5 알고리즘의 효율성 표현
2.6 복잡도의 점근적 표기
2.7 왜 효율적인 알고리즘이 필요한가?
■ 요약
■ 연습문제

Chapter 03 분할 정복 알고리즘
3.1 합병 정렬
3.2 퀵 정렬
3.3 선택 문제
3.4 최근접 점의 쌍 찾기
3.5 분할 정복을 적용하는 데 있어서 주의할 점
■ 요약
■ 연습문제

Chapter 04 그리디 알고리즘
4.1 동전 거스름돈
4.2 최소 신장 트리
4.3 최단 경로 찾기
4.4 부분 배낭 문제
4.5 집합 커버 문제
4.6 작업 스케줄링
4.7 허프만 압축
■ 요약
■ 연습문제

Chapter 05 동적 계획 알고리즘
5.1 모든 쌍 최단 경로
5.2 연속 행렬 곱셈
5.3 편집 거리 문제
5.4 배낭 문제
5.5 동전 거스름돈
■ 요약
■ 연습문제

Chapter 06 정렬 알고리즘
6.1 버블 정렬
6.2 선택 정렬
6.3 삽입 정렬
6.4 쉘 정렬
6.5 힙 정렬
6.6 정렬 문제의 하한
6.7 기수 정렬
6.8 외부정렬
■ 요약
■ 연습문제

Chapter 07 NP-완전 문제
7.1 문제 분류
7.2 NP-완전 문제의 특성
7.3 NP-완전 문제의 소개
7.4 NP-완전 문제들의 활용
■ 요약
■ 연습문제

Chapter 08 근사 알고리즘
8.1 여행자 문제
8.2 정점 커버 문제
8.3 통 채우기 문제
8.4 작업 스케줄링 문제
8.5 클러스터링 문제
■ 요약
■ 연습문제

Chapter 09 해 탐색 알고리즘
9.1 백트래킹 기법
9.2 분기 한정 기법
9.3 유전자 알고리즘
9.4 모의 담금질 기법
■ 요약
■ 연습문제

부록
Ⅰ. 재귀 관계의 해 구하는 방법
Ⅱ. 힙 자료구조
Ⅲ. 매칭
Ⅳ. 백트래킹 기법과 분기 한정기법의 추가 문제