목차 일부
역자 서문 ... ⅴ
저자 서문 ... 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
더보기 닫기