목차
Chapter 1 알고리즘의 개요 = 11
1-1 알고리즘 = 12
(1) 알고리즘의 정당성 = 14
(2) 정당성의 증명법 = 16
1-2 복잡도 = 17
(1) 점근적인 복잡도 평가 = 21
(2) Ο와 Ω표기법 = 23
(3) 점근적인 복잡도의 중요성 = 24
(4) 각종 복잡도의 정의 = 26
(5) 알고리즘의 선택 = 28
1-3 자료 구조 = 30
(1) 배열 = 31
(2) 리스트 = 33
(3) 스택과 큐 = 38
(4) 트리(tree) = 41
연습문제 = 46
Chapter 2 탐색 알고리즘 = 47
2-1 선형 탐색 = 49
(1) 선형 탐색 알고리즘 = 50
(2) 개량 알고리즘 = 53
2-2 이진 탐색 = 55
(1) 탐색 알고리즘 = 56
(2) 삽입 알고리즘 = 60
2-3 이진 탐색트리 = 62
(1) 탐색 알고리즘 = 65
(2) 삽입 알고리즘 = 66
(3) 삭제 알고리즘 = 74
2-4 균형트리 = 76
(1) 삽입 알고리즘 = 78
(2) 삭제 알고리즘 = 82
2-5 B트리 = 87
(1) 탐색 알고리즘 = 92
(2) 삽입 알고리즘 = 92
(3) 삭제 알고리즘 = 94
2-6 $$B^+$$트리와 $$B^*$$트리 = 97
2-7 해시법 = 99
(1) 해시 함수 = 102
(2) 충돌 처리 기법 = 106
연습문제 = 114
Chapter 3 정렬 알고리즘 = 117
3-1 단순한 정릴 알고리즘 = 119
(1) 선택법 = 122
(2) 삽입 정렬 = 124
3-2 비교 정렬의 하한 = 127
3-3 셀 정렬 알고리즘 = 129
3-4 퀵 정렬 알고리즘 = 135
3-5 히프 정렬 알고리즘 = 144
3-6 합병 정렬 알고리즘 = 152
3-7 분배 정렬 알고리즘 = 158
(1) 빈 정렬 = 158
(2) 기수 정렬 = 161
3-8 외부 정렬 알고리즘 = 164
(1) 자연 합병 정렬 = 165
(2) 균형 합병 정렬 = 165
(3) 다단계 합병 = 168
(4) 케스케이트 합병 정렬 = 171
(5) 진동 정렬 = 172
연습문제 = 176
Chapter 4 그래프 알고리즘 = 179
4-1 그래프 탐색 문제 = 190
(1) 깊이 우선 탐색 알고리즘 = 191
(2) 깊이 우선 탐색의 응용 예 = 196
(3) 폭 우선 탐색 알고리즘 = 198
4-2 각종 결합성 판정 문제 = 201
(1) 이중 결합성 판정 알고리즘 = 202
(2) 절단점 및 이중 결합 요소 판정 알고리즘 = 203
(3) 강결합성 판정 알고리즘 = 208
(4) 강결합 요소 판정 알고리즘 = 209
4-3 최단 경로 문제 = 215
(1) 단일점 출발 문제의 알고리즘 = 216
(2) Dijkstra 알고리즘의 실현법 = 220
(3) 모든 정점 출발점 문제의 알고리즘 = 225
4-4 최소목 구성 문제 = 230
(1) Prim 알고리즘 = 231
(2) Kruskal 알고리즘 = 233
4-5 매칭 문제 = 241
4-6 최대 플로 문제 = 245
4-7 그 외의 그래프 문제 = 252
(1) 연결도 문제 = 252
(2) 오일러 경로와 해밀턴 폐로 문제 = 253
(3) 변 채색과 정점 채색 문제 = 254
(4) 평면성 판정 문제 = 255
(5) 동형성 판정 문제 = 255
연습문제 = 257
Chapter 5 문자열 알고리즘 = 259
5-1 간단한 매칭 알고리즘 = 261
5-2 Knuth-Morris-Pratt 알고리즘 = 264
5-3 Boyer-Moore 알고리즘 = 267
(1) 테크닉 1 = 268
(2) 테크닉 2 = 273
연습문제 = 281
Chapter 6 알고리즘의 설계 기법 = 283
6-1 분할 통치법 = 284
6-2 균형법 = 290
6-3 동적 계획법 = 291
6-4 탐욕법 = 301
6-5 백트랙킹법 = 305
6-6 NP완전 문제의 해법 = 308
연습문제 = 316
Chapter 7 병렬 알고리즘 = 317
7-1 PRAM 모델 = 319
(1) 최대값 계산 문제 = 320
(2) 연결 성분 판정 문제 = 324
7-2 1차원 배열 구조 = 333
7-3 트리 구조 = 337
7-4 정렬용 네트워크 = 341
(1) 합병 네트워크 = 342
(2) 쌍단조 네트워크 = 345
연습문제 = 351
Chapter 8 분산 알고리즘 = 353
8-1 리더 선택 분산 알고리즘 = 356
8-2 깊이 우선 생성목 구성 분산 알고리즘 = 360
8-3 폭 우선 생성목 구성 분산 알고리즘 = 363
8-4 생성목 갱신 분산 알고리즘 = 366
8-5 최소목 갱신 분산 알고리즘 = 368
8-6 그 외의 분산 알고리즘 = 371
연습문제 = 374
부록 = 375
찾아보기 = 413
