목차 일부
1 서론 ... 1
1.1 이 책의 소개 ... 1
1.2 수학적 분석 ... 3
1.2.1 지수 함수 ... 3
1.2.2 로그 함수 ... 3
1.2.3 급수(Series) ... 4
1.2.4 모듈러 계산법(Modular Arithmetic) ... 6
1.2.5 문자 ... 6
1...
더보기
목차 전체
1 서론 ... 1
1.1 이 책의 소개 ... 1
1.2 수학적 분석 ... 3
1.2.1 지수 함수 ... 3
1.2.2 로그 함수 ... 3
1.2.3 급수(Series) ... 4
1.2.4 모듈러 계산법(Modular Arithmetic) ... 6
1.2.5 문자 ... 6
1.3 재귀(recursion)함수 입문 ... 8
1.4 C++ 클래스 ... 12
1.4.1 기본적인 class 문법 ... 12
1.4.2 추가적인 생성자 문법과 접근자 ... 14
1.4.3 인터페이스와 구현의 분리 ... 17
1.4.4 vector와 string ... 19
1.5 C++ 세부 사항 ... 21
1.5.1 포인터 ... 21
1.5.2 매개변수 전달 ... 24
1.5.3 반환값 전달 ... 25
1.5.4 참조 변수 ... 26
1.5.5 3대 중요 요소: 소멸자, 복사 생성자, operator ... 27
1.5.6 C-스타일 배열과 문자열 ... 32
1.6 템플릿(Template) ... 33
1.6.1 함수 템플릿 ... 34
1.6.2 클래스 템플릿 ... 35
1.6.3 Object, Comparable과 예제 ... 37
1.6.4 함수 객체 ... 37
1.6.5 클래스 템플릿의 분리된 컴파일 ... 42
1.7 행렬의 사용 ... 42
1.7.1 데이터 멤버, 생성자, 기본 접근자 ... 43
1.7.2 operator[ ] ... 44
1.7.3 소멸자, 복사 할당, 복사 생성자 ... 44
1장 요약 ... 45
1장 연습문제 ... 46
1장 참고문헌 ... 49
2 알고리즘 분석 ... 51
2.1 수학적 배경지식 ... 51
2.2 모델 ... 55
2.3 분석의 대상 ... 56
2.4 실행시간 계산 ... 59
2.4.1 간단한 예제 ... 60
2.4.2 일반적인 규칙 ... 60
2.4.3 부분 수열의 최대 합 문제의 풀이 ... 63
2.4.4 로그 함수적 실행시간 ... 70
2.4.5 분석 결과의 확인 ... 74
2.4.6 비판적 분석 ... 76
2장 요약 ... 76
2장 연습문제 ... 78
2장 참고문헌 ... 86
3 리스트, 스택, 그리고 큐 ... 87
3.1 추상자료타입(ADTs) ... 87
3.2 리스트 추상자료타입 ... 88
3.2.1 배열을 이용한 리스트 ... 88
3.2.2 단순 연결 리스트 ... 89
3.3 STL에서의 벡터와 리스트 ... 91
3.3.1 Iterators ... 92
3.3.2 예 : 리스트에서 erase 사용 ... 94
3.3.3 const_iterators ... 95
3.4 벡터의 구현 ... 97
3.5 list의 구현 ... 101
3.6 스택 ADT ... 113
3.6.1 스택 모델 ... 113
3.6.2 스택 구현 ... 114
3.6.3 응용 ... 115
3.7 큐 ADT ... 123
3.7.1 큐 모델 ... 123
3.7.2 큐의 배열 구현 ... 123
3.7.3 큐의 응용 ... 126
3장 요약 ... 127
3장 연습문제 ... 128
4 트리(Trees) ... 135
4.1 개요 ... 135
4.1.1 트리의 구현 ... 137
4.1.2 응용에서의 트리 순회 ... 137
4.2 이진 트리 ... 141
4.2.1 구현 ... 142
4.2.2 수식 트리 ... 143
4.3 탐색 트리 ADT-이진 탐색 트리 ... 146
4.3.1 contains ... 147
4.3.2 findMin과 findMax ... 150
4.3.3 insert ... 152
4.3.4 remove ... 153
4.3.5 Destructor와 Copy Assignment 연산자 ... 155
4.3.6 Average Case 분석 ... 155
4.4 AVL 트리 ... 158
4.4.1 Single Rotation ... 161
4.4.2 Double Rotation ... 164
4.5 스플레이 트리 ... 171
4.5.1 간단한 아이디어(작동하지 않음) ... 172
4.5.2 스플레잉 ... 174
4.6 트리 순회(Revisited) ... 179
4.7 B-트리 ... 181
4.8 표준 라이브러리의 Sets와 Maps ... 187
4.8.1 Sets ... 187
4.8.2 Maps ... 188
4.8.3 set과 map의 구현 ... 190
4.8.4 여러 개의 map을 이용한 예 ... 190
4장 요약 ... 196
4장 연습문제 ... 197
4장 참고문헌 ... 206
5 해싱(Hashing) ... 209
5.1 일반적인 개념 ... 209
5.2 해쉬 함수 ... 210
5.3 체인법 ... 212
5.4 연결리스트를 사용하지 않는 해쉬테이블 ... 217
5.4.1 선형탐사(Linear Probing) ... 217
5.4.2 이차 탐사(Quadratic Probing) ... 219
5.4.3 Double Hashing(이중해싱) ... 225
5.5 재해싱 ... 226
5.6 표준 라이브러리에서의 해쉬 테이블 ... 229
5.7 확장가능 해싱 ... 229
5장 요약 ... 232
5장 연습문제 ... 235
5장 참고문헌 ... 240
6 우선순위 큐(Priority Queues) ... 243
6.1 모델 ... 243
6.2 간단한 구현 ... 244
6.3 이진 힙 ... 245
6.3.1 구조적 특성 ... 245
6.3.2 힙-순서 특성 ... 247
6.3.3 기본 힙 연산 ... 247
6.3.4 다른 힙 연산들 ... 252
6.4 우선순위 큐의 응용 ... 255
6.4.1 선택 문제 ... 256
6.4.2 이벤트 시뮬레이션 ... 257
6.5 d-힙 ... 258
6.6 Leftist 힙 ... 259
6.6.1 Leftist 힙의 특성 ... 260
6.6.2 Leftist 힙 연산 ... 261
6.7 Skew 힙 ... 267
6.8 이항 큐 ... 269
6.8.1 이항 큐 구조 ... 270
6.8.2 이항 큐 연산 ... 271
6.8.3 이항 큐의 구현 ... 275
6.9 표준 라이브러리에서 우선순위 큐 ... 281
6장 요약 ... 281
6장 연습문제 ... 283
6장 참고문헌 ... 290
7 정렬(Sorting) ... 293
7.1 개요 ... 293
7.2 삽입정렬(insertion sort) ... 294
7.2.1 알고리즘 ... 294
7.2.2 삽입정렬의 STL 구현 ... 295
7.2.3 삽입 정렬의 분석 ... 297
7.3 간단한 정렬 알고리즘에서의 하한(lower bound) ... 298
7.4 쉘 정렬(shellsort) ... 299
7.4.1 쉘 정렬의 최악의 경우(worst-case) 분석 ... 300
7.5 힙 정렬 ... 303
7.5.1 힙 정렬의 분석 ... 305
7.6 합병정렬 ... 308
7.6.1 합병정렬의 분석 ... 311
7.7 퀵정렬 ... 313
7.7.1 피봇의 선택 ... 314
7.7.2 분할 전략 ... 316
7.7.3 작은 배열 ... 319
7.7.4 퀵정렬 루틴 ... 319
7.7.5 퀵정렬의 분석 ... 322
7.7.6 선택을 위한 선형 기대 시간(linear-expected-time) 알고리즘 ... 325
7.8 간접 정렬(indirect sorting) ... 327
7.8.1 vector〈Comparable*〉의 무작업 ... 330
7.8.2 지능적 포인터 클래스 ... 330
7.8.3 연산자〈의 다중정의(overloading) ... 331
7.8.4 *를 가진 포인터의 역참조 ... 331
7.8.5 타입 변환 연산자의 다중정의(overloading) ... 331
7.8.6 내재된 타입 변환(implicit type conversions)은 어디에나 존재 ... 331
7.8.7 양방향 내재된 변환에 의한 모호성 야기 ... 332
7.8.8 적절한 포인터 차(pointer subtraction) ... 333
7.9 정렬에서 일반적인 하한 ... 333
7.9.1 결정 트리 ... 333
7.10 버켓 정렬(bucket sort) ... 336
7.11 외부 정렬(external sorting) ... 336
7.11.1 새로운 알고리즘이 필요한 이유 ... 336
7.11.2 외부 정렬을 위한 모델 ... 337
7.11.3 간단한 알고리즘 ... 337
7.11.4 다중 합병(multiway merge) ... 339
7.11.5 다단계 합병(polyphase merge) ... 340
7.11.6 대체 선택(replacement selection) ... 341
7장 요약 ... 342
7장 연습문제 ... 344
7장 참고문헌 ... 352
8 서로소 집합 클래스 ... 355
8.1 동치 관계(Equivalence Relations) ... 355
8.2 동적 동치 문제(Dynamic Equivalence Problem) ... 356
8.3 기본 자료 구조(Basic Data Structure) ... 358
8.4 똑똑한 결합 알고리즘(Smart Union Algorithms) ... 362
8.5 경로 압축(Path Compression) ... 365
8.6 최악의 경우의 Union-by-Rank와 경로 압축 ... 367
8.6.1 Union/Find 알고리즘의 분석 ... 367
8.7 응용 ... 374
8장 요약 ... 376
8장 연습문제 ... 378
8장 참고문헌 ... 380
9 그래프 알고리즘 ... 383
9.1 정의 ... 383
9.1.1 그래프의 표현 ... 384
9.2 위상 정렬 ... 387
9.3 최단 경로 알고리즘 ... 390
9.3.1 비가중치 최단 경로들 ... 392
9.3.2 Dijkstra의 알고리즘 ... 397
9.3.3 음의 간선 비용을 갖는 그래프 ... 404
9.3.4 비순환 그래프 ... 406
9.3.5 전쌍(all-pairs) 최단 경로 ... 409
9.3.6 최단 경로 예제 ... 409
9.4 네트워크 흐름 문제 ... 411
9.4.1 단순한 최대-흐름 알고리즘 ... 412
9.5 최소 신장 트리 ... 417
9.5.1 Prim의 알고리즘 ... 418
9.5.2. Kruskal의 알고리즘 ... 421
9.6 깊이-우선 탐색의 응용 ... 423
9.6.1 무향그래프 ... 424
9.6.2 이중 연결(biconnectivity) ... 426
9.6.3 오일러 회로(Euler circuits) ... 430
9.6.4 유향그래프(Directed Graphs) ... 433
9.6.5 강력한 컴포넌트 발견 ... 435
9.7 NP-Completeness의 소개 ... 437
9.7.1 쉬움 vs. 어려움 ... 437
9.7.2 클래스 NP ... 438
9.7.3 NP-Complete 문제 ... 439
9장 요약 ... 442
9장 연습문제 ... 443
9장 참고문헌 ... 453
10 알고리즘 설계 기법 ... 457
10.1 탐욕적 알고리즘(Greedy Algorithms) ... 457
10.1.1 간단한 스케줄링 문제(A Simple Scheduling Problem) ... 458
10.1.2 허프만 코드(Huffman Codes) ... 462
10.1.3 근사적으로 상자 채우기(Approximate Bin Packing) ... 468
10.2 분할정복(Divide and Conquer) ... 478
10.2.1 분할정복 알고리즘의 실행 시간 ... 480
10.2.2 가장 가까운 점 구하기 문제(Closest-points Problem) ... 482
10.2.3 선택 문제(The Selection Problem) ... 487
10.2.4 산술문제에 대한 이론적 개선(Theoretical improvements for Arithmetic Problems) ... 491
10.3 동적 프로그래밍(Dynamic Programming) ... 496
10.3.1 재귀 대신에 테이블의 사용 ... 496
10.3.2 행렬곱셈의 순서 ... 499
10.3.3 최적의 이진 탐색 트리 ... 502
10.3.4 전쌍최단경로(All-Pairs Shortest Path) ... 506
10.4 확률적 알고리즘(Randomized Algorithms) ... 508
10.4.1 난수 생성기(Random Number Generators) ... 510
10.4.2 스킵 리스트(Skip Lists) ... 515
10.4.3 소수 판별법(Primality Testing) ... 517
10.5 역추적 알고리즘(Backtracking Algorithms) ... 521
10.5.1 유료도로 재구성 문제(The Turnpike Reconstruction Problem) ... 521
10.5.2 게임(Games) ... 526
10장 요약 ... 534
10장 연습문제 ... 535
10장 참고문헌 ... 547
11 상환 분석 ... 553
11.1 비연관 퍼즐 ... 554
11.2 이항 큐 ... 554
11.3 기울어진 힙(Skew Heaps) ... 559
11.4 피보나치 힙 ... 562
11.4.1 좌향 힙의 노드 절단 ... 563
11.4.2 이항 큐를 위한 게으른 합병 ... 566
11.4.3 피보나치 힙 연산들 ... 569
11.4.4 시간 상한의 증명 ... 570
11.5 스프레이 트리 ... 572
11장 요약 ... 576
11장 연습문제 ... 578
11장 참고문헌 ... 581
12 고급 자료구조와 구현 ... 583
12.1 하향식 스플레이 트리(Top-down Splay Trees) ... 583
12.2 레드-블랙 트리(Red-Black Trees) ... 591
12.2.1 상향식 삽입(Bottom-Up Insertion) ... 592
12.2.2 하향식 레드-블랙 트리(Top-Down Red-Black Trees) ... 593
12.2.3 하향식 삭제 ... 599
12.3 결정적 스킵 리스트(Deterministic Skip Lists) ... 601
12.4 AA-트리(AA-trees) ... 607
12.5 트립(Treaps) ... 614
12.6 k-d 트리(k-d Trees) ... 617
12.7 페어링 힙(Pairing Heaps) ... 620
12장 요약 ... 626
12장 연습문제 ... 627
12장 참고문헌 ... 632
Appendix A 클래스 템플리트의 분리 편집 ... 635
A.1 모든 것을 헤더 안에(Everything in the Header) ... 636
A.2 명시적인 개체화(Explicit Instantiation) ... 637
A.3 Export Directive ... 638
더보기 닫기