목차 일부

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

더보기 닫기