목차

역자 서문………………………………………………………………. xiii
서문 ……………………………………………………………………. xv
감사의 글……………………………………………………………….xvii
1장 소개 1
1.1 변수…………………………………………………………………….1
1.2 데이터형………………………………………………………………..2
1.3 데이터 구조…………………………………………………………….3
1.4 추상 데이터형 …………………………………………………………4
1.5 알고리즘이란 무엇인가?……………………………………………….5
1.6 왜 알고리즘을 분석하는가?……………………………………………5
1.7 알고리즘 정렬의 목적………………………………………………….6
1.8 수행 시간 분석이란 무엇인가?…………………………………………6
1.9 어떻게 알고리즘을 비교하는가?……………………………………….6
1.10 증가율이란 무엇인가?………………………………………………..7
1.11 많이 사용되는 증가율………………………………………………..7
1.12 분석의 종류…………………………………………………………..9
1.13 점근적 표기법………………………………………………………. 10
1.14 빅-오 표기법……………………………………………………….. 10
1.15 오메가 표기법………………………………………………………. 13
1.16 세타 표기법………………………………………………………… 14
1.17 중요 사항…………………………………………………………… 15
1.18 왜 점근적 분석이라고 불리는가?…………………………………… 16
1.19 점근적 분석 가이드라인……………………………………………. 16
1.20 각 표기법의 특성…………………………………………………… 18
1.21 자주 사용되는 로그 함수와 급수………………………………….. 19
1.22 분할 정복을 위한 마스터 정리…………………………………….. 20
1.23 분할 정복 마스터 정리 연습문제…………………………………… 20
1.24 차감 정복 점화식을 위한 마스터 정리…………………………….. 23
1.25 차감 정복 마스터 정리의 변형……………………………………… 23
1.26 상각 분석…………………………………………………………… 23
1.27 상각 분석 연습문제………………………………………………… 24
2장 재귀와 백트래킹 41
2.1 소개…………………………………………………………………. 41
2.2 재귀란 무엇인가?……………………………………………………. 41
2.3 왜 재귀를 사용하는가?……………………………………………… 42
2.4 재귀 함수의 형식……………………………………………………. 42
2.5 재귀와 메모리(시각화)……………………………………………… 43
2.6 재귀와 반복 비교……………………………………………………. 44
2.7 재귀에 대한 참고 사항………………………………………………. 45
2.8 재귀 알고리즘의 예………………………………………………….. 45
2.9 재귀 연습문제……………………………………………………….. 46
2.10 백트래킹은 무엇인가?……………………………………………… 47
2.11 백트래킹 알고리즘의 예……………………………………………. 47
2.12 백트래킹 연습문제…………………………………………………. 48
3장 연결 리스트 51
3.1 연결 리스트란 무엇인가?……………………………………………. 51
3.2 연결 리스트 ADT……………………………………………………. 52
3.3 왜 연결 리스트를 사용하는가?……………………………………… 52
3.4 배열 개요……………………………………………………………. 52
3.5 연결 리스트와 배열 그리고 동적 배열의 비교………………………. 55
3.6 단일 연결 리스트……………………………………………………. 55
3.7 이중 연결 리스트……………………………………………………. 63
3.8 원형 연결 리스트……………………………………………………. 70
3.9 메모리-효율적인 이중 연결 리스트………………………………….. 78
3.10 연결 리스트 연습문제……………………………………………… 81
4장 스택 107
4.1 스택이란 무엇인가?…………………………………………………107
4.2 스택은 어떻게 사용되는가?…………………………………………108
4.3 스택 ADT……………………………………………………………108
4.4 예외들……………………………………………………………….109
4.5 스택의 적용 사례……………………………………………………109
4.6 스택의 구현………………………………………………………… 110
4.7 각 구현 방법의 비교………………………………………………… 116
4.8 스택 연습문제………………………………………………………. 117
5장 큐 149
5.1 큐란 무엇인가?………………………………………………………149
5.2 큐는 어떻게 사용되는가?…………………………………………… 150
5.3 큐 ADT…………………………………………………………….. 150
5.4 예외들………………………………………………………………. 151
5.5 큐의 적용 사례들…………………………………………………… 151
5.6 큐의 구현…………………………………………………………… 151
5.7 큐 연습문제………………………………………………………… 158
6장 트리 165
6.1 트리란 무엇인가?…………………………………………………… 165
6.2 용어 설명……………………………………………………………166
6.3 이진 트리……………………………………………………………… 167
6.4 이진 트리 탐색……………………………………………………… 171
6.5 범용 트리(N항 트리)………………………………………………..203
6.6 스레드 이진 트리 탐색……………………………………………… 213
6.7 수식 트리…………………………………………………………… 222
6.8 XOR 트리…………………………………………………………… 225
6.9 이진 검색 트리………………………………………………………227
6.10 균형 이진 검색 트리………………………………………………..249
6.11 AVL 트리…………………………………………………………..250
6.12 기타 트리의 변형들………………………………………………..263
7장 우선순위 큐와 힙 269
7.1 우선순위 큐란 무엇인가?……………………………………………269
7.2 우선순위 큐 ADT……………………………………………………270
7.3 우선순위 큐의 적용…………………………………………………270
7.4 우선순위 큐의 구현………………………………………………… 271
7.5 힙과 이진 힙…………………………………………………………273
7.6 이진 힙………………………………………………………………274
7.7 우선순위 큐와 힙 연습문제…………………………………………283
8장 분리집합 ADT 299
8.1 소개…………………………………………………………………299
8.2 동치 관계와 동치 류………………………………………………..299
8.3 부분집합 ADT……………………………………………………… 301
8.4 적용 사례…………………………………………………………… 301
8.5 분리집합 ADT 구현에서의 타협점들………………………………. 301
8.6 빠른 UNION 구현(느린 FIND)……………………………………..303
8.7 빠른 UNION 구현(빠른 FIND)……………………………………..307
8.8 경로 압축…………………………………………………………… 310
8.9 요약………………………………………………………………… 311
8.10 분리집합 연습문제………………………………………………… 312
9장 그래프 알고리즘 315
9.1 소개………………………………………………………………… 315
9.2 용어………………………………………………………………… 315
9.3 그래프의 적용 사례…………………………………………………320
9.4 그래프의 표현……………………………………………………….320
9.5 그래프 탐색…………………………………………………………324
9.6 위상 정렬 ………………………………………………………….. 335
9.7 최단 경로 알고리즘…………………………………………………337
9.8 최소 신장 트리………………………………………………………346
9.9 그래프 알고리즘 연습문제…………………………………………. 353
10장 정렬 387
10.1 정렬은 무엇인가?…………………………………………………..387
10.2 왜 정렬하는가?…………………………………………………….387
10.3 분류………………………………………………………………..387
10.4 다른 분류………………………………………………………….389
10.5 버블 정렬…………………………………………………………..389
10.6 선택 정렬………………………………………………………….. 391
10.7 삽입 정렬…………………………………………………………..392
10.8 쉘 정렬 …………………………………………………………….395
10.9 병합 정렬 ………………………………………………………….397
10.10 힙 정렬 ……………………………………………………………399
10.11 퀵 정렬 ……………………………………………………………400
10.12 트리 정렬 …………………………………………………………404
10.13 정렬 알고리즘 비교……………………………………………….405
10.14 선형 정렬 알고리즘 ………………………………………………405
10.15 계수 정렬 …………………………………………………………406
10.16 버킷 정렬………………………………………………………….407
10.17 기수 정렬………………………………………………………….407
10.18 위상 정렬………………………………………………………….408
10.19 외부 정렬 …………………………………………………………409
10.20 정렬 연습문제……………………………………………………. 410
11장 검색 427
11.1 검색은 무엇인가?…………………………………………………..427
11.2 왜 검색을 하는가?………………………………………………….427
11.3 검색의 종류………………………………………………………..428
11.4 심볼 테이블과 해싱………………………………………………..430
11.5 문자열 검색 알고리즘……………………………………………… 431
11.6 검색 연습문제……………………………………………………… 431
12장 선택 알고리즘 467
12.1 선택 알고리즘은 무엇인가?………………………………………..467
12.2 정렬에 의한 선택…………………………………………………..467
12.3 분할에 기반한 선택 알고리즘……………………………………..468
12.4 선형 선택 알고리즘 – 중간값의 중간값 알고리즘………………….468
12.5 정렬된 순서에서 K개의 작은 항목들을 찾기………………………468
12.6 선택 알고리즘 연습문제……………………………………………468
13장 심볼 테이블 485
13.1 소개………………………………………………………………..485
13.2 심볼 테이블이란 무엇인가?………………………………………..486
13.3 심볼 테이블의 구현………………………………………………..486
13.4 심볼 테이블 구현의 비교…………………………………………..488
14장 해싱 489
14.1 해싱이란 무엇인가?………………………………………………..489
14.2 왜 해싱을 하는가?………………………………………………….489
14.3 해시 테이블 ADT…………………………………………………..489
14.4 해싱을 이해하기……………………………………………………490
14.5 해싱의 구성 요소…………………………………………………..492
14.6 해시 테이블………………………………………………………..492
14.7 해시 함수…………………………………………………………..492
14.8 적재율……………………………………………………………..493
14.9 충돌………………………………………………………………..494
14.10 충돌 해결 기법들………………………………………………….494
14.11 분리 체인법……………………………………………………….494
14.12 개방 번지화……………………………………………………….495
14.13 충돌 해결 기법의 비교…………………………………………….498
14.14 어떻게 해싱이 O(1) 복잡도를 갖는가?……………………………499
14.15 해싱 기법들……………………………………………………….499
14.16 어떤 해시 테이블이 적합하지 않은가의 문제……………………..500
14.17 해싱 연습문제…………………………………………………….500
15장 문자열 알고리즘 515
15.1 소개……………………………………………………………….. 515
15.2 문자열 매칭 알고리즘…………………………………………….. 516
15.3 브루트-포스 기법………………………………………………….. 516
15.4 라빈-카프 문자열 매칭 알고리즘 …………………………………. 517
15.5 유한 오토마타 문자열 매칭……………………………………….. 519
15.6 KMP 알고리즘…………………………………………………….. 521
15.7 보이어-무어 알고리즘………………………………………………526
15.8 문자열 저장을 위한 데이터 구조…………………………………..527
15.9 문자열을 위한 해시 테이블………………………………………..527
15.10 문자열을 위한 이진 검색 트리…………………………………….528
15.11 트라이…………………………………………………………….528
15.12 삼진 검색 트리…………………………………………………… 532
15.13 접미어 트리 ………………………………………………………538
15.14 문자열 연습문제………………………………………………….543
16장 알고리즘 디자인 기법 555
16.1 소개……………………………………………………………….. 555
16.2 분류……………………………………………………………….. 555
16.3 구현 기법에 의한 분류…………………………………………….. 556
16.4 디자인 기법에 의한 분류………………………………………….. 557
16.5 기타 분류…………………………………………………………..558
17장 탐욕 알고리즘 561
17.1 소개……………………………………………………………….. 561
17.2 탐욕 전략………………………………………………………….. 561
17.3 탐욕 알고리즘의 항목……………………………………………..562
17.4 탐욕 알고리즘이 항상 동작하는가?……………………………….562
17.5 탐욕 기법의 장점과 단점…………………………………………..562
17.6 탐욕 기법의 적용 사례……………………………………………..563
17.7 탐욕 기법 이해하기………………………………………………..563
17.8 탐욕 알고리즘 연습문제…………………………………………..568
18장 분할 정복 알고리즘 581
18.1 소개……………………………………………………………….. 581
18.2 분할 정복 전략이란 무엇인가?……………………………………. 581
18.3 분할 정복이 언제나 성공하는가?………………………………….582
18.4 분할 정복 시각화………………………………………………….582
18.5 분할 정복 이해하기………………………………………………..583
18.6 마스터 정리………………………………………………………..585
18.7 분할 정복의 적용 사례…………………………………………….585
18.8 분할 정복 연습문제………………………………………………..586
19장 동적 계획법 607
19.1 소개………………………………………………………………..607
19.2 동적 계획법 전략이란 무엇인가?…………………………………..607
19.3 동적 계획법 전략의 속성들?……………………………………….608
19.4 동적 계획법이 어떤 문제라도 풀 수 있는가?………………………608
19.5 동적 계획법 접근…………………………………………………..608
19.6 동적 계획법 알고리즘의 예…………………………………………609
19.7 동적 계획법 이해하기……………………………………………… 610
19.8 동적 계획법 연습문제……………………………………………… 619
20장 복잡도 클래스 667
20.1 소개………………………………………………………………..667
20.2 다항적/지수적 시간………………………………………………..668
20.3 결정 문제란 무엇인가?…………………………………………….668
20.4 결정 절차 ………………………………………………………….669
20.5 복잡도 클래스란 무엇인가?……………………………………….669
20.6 복잡도 클래스의 종류……………………………………………..669
20.7 환원………………………………………………………………..673
20.8 복잡도 클래스 연습문제…………………………………………..678
21장 기타 개념들 683
21.1 소개………………………………………………………………..683
21.2 비트 연산 프로그래밍 공략………………………………………..683
21.3 기타 프로그래밍 연습문제………………………………………… 691
참고 도서……………………………………………………………….694
찾아보기………………………………………………………………..697