그들은 알고리즘을 알았을까? - 길 찾던 헨젤과 그레텔 마법 주문 외우던 해리 포터 -

영화와 동화 속 이야기로 풀어내는
컴퓨터 과학과 알고리즘

 컴퓨터 과학은 체계적인 문제 해결의 연구로, 우리가 매일 겪는 일상의 활동들이 문제 해결과 관련이 있습니다. 아침에 일어나고, 샤워를 하고, 옷을 입고, 아침을 먹는 간단한 일상은 일련의 잘 정의된 단계를 거쳐, 반복되는 문제를 해결합니다. 컴퓨터 과학에서 이러한 과정을 알고리즘이라고 합니다. 이 책은 우리에게 친숙한 영화, 동화와 일상생활 이야기로 컴퓨터 과학과 알고리즘의 개념을 풀어냅니다.

컴퓨터 과학의 주제는 계산입니다. 이 책은 아침 식사, 출근, 병원 진료, 취미 활동 등 일상생활 속에서 발견할 수 있는 계산의 사례로 이야기를 시작합니다. 그리고 헨젤과 그레텔, 인디아나 존스, 해리 포터 등의 이야기를 통해 알고리즘, 표상, 제어구조, 재귀 등 컴퓨터 과학의 개념을 설명합니다. 컴퓨터 과학과 알고리즘을 처음 접하는 분들, 컴퓨터 과학의 개념을 이해하는 데 어려움을 겪고 있는 분들 모두 영화와 동화 이야기와 함께라면 이를 쉽고 재미있게 배울 수 있을 겁니다.

Chapter 01 계산 및 알고리즘: 헨젤과 그레텔
 계산을 수행하는 것은 컴퓨터에 의한 알고리즘의 실행입니다. 알고리즘만 있으면 언제 어떤 컴퓨터를 이용해서든 반복적으로 계산을 수행할 수 있습니다. 계산의 또 다른 중요한 측면은 자원을 필요로 하며 시간이 걸린다는 것입니다. 여기서 다시 알고리즘적 기술이 중요해지는데, 왜냐하면 그것이 계산에 필요한 자원을 분석하는 데에 도움이 되기 때문입니다. 1장과 2장에서는 알고리즘의 개념과, 알고리즘이 체계적인 문제 해결을 위해 사용됨을 설명합니다.

Chapter 02 표상과 데이터 구조: 셜록 홈즈
 계산의 핵심은 표상을 변형시키는 것입니다. 3장에서는 표상이란 무엇이며 어떻게 계산에 사용하는지 설명합니다. 계산은 많은 경우 대량의 정보를 대상으로 하기 때문에, 4장에서는 어떻게 대량의 데이터를 효율적으로 구성할 수 있는지 설명합니다. 이러한 질문이 까다로운 이유는 데이터 구성 방식에 따라 데이터에 접근하는 어떤 방식은 효율적으로 지원하지만, 다른 방식에는 그렇지 않다는 사실 때문입니다.

Chapter 03 문제 해결과 한계: 인디아나 존스
 알고리즘을 통해 해결할 수 있는 많은 문제 중에서 두 가지는 특히 자세히 논의해 볼 만한 가치가 있습니다. 5장에서는 데이터에 대해 가장 자주 사용되는 계산 중 하나인 검색 문제를 설명합니다. 6장에서는 정렬 문제를 설명하면서, 강력한 문제 해결 방법과 문제의 고유 복잡도라는 개념에 대해서 설명하며, 7장에서는 소위 풀기 어려운 문제에 대해서 설명합니다. 이러한 문제에 대해서도 알고리즘은 존재하지만 실행이 너무 오래 걸리므로 실질적으로 이런 문제들은 해결할 수 없습니다.

Chapter 04 언어와 의미: 오버 더 레인보우
 모든 알고리즘은 어떤 종류의 언어이든 언어로 표현됩니다. 현재의 컴퓨터는 인간과 달리 자연어가 가지는 모호성을 쉽게 처리할 수 없으므로 인간의 언어로 프로그래밍될 수 없습니다. 따라서 컴퓨터에 의해 실행되는 알고리즘은 구조와 의미가 잘 정의된 언어로 작성되어야 합니다. 8장에서는 언어가 무엇인지, 구문을 어떻게 정의할 수 있는지 설명합니다. 언어의 구문은 각 문장이 잘 정의된 구조를 가지도록 보장함으로써 문장과 언어의 의미를 이해하고 정의하기 위한 기초를 제공합니다. 9장에서는 언어의 의미와 모호함의 문제에 대해 논의합니다.

Chapter 05 제어 구조 및 순환문: 사랑의 블랙홀
 알고리즘의 명령어에는 두 가지 종류가 있습니다. 그중 하나는 직접 데이터를 조작하기 위한 것이고 다른 하나는 다음에 수행될 명령어와 그 빈도를 결정하기 위한 것입니다. 후자의 경우를 제어 구조라고 부릅니다. 10장에서는 다양한 제어 구조를 설명하고 반복적으로 동작을 표현하는 데 사용되는 순환문을 중점적으로 살펴봅니다. 11장에서 논의할 중요한 질문은 순환문이 끝날지 혹은 영원히 반복될지의 여부와, 이것이 알고리즘에 의해 확인될 수 있는지의 여부에 관한 것입니다.

Chapter 06 재귀: 백 투 더 퓨처
 단순화된 부분으로 복잡한 시스템을 설명하거나 구현하는 프로세스인 축소의 원칙은 많은 과학 기술 분야에서 중요한 역할을 합니다. 재귀는 자기 자신을 참조하는 축소의 특수한 형태입니다. 많은 알고리즘이 재귀적입니다. 12장에서는 재귀에 대해 설명합니다. 재귀는 제어 구조이지만 데이터 구성을 정의할 때도 사용됩니다. 13장에서는 재귀를 이해하기 위한 다양한 접근법을 설명합니다.

Chapter 07 유형과 추상화: 해리 포터
 표상과 변환 방식을 분류해서 적용 가능한 변환과 적용의 의미가 없는 변환을 구분할 수 있습니다. 이러한 그룹을 유형(type)이라고 하며 변환 및 표상의 조합을 허용하는 규칙을 유형 규칙이라고 합니다. 유형 및 유형 규칙은 알고리즘 설계에 도움이 됩니다. 14장에서는 유형이 무엇인지 설명하고, 이를 사용해서 계산의 정규성을 기술하기 위한 규칙들을 만드는 방법을 설명합니다. 이러한 규칙들은 알고리즘에서 오류를 찾는 데 사용될 수 있습니다. 유형은 개별 대상의 세부 사항을 무시함으로써 더 일반적인 수준에서 규칙을 공식화할 수 있다는 데에 그 강점이 있습니다. 세부 사항을 무시하는 과정을 추상화라고 합니다. 15장에서는 왜 추상화가 컴퓨터 과학의 핵심이며 어떻게 추상화가 유형뿐만 아니라 알고리즘, 심지어 컴퓨터와 언어에 적용되는지를 살펴봅니다.

지은이 : Martin Erwig 
오리건주립대학교(Oregon State University) 전기공학 및 컴퓨터 과학과, 컴퓨터 과학 교수

옮긴이 : 송원형 

서울시립대학교 전자전기컴퓨터 학/석사 졸
삼성전자 책임연구원(현)
스탠포드 방문연구원(현)
전자 엔지니어 & 번역가
 

PART 01 알고리즘
Chapter 01 계산 및 알고리즘: 헨젤과 그레텔
01 계산을 이해하는 길
02 정말로 가 보기: 계산이 실제로 벌어질 때

Chapter 02 표상과 데이터 구조: 셜록 홈즈
03 기호의 신비
04 탐정의 수첩: 사실을 좇는 소품

Chapter 03 문제 해결과 한계: 인디아나 존스
05 완벽한 데이터 구조를 찾아서
06 좋은 정렬 방식을 골라내기
07 풀기 어려운 과제

PART 02 언어
Chapter 04 언어와 의미: 오버 더 레인보우
08 언어의 프리즘
09 딱 맞는 음 찾기: 소리의 의미

Chapter 05 제어 구조 및 순환문: 사랑의 블랙홀
10 날씨 다시 반복
11 해피엔딩은 필연이 아니다

Chapter 06 재귀: 백 투 더 퓨처
12 제때에 해 두면 제대로 풀린다
13 해석하기 나름

Chapter 07 유형과 추상화: 해리 포터
14 마법의 유형
15 조감도: 세부 사항에서 추상화하기