목차
Chapter 1 서론
1. 알고리즘의 개념 = 14
2. 효율적인 알고리즘 개발의 중요성 = 15
3. 알고리즘 언어(C & C++) = 16
3.1 C = 16
1. 변수와 상수 = 16
2. 연산자 = 20
3. 제어문 = 25
4. 함수 = 27
5. 배열과 포인터 = 28
6. 구조체와 공용체 = 28
3.2 C++ = 31
1. 객체지향 프로그래밍의 소개 = 31
2. C++ 프로그램의 기본 = 33
3. Class = 37
4. 상속성과 다형성 = 43
4. 재귀(recursion) = 52
5. 알고리즘 분석과 구현 = 55
5.1 알고리즘 분석 = 55
5,2 알고리즘 구현 = 71
Chapter 2 기본적인 자료구조
1. 배열, 스택, 큐 = 80
1.1 배열(Arrays) = 80
1.2 스택 = 82
1.3 큐 = 86
2. 우선순위 = 87
2.1 힙(heap) = 90
2.2 힙 정렬(Heap Sort) = 99
2.3 간접 힙(Indirect Heaps) = 100
3. 연결 리스트 = 103
4. 트리(Tree) = 106
4.1 기본 개념 = 106
4.2 이진 트리(Binary Tree) = 110
4.3 균형트리(하향식 2-3-4 트리, Red-Black 트리) = 112
4.4 이진 트리 운행법 = 122
4.5 트리의 응용 = 124
5. 그래프 = 132
5.1 기본개념 = 132
5.2 그래프 표현 = 134
5.3 그래프의 운용 = 139
5.4 우선순위 검색 - 가중치 그래프 = 146
5.5 매칭 = 149
5.6 네트워크 흐름 = 153
6. 검색과 정렬 = 156
6.1 검색 방법 = 156
6.2 정렬 방법 = 170
6.3 외부 정렬(External Sorting) = 182
7. 해싱 = 189
7.1 기본 개념(해시함수) = 190
7.2 분리된 연쇄(Separate Chaining) = 191
7.3 선형 조사(Linear Probing) = 193
7.4 이중 해싱(Double Hashing) = 196
Chapter 3 Divide-and-Conquer 방법
1. 최소 값과 최대 값 찾기 = 200
2. 병합 정렬(MergeSort) = 205
3. 퀵 정렬(QuickSort) = 210
4. Strassen의 행렬 곱셈 = 215
5. 볼록 외곽 찾기(Finding the Convex Hull) = 219
Chapter 4 Greedy 방법
1. 테이프상의 최적 기억 장치 = 233
2. 배낭문제(Knapsack Problem) = 237
3. 데드라인을 갖는 작업 순위 = 240
4. 최적의 병합 형태 = 245
5. 최소가격 스패닝 트리(Spanning Tree) = 250
5.1 Prim의 알고리즘 = 252
5.2 Kruskal 방법(Kruskal's Method) = 256
6. 최단 경로(Shortest Path) = 260
6.1 덴스 그래프에서의 최소 스패닝 트리와 최단 경로(Minimum Spanning Tree and Shortest Paths in Dence Graphs) = 263
Chapter 5 동적 프로그래밍(Dynamic Programming)
1. 이항 계수(Binomial Coefficient) = 270
2. 다단계 그래프(Multistage Graphs) = 273
3. 최단 경로를 위한 Floyd 알고리즘 = 279
4. 최적 검색 트리(Optimal Binary Search tree) = 282
5. 연속 행렬 곱셈(Chained Matrix Product) = 287
6. 배낭(knapsack) = 295
7. 외판원 문제(The Traveling Salesperson Problem) = 299
8. 플로우 샵 스케줄링(Flow Shop Scheduling) = 304
Chapter 6 역추적과 분기-한계
1. 역추적(BACKTRACKING) = 310
1.1 N-퀸즈 문제(N-Queens Problem) = 312
1.2 그래프 컬러링(GRAPH COLORING) = 318
1.3 해밀턴 사이클 문제(Hamiltonian Cycle Problems) = 324
2. 분기-한계(BRANCH-and-BOUND) = 330
2.1 0／l 배낭 문제(The 0／1 Knapsack Problem) = 330
2.2 외판원 문제(The Traveling Salesperson Problem) = 337
2.3 TIC-TAC-TOC 게임 = 346
2.4 알파-베타 전지(Alpha-Beta Pruning) = 352
Chapter 7 문자열 처리와 기하학적 알고리즘
1. 문자열 검색 = 358
1.1 주먹구구식(Brute-Force) 알고리즘 = 358
1.2 Knuth-Moriss-Pratt 알고리즘 = 361
1.3 Boyer-Moore 알고리즘 = 365
1.4 알고리즘의 비교 = 366
2. 파싱(Parsing) = 369
2.1 파싱(Parsing)의 개요 = 369
2.2 문법(Grammars)의 형식과 분류 = 372
(1) 관용구-구조 문법(Phrase-Structure Grammar) = 372
(2) 문맥-인식 문법(Context-Sensitive Grammar) = 373
(3) 문맥-자유 문법(Context-Free Grammar) = 373
(4) 하향식 파싱(Top-Down Parsing) = 375
(5) 상향식 파싱(Bottom-Up Parsing) = 378
(6) 컴파일러(Compilers) = 379
3. 파일 압축(File Compression) = 384
3.1 반복문자열-길이의 코드화(Run-Length Encoding) = 385
3.2 가변문자-길이 코드화(Variable-Length Encoding) = 387
3.3 허프만 코드화(Huffman Encoding) = 388
4. 암호학(Cryptology) = 394
4.1 암호 시스템 = 395
4.2 Caesar 암호화 기법 = 396
4.3 Vigenere 암호화 = 397
4.4 암호 작성／해독 모델(Encryption／Descryption Model) = 398
4.5 공개키 암호화시스템(Public-Key Cryptosystems) = 399
5. 기하학적 알고리즘 = 403
5.1 볼록 외곽 찾기(Finding the Convex Hull) = 403
5.2 게임 규칙(Rules of the Game) = 405
5.3 패키지 포장(Package Wrapping) = 406
5.4 Graham 스캔(The Graham Scan) = 409
5.5 내부제거(Interior Elimination) = 412
6. 구간 검색(Range Searching) = 413
6.1 기본 방법(Elementary Methods) = 415
6.2 격자법(Grid Method) = 416
6.3 2차원 트리(Two-Dimensional Tree) = 420
6.4 다차원 구간 검색(Multidimensional Range Searching) = 424
7. 가장 인접한 점 문제들(Closet-Point Problems) = 427
7.1 가장 인접한 쌍 문제(Closest-Pair Problem) = 427
7.2 Voronoi 다이어그램(Voronoi Diagram)과 Delaunary 삼각형 = 435
8. NP-HARD와 NP-완전성 문제 = 438
8.1 결정적인 다항식-시간 알고리즘과 비결정적인 다항식-시간 알고리즘 = 439
8.2 NP-hard와 NP-완전 문제 = 440
8.3 NP-완전 문제 = 444
8.4 쿡(Cook)의 정리 = 445
8.5 그 밖의 NP-완전 문제 = 448
Chapter 8 병렬 알고리즘
1. 병렬 알고리즘의 개요 = 452
1.1 기본 개념 = 452
1.2 계산 모델 = 456
(1) SISD 컴퓨터 = 457
(2) MISD 컴퓨터 = 457
(3) SIMD 컴퓨터 = 458
(4) MIMD 컴퓨터 = 460
1.3 병렬 알고리즘 분석 = 461
(1) 가속화율(speedup ratio) = 461
(2) EPU(effective processor utilization) = 462
(3) 비용(cost) = 463
(4) 기타 방법 = 463
1.4 병렬 알고리즘 표현법 = 464
2. 병렬 알고리즘을 이용한 병합 = 465
2.1 홀수-짝수(odd-even) 병합 = 467
2.2 파이프라인(Pipeline)상에서의 병합 = 470
3. 병렬 알고리즘을 이용한 정렬 = 473
3.1 퀵 정렬(Quicksort) = 473
3.2 비동기식 퀵정렬(Asychronous Quicksort) = 475
4. 시스톨릭 배열(Systolic Array) = 478
5. Enumeration 분류 = 481
6. odd-even 전송 분류 = 486
7. 병렬 heap 병합 알고리즘 = 489
7.1 크기가 같은 경우의 병합 = 489
7.2 크기가 다른 경우의 병합 = 490
7.3 LEVEL-FIND 알고리즘 = 492
(1) nheap가 완전 heap인 경우 = 493
(2) nheap가 불완전 heap인 경우 = 494
7.4 병합 알고리즘 = 495
(1) PE(i)의 해당 subheap 할당 방법 = 496
(2) 병합 알고리즘 기법 = 498
7.5 알고리즘 분석과 비교 = 500
(1) 프로세서 수 = 500
(2) 시간 복잡도 = 501
(3) 공간 복잡도 = 501
찾아보기 = 504
