목차 일부

역자 서문 ... ⅴ
저자 서문 ... xxⅲ
Ⅰ부. 기초
   개요 ... 3
   1장. 알고리즘의 역활
      1.1 알고리즘 ... 5
      1.2 기술로서의 알고리즘 ... 10
   2장. 시작하기
      2.1 삽입정렬 ... 15
      2.2 알고리즘 분석하기 ... 21
      2.3 알고리즘 설계하기 ... 28
  ...

더보기

목차 전체

역자 서문 ... ⅴ
저자 서문 ... xxⅲ
Ⅰ부. 기초
   개요 ... 3
   1장. 알고리즘의 역활
      1.1 알고리즘 ... 5
      1.2 기술로서의 알고리즘 ... 10
   2장. 시작하기
      2.1 삽입정렬 ... 15
      2.2 알고리즘 분석하기 ... 21
      2.3 알고리즘 설계하기 ... 28
   3장. 함수의 증가
      3.1 점근적 표기 ... 43
      3.2 표준 표기법과 흔히 사용하는 함수들 ... 54
   4장. 점화식
      4.1 치환법 ... 67
      4.2 재귀 트리 방법 ... 72
      4.3 마스터 방법 ... 77
      4.4 마스터 정리의 증명 ... 80
   5장. 확률적 분석, 랜덤화된 알고리즘
      5.1 고용 문제 ... 97
      5.2 지표 확률 변수 ... 101
      5.3 랜덤화된 알고리즘 ... 105
      5.4 확률적 분석과 지표 확률 변수의 부가적인 활용 ... 112
Ⅱ. 정렬과 순서 통계량
   개요 ... 129
   6장. 힙 정렬
      6.1 힙 ... 133
      6.2 힙 특성 유지하기 ... 136
      6.3 힙 만들기 ... 139
      6.4 힙 정렬 알고리즘 ... 142
      6.5 우선순위 큐 ... 144
   7장. 퀵 정렬
      7.1 퀵 정렬 ... 152
      7.2 퀵 정렬의 성능 ... 156
      7.3 랜덤화된 퀵 정렬 ... 161
      7.4 퀵 정렬 분석 ... 162
   8장. 선형 시간 정렬
      8.1 정렬의 하한 ... 173
      8.2 계수 정렬 ... 176
      8.3 기수 정렬 ... 179
      8.4 버킷 정렬 ... 182
   9장. 중앙값과 순서 통계량
      9.1 최소값과 최대값 ... 193
      9.2 평균적으로 선형 시간에 선택하기 ... 194
      9.3 최악의 경우에도 선형 시간에 선택하기 ... 198
Ⅲ부. 자료구조
   개요 ... 207
   10장. 기본 자료구조
      10.1 스택과 큐 ... 211
      10.2 연결 리스트 ... 215
      10.3 포인터와 객체의 구현 ... 220
      10.4 루트있는 트리의 표현 ... 225
   11장. 해시 테이블
      11.1 직접 번지 테이블 ... 234
      11.2 해시 테이블 ... 236
      11.3 해시 함수 ... 242
      11.4 개방 번지화 방법 ... 250
      11.5 완전 해싱 ... 259
   12장. 이진 검색 트리
      12.1 이진 검색 트리란 ... 268
      12.2 이진 검색 트리에 대한 질의 ... 271
      12.3 삽입과 삭제 ... 275
      12.4 임의로 만들어진 이진 검색 트리 ... 279
   13장. 레드블랙 트리
      13.1 레드블랙 트리의 특성 ... 289
      13.2 회전 ... 294
      13.3 삽입 ... 296
      13.4 삭제 ... 305
   14장. 자료구조의 확정
      14.1 동적 순서 통계량 ... 320
      14.2 자료구조 확정 기법 ... 327
      14.3 구간 트리 ... 330
Ⅳ부. 고급 설계 및 분석 기법
   개요 ... 341
   15장. 동적 프로그래밍
      15.1 조립 라인 스케줄링 ... 344
      15.2 행렬-체인 곱 ... 352
      15.3 동적 프로그래밍의 요소 ... 360
      15.4 최대 공통 부분 수열 ... 372
      15.5 최적 이진 검색 트리 ... 378
   16장. 그리디 알고리즘
      16.1 활동 선택 문제 ... 395
      16.2 그리디 방법의 요소들 ... 405
      16.3 허프만 코드 ... 410
      16.4 그리디 방법의 이론적 기반 ... 420
      16.5 일정 짜기 문제 ... 427
   17장. 분할상환 분석
      17.1 총계 분석 ... 436
      17.2 결산 방법 ... 440
      17.3 잠재비용 방법 ... 443
      17.4 동적 테이블 ... 448
Ⅴ부. 고급 자료 구조
   개요 ... 465
   18장. B-트리
      18.1 B-트리의 정의 ... 472
      18.2 B-트리의 기본적인 연산 ... 475
      18.3 B-트리에서 키 삭제하기 ... 484
   19장. 이항 힙
      19.1 이항 트리와 이항 힙 ... 493
      19.2 이항 힙의 연산 ... 498
   20장. 피보나치 힙
      20.1 피보나치 힙의 구조 ... 514
      20.2 병합 가능한 힙의 연산 ... 517
      20.3 키 감소시키기와 노드 삭제하기 ... 526
      20.4 최대 차수의 한계 정하기 ... 531
   21장. 서로 소 집합의 자료구조
      21.1 서로 소 집합의 연산 ... 537
      21.2 소로 소 집합의 연결 리스트를 이용한 표현 ... 540
      21.3 서로 소 집합 포리스트 ... 545
      21.4 결로 압축을 이용한 순위에 의한 합병의 분석 ... 549
Ⅵ부. 그래프 알고리즘
   개요 ... 567
   22장. 기초적인 그래프 알고리즘
      22.1 그래프의 표현 ... 569
      22.2 너비 우선 검색 ... 573
      22.3 깊이 우선 검색 ... 583
      22.4 위상 정렬 ... 594
      22.5 강한 연결 요소 ... 597
   23장. 최소 신장 트리
      23.1 최소 신장 트리 확장하기 ... 608
      23.2 크루스칼과 프림 알고리즘 ... 614
   24장. 단일 출발지 최단 경로
      24.1 벨만-포드 알고리즘 ... 635
      24.2 비순환 뱡향 그래프에서의 단일 출발전 최단 경로 ... 640
      24.3 다익스트라 알고리즘 ... 643
      24.4 차이 제약 사항과 최단 경로 ... 649
      24.5 최단 경로의 특성 증명 ... 656
   25장. 모든 쌍의 최단 경로
      25.1 최단 경로의 행렬 곱 ... 673
      25.2 플로이드-위샬 알고리즘 ... 680
      25.3 희소 그래프에 대한 존슨 알고리즘 ... 688
   26장. 최대 플로우
      26.1 플로우 네트워크 ... 697
      26.2 포트-풀커슨 방법 ... 704
      26.3 최대 이분 대칭 ... 719
      26.4 푸시-재명명 알고리즘 ... 725
      26.5 재명명후-앞보내기 알고리즘 ... 739
Ⅶ부. 알고리즘 분야의 중요한 토픽
   개요 ... 765
   27장. 정렬 네트워크
      27.1 비교 네트워크 ... 764
      27.2 제로-원 원리 ... 769
      27.3 바이토닉 정렬 네트워크 ... 772
      27.4 병합 네트워크 ... 777
      27.5 정렬 네트워크 ... 779
   28장. 행렬 연산
      28.1 행렬의 특성 ... 786
      28.2 행렬의 곱에 대한 스트라센 알고리즘 ... 797
      28.3 선형 연립 방정식의 해 ... 804
      28.4 역 행렬 ... 819
      28.5 대칭이고 양이고-정의된 행렬과 최소-제곱 근사값 ... 824
   29장. 선형 계획법
      29.1 정규형과 이완형 ... 843
      29.2 문제를 선형 계획법으로 구성하기 ... 852
      29.3 심플렉스 알고리즘 ... 875
      29.4 쌍대성 ... 873
      29.5 초기 가능한 기본 해 ... 879
   30장. 다항식과 FFT
      30.1 다항식의 표현 ... 893
      30.2 DFT와 FFT ... 900
      30.3 효율적인 FFT 응용 ... 910
   31장. 수리 이론 알고리즘
      31.1 기초적인 수리 이론 ... 921
      31.2 최대 공약수 ... 929
      31.3 모듈로에 의한 계산 ... 935
      31.4 모듈에 의한 선형 방정식의 해 ... 943
      31.5 중국인의 나머지 정리 ... 948
      31.6 원소의 거듭제곱 ... 952
      31.7 RSA 공개-키 암호시스템 ... 957
      31.8 소수 판정 ... 965
      31.9 정수의 인수분해 ... 975
   32장. 스트링 매칭
      32.1 단순한 스트링-대칭 알고리즘 ... 989
      32.2 라빈-카프 알고리즘 ... 991
      32.3 유한 오토마타를 이용한 스트링 매칭 ... 997
      32.4 크누스-모리스-프랫 알고리즘 ... 1004
   33장. 계산 기하학
      33.1 선분의 특징 ... 1016
      33.2 선분의 교차성 결정 ... 1023
      33.3 볼록 껍질의 발견 ... 1030
      33.4 가장 가까운 점들의 쌍 구하기 ... 1040
   34장. NP-완비성
      34.1 다항식 시간 ... 1055
      34.2 다항식 시간 확인 ... 1063
      34.3 NP-완비성과 환원 가능성 ... 1068
      34.4 NP-완비성 증명 ... 1080
      34.5 NP-완비 문제들 ... 1088
   35장. 근사 알고리즘
      35.1 정점 덮개 문제 ... 1112
      35.2 순회 판매원 문제 ... 1116
      35.3 집합 덮개 문제 ... 1122
      35.4 랜덤화와 선형 계획법 ... 1128
      35.5 부분집합 합 문제 ... 1134
Ⅷ부. 부록 : 수학적 기초
   개요 ... 1147
   A. 합 구하기
      A.1 덧셈 공식과 그 특징 ... 1148
      A.2 합의 경계 ... 1153
   B. 집합, 기타
      B.1 집합 ... 1162
      B.2 관계 ... 1168
      B.3 함수 ... 1171
      B.4 그래프 ... 1173
      B.5 트리 ... 1179
   C. 계산과 통계
      C.1 계산 ... 1188
      C.2 확률 ... 1195
      C.3 이산적 임의 변수 ... 1202
      C.4 기하 분포와 이항 분포 ... 1209
      C.5 이항 분포의 꼬리 ... 1215
참고문헌 ... 1225
찾아보기 ... 1239

더보기 닫기