책소개
 
 자료구조의 이해 + 알고리즘의 설계/분석 + 재귀적/귀납적 사고방식의 훈련= 문제 해결 기법의 훈련

알고리즘 입문서. 이 책은 알고리즘 설계와 분석의 기초부터 점화식과 점근적 복잡도 분석, 정렬과 선택 알고리즘, 해시테이블, 동적 프로그래밍과 상태공간 트리 탐색까지 이해하기 쉽게 설명한다.

목차
 
 1장. 알고리즘 설계와 분석의 기초
01. 몇 가지 기초 사항들
1.1 알고리즘이란
1.2 알고리즘을 왜 분석하는가
1.3 알고리즘의 수행 시간
1.4 재귀(자기호출)와 귀납적 사고
1.5 알고리즘으로 어떤 문제를 푸는가
[알고리즘 1-1] 병합정렬
02. 점근적 표기
2.1 θ-표기법
2.2 O-표기법
2.2 Ω-표기법
☆03. 점근적 표기의 엄밀한 정의
3.1 O-표기법
3.2 Ω-표기법
3.3 θ-표기법
3.4 ο-표기법
3.5 ω-표기법
요약
연습문제
[Drift] 에너지의 천재 크누스

2장. 점화식과 점근적 복잡도 분석
01. 점화식의 이해
02. 점화식의 점근적 분석 방법
2.1 반복대치
2.2 추정후 증명
2.3 마스터 정리
요약
연습문제

3장. 정렬
01. 기초적인 정렬 알고리즘
1.1 선택정렬
1.2 버블정렬
1.3 삽입정렬
[알고리즘 3-1] 선택정렬
[알고리즘 3-2] 버블정렬
[알고리즘 3-3] 삽입정렬
02. 고급 정렬 알고리즘
2.1 병합정렬
2.2 퀵정렬
2.3 힙정렬
[알고리즘 3-4] 병합정렬
[알고리즘 3-5] 퀵정렬
[알고리즘 3-6] 힙만들기
[알고리즘 3-7] 힙정렬
03. 비교정렬 시간의 하한
04. 특수 정렬 알고리즘
4.1 기수정렬
4.2 계수정렬
[알고리즘 3-8] 기수정렬
[알고리즘 3-9] 계수정렬
요약
연습문제
[Drift] 관계 중심의 사고 방식

4장. 선택 알고리즘
01. 평균 선형시간 선택 알고리즘
[알고리즘 4-1] 평균 선형시간 선택 알고리즘
02. 최악의 경우 선형시간 선택 알고리즘
[알고리즘 4-2] 최악의 경우 선형시간 선택 알고리즘
요약
연습문제

5장. 검색트리
01. 레코드, 키의 정의 및 검색트리
02. 이진검색트리
2.1 이진검색트리에서의 검색
2.2 이진검색트리에서의 삽입
2.3 이진검색트리에서의 삭제
[알고리즘 5-1] 이진검색트리에서의 검색
[알고리즘 5-2] 이진검색트리에서의 삽입
[알고리즘 5-2b] 이진검색트리에서의 삽입(비재귀적 버전)
[알고리즘 5-3] 이진검색트리에서의 삭제
03. 레드블랙트리
3.1 레드블랙트리에서의 삽입
3.2 레드블랙트리에서의 삭제
3.3 레드블랙트리의 작업 성능 분석
04. B-트리
4.1 B-트리에서의 검색
4.2 B-트리에서의 삽입
4.3 B-트리에서의 삭제
4.4 B-트리의 작업 성능 분석
[스케치 5-4] B-트리에서의 삽입
[스케치 5-5] B-트리에서의 삭제
☆05. 다차원검색트리
5.1 KD-트리
5.2 KDB-트리
5.3 R-트리
5.4 그리드 파일
요약
연습문제
[Drift] 천재 알고리즘의 재현: 스트라센 알고리즘의 재고

6장. 해시 테이블
01. 해시 테이블: 검색 효율의 극단
02. 해시 함수
2.1 나누기 방법
2.2 곱하기 방법
03. 충돌 해결
3.1 체이닝
3.2 개방 주소 방법
[알고리즘 6-1] 체이닝을 사용하는 해시 테이블에서의 작업
[알고리즘 6-2] 개방주소 방법
04. 해시 테이블에서의 검색 시간 분석
요약
연습문제

7장. 상호 배타적 집합의 처리
01. 연결 리스트를 이용한 집합의 처리
1.1 작업의 개요
1.2 수행시간
02. 트리를 이용한 집합의 처리
2.1 기본적인 원리
2.2 연산의 효율을 높이는 방법
[알고리즘 7-1] 트리를 이용한 집합의 처리에서의 Make-Set, Union, Find-Set
[알고리즘 7-2] 랭크를 이용한 Union과 Make-Set
[알고리즘 7-3] 경로압축을 이용한 Find-Set
요약
연습문제
[Drift] 추상화와 은유

8장. 동적 프로그래밍
01. 어떤 문제를 동적 프로그래밍으로 푸는가
[알고리즘 8-1] 피보나치 수(재귀호출)
[알고리즘 8-2] 피보나치 수(동적 프로그래밍 1)
[알고리즘 8-3] 피보나치 수(동적 프로그래밍 2)
02. 행렬 경로 문제
[알고리즘 8-4] 행렬 경로 문제(재귀호출)
[알고리즘 8-5] 행렬 경로 문제(동적 프로그래밍)
03. 조약돌 놓기 문제
[알고리즘 8-6] 조약돌 놓기 문제(재귀호출)
[알고리즘 8-7] 조약돌 놓기 문제(동적 프로그래밍)
04. 행렬 곱셈 순서 문제
[알고리즘 8-8] 행렬 곱셈 순서 문제(재귀호출)
[알고리즘 8-9] 행렬 곱셈 순서 문제(동적 프로그래밍)
05. 최장 공통 부분순서(LCS)
[알고리즘 8-10] 최장 공통 부분순서 길이(재귀호출)
[알고리즘 8-11] 최장 공통 부분순서 길이(동적 프로그래밍)
요약
연습문제

9장. 그래프 알고리즘
01. 그래프
02. 그래프의 표현
2.1 인접행렬을 이용한 방법
2.2 인접리스트를 이용한 방법
03. 너비우선탐색(BFS)과 깊이우선탐색(DFS)
[알고리즘 9-1] BFS 알고리즘
[알고리즘 9-2] DFS 알고리즘
04. 최소신장트리
4.1 프림 알고리즘
4.2 크루스칼 알고리즘
4.3 안정성 정리
[알고리즘 9-3] 프림 알고리즘(버전 1)
[알고리즘 9-4] 프림 알고리즘(버전 2)
[알고리즘 9-5] 크루스칼 알고리즘
05. 위상 정렬
[알고리즘 9-6] 위상정렬 알고리즘 1
[알고리즘 9-7] 위상정렬 알고리즘 2
06. 최단경로
6.1 다익스트라 알고리즘(음의 가중치를 허용하지 않는 경우)
6.2 벨만-포드 알고리즘
6.3 모든쌍 최단경로 알고리즘
6.4 싸이클이 없는 그래프의 최단경로
[알고리즘 9-8] 다익스트라 알고리즘
[알고리즘 9-9] 벨만-포드 알고리즘
[알고리즘 9-10] 플로이드-워샬 알고리즘
[알고리즘 9-11] 싸이클이 없는 유향 그래프(DAG)에서 최단경로 구하기
07. 강연결 요소
[알고리즘 9-12] 강연결요소 구하기
요약
연습문제

10장. 문자열 매칭
01. 원시적인 매칭 방법
[알고리즘 10-1] 원시적인 매칭 알고리즘
02. 오토마타를 이용한 매칭
[알고리즘 10-2] 매칭을 체크하는 알고리즘
03. 라빈-카프 알고리즘
[알고리즘 10-3] 수치화를 이용한 매칭 알고리즘
[알고리즘 10-4] 라빈-카프 매칭 알고리즘
☆04. KMP 알고리즘
[알고리즘 10-5] KMP 알고리즘
☆05. 보이어-무어 알고리즘
[알고리즘 10-5] 약식 보이어-무어 알고리즘
요약
연습문제

11장. NP-완비
01. 문제의 종류
02. Yes/No 문제와 최적화 문제
03. NP
04. 변환
05. NP-완비
06. NP-완비 문제들
07. NP-하드를 최적화 문제로 확장하기
☆08_근사해 구하기
요약
연습문제
[Drift] 비운의 천재 알란 튜링과 정지문제

12장. 상태공간 트리의 탐색
01. 상태공간 트리
02. 백트래킹
2.1 미로 찾기 문제
2.2 색칠 문제
[알고리즘 12-1] 미로 찾기 문제를 위한 백트래킹 알고리즘
[알고리즘 12-2] 색칠 문제를 위한 백트래킹 알고리즘
03. 한정분기
04. A* 알고리즘
4.1 최단 경로 찾기 문제
4.2 TSP
[알고리즘 12-3] 그래프에서 최단경로를 찾기 위한 A* 알고리즘
요약
연습문제
[Drift] 공간 탐색과 끌개

참고문헌
찾아보기