KMO200702622 권 호 :
발행년 : 2007
발행처 : 한빛미디어

서 명 : 쉽게 배우는 알고리즘:관계 중심의 사고법


목차
저자 머리말 = 4
워밍업 = 6
강의 계획표 = 8
숲과 나무 이야기 = 10
학습로드맵과 강의보조자료 = 11
Chapter 01 알고리즘 설계와 분석의 기초
01 몇 가지 기초 사항들 = 21
01 알고리즘이란 = 21
02 알고리즘을 왜 분석하는가 = 22
03 알고리즘의 수행 시간 = 23
04 재귀(자기호출)와 귀납적 사고 = 26
05 알고리즘으로 어떤 문제를 푸는가 = 28
[알고리즘 1-1] 병합정렬 = 27
02 점근적 표기 = 30
01 ○-표기법 = 32
02 Ο-표기법 = 33
03 Ω-표기법 = 33
03 점근적 표기의 엄밀한 정의 = 35
01 Ο-표기법 = 35
02 Ω-표기법 = 37
03 ○-표기법 = 39
04 ο-표기법 = 40
05 w-표기법 = 42
요약 = 44
연습문제 = 45
[Drift] 에너지의 천재 크누스 = 47
Chapter 02 점화식과 점근적 복잡도 분석
01 점화식의 이해 = 51
02 점화식의 점근적 분석 방법 = 53
01 반복대치 = 53
02 추정후 증명 = 56
03 마스터 정리 = 60
요약 = 64
연습문제 = 65
Chapter 03 정렬
01 기초적인 정렬 알고리즘 = 71
01 선택정렬 = 71
02 버블정렬 = 74
03 삽입정렬 = 76
[알고리즘 3-1] 선택정렬 = 71
[알고리즘 3-2] 버블정렬 = 74
[알고리즘 3-3] 삽입정렬 = 77
02 고급 정렬 알고리즘 = 80
01 병합정렬 = 80
02 퀵정렬 = 85
03 힙정렬 = 93
[알고리즘 3-4] 병합정렬 = 81
[알고리즘 3-5] 퀵정렬 = 86
[알고리즘 3-6] 힙 만들기 = 95
[알고리즘 3-7] 힙정렬 = 99
03 비교정렬 시간의 하한 = 100
04 특수 정렬 알고리즘 = 102
01 기수정렬 = 102
02 계수정렬 = 104
[알고리즘 3-8] 기수정렬 = 103
[알고리즘 3-9] 계수정렬 = 104
요약 = 106
연습문제 = 107
[Drift] 관계 중심의 사고 방식 = 110
Chapter 04 선택 알고리즘
01 평균 선형시간 선택 알고리즘 = 115
[알고리즘 4-1] 평균 선형시간 선택 알고리즘 = 116
02 최악의 경우 선형시간 선택 알고리즘 = 119
[알고리즘 4-2] 최악의 경우 선형시간 선택 알고리즘 = 120
요약 = 123
연습문제 = 123
Chapter 05 검색트리
01 레코드, 키의 정의 및 검색트리 = 127
02 이진검색트리 = 129
01 이진검색트리에서의 검색 = 130
02 이진검색트리에서의 삽입 = 132
03 이진검색트리에서의 삭제 = 137
[알고리즘 5-1] 이진검색트리에서의 검색 = 130
[알고리즘 5-2] 이진검색트리에서의 삽입 = 134
[알고리즘 5-2b] 이진검색트리에서의 삽입(비재귀적 버전) = 134
[알고리즘 5-3] 이진검색트리에서의 삭제 = 141
03 레드블랙트리 = 142
01 레드블랙트리에서의 삽입 = 144
02 레드블랙트리에서의 삭제 = 146
03 레드블랙트리의 작업 성능 분석 = 152
04 B-트리 = 154
01 B-트리에서의 검색 = 156
02 B-트리에서의 삽입 = 157
03 B-트리에서의 삭제 = 160
04 B-트리의 작업 성능 분석 = 164
[스케치 5-4] B-트리에서의 삽입 = 157
[스케치 5-5] B-트리에서의 삭제 = 161
05 다차원검색트리 = 165
01 KD-트리 = 165
02 KDB-트리 = 172
03 R-트리 = 176
04 그리드 파일 = 182
요약 = 188
연습문제 = 189
[Drift] 천재 알고리즘의 재현: 스트라센 알고리즘의 재고 = 192
Chapter 06 해시 테이블
01 해시 테이블: 검색 효율의 극단 = 197
02 해시 함수 = 199
01 나누기 방법 = 199
02 곱하기 방법 = 200
03 충돌 해결 = 202
01 체이닝 = 203
02 개방 주소 방법 = 204
[알고리즘 6-1] 체이닝을 사용하는 해시 테이블에서의 작업 = 203
[알고리즘 6-2] 개방주소 방법 = 209
04 해시 테이블에서의 검색 시간 분석 = 212
요약 = 216
연습문제 = 217
Chapter 07 상호 배타적 집합의 처리
01 연결 리스트를 이용한 집합의 처리 = 221
01 작업의 개요 = 221
02 수행시간 = 223
02 트리를 이용한 집합의 처리 = 225
01 기본적인 원리 = 225
02 연산의 효율을 높이는 방법 = 227
[알고리즘 7-1] 트리를 이용한 집합의 처리에서의 Make-Set, Union, Find-Set = 226
[알고리즘 7-2] 랭크를 이용한 Union과 Make-Set = 228
[알고리즘 7-3] 경로압축을 이용한 Find-Set = 229
요약 = 232
연습문제 = 233
[Drift] 추상화와 은유 = 234
Chapter 08 동적 프로그래밍
01 어떤 문제를 동적 프로그래밍으로 푸는가 = 239
[알고리즘 8-1] 피보나치 수(재귀호출) = 239
[알고리즘 8-2] 피보나치 수(동적 프로그래밍 1) = 241
[알고리즘 8-3] 피보나치 수(동적 프로그래밍 2) = 242
02 행렬 경로 문제 = 244
[알고리즘 8-4] 행렬 경로 문제(재귀호출) = 246
[알고리즘 8-5] 행렬 경로 문제(동적 프로그래밍) = 248
03 조약돌 놓기 문제 = 249
[알고리즘 8-6] 조약돌 놓기 문제(재귀호출) = 252
[알고리즘 8-7] 조약돌 놓기 문제(동적 프로그래밍) = 254
04 행렬 곱셈 순서 문제 = 255
[알고리즘 8-8] 행렬 곱셈 순서 문제(재귀호출) = 257
[알고리즘 8-9] 행렬 곱셈 순서 문제(동적 프로그래밍) = 258
05 최장 공통 부분순서(LCS) = 259
[알고리즘 8-10] 최장 공통 부분순서 길이(재귀호출) = 260
[알고리즘 8-11] 최장 공통 부분순서 길이(동적 프로그래밍) = 262
요약 = 264
연습문제 = 264
Chapter 09 그래프 알고리즘
01 그래프 = 269
02 그래프의 표현 = 272
01 인접행렬을 이용한 방법 = 272
02 인접리스트를 이용한 방법 = 274
03 너비우선탐색(BFS)과 깊이우선탐색(DFS) = 277
[알고리즘 9-1] BFS 알고리즘 = 279
[알고리즘 9-2] DFS 알고리즘 = 280
04 최소신장트리 = 282
01 프림 알고리즘 = 282
02 크루스칼 알고리즘 = 288
03 안전성 정리 = 291
[알고리즘 9-3] 프림 알고리즘(버전 1) = 283
[알고리즘 9-4] 프림 알고리즘(버전 2) = 286
[알고리즘 9-5] 크루스칼 알고리즘 = 288
05 위상정렬 = 294
[알고리즘 9-6] 위상정렬 알고리즘 1 = 296
[알고리즘 9-7] 위상정렬 알고리즘 2 = 299
06 최단경로 = 302
01 다익스트라 알고리즘(음의 가중치를 허용하지 않는 경우) = 303
02 벨만-포드 알고리즘(음의 가중치를 허용하는 경우) = 307
03 모든쌍 최단경로 알고리즘 = 313
04 싸이클이 없는 그래프의 최단경로 = 316
[알고리즘 9-8] 다익스트라 알고리즘 = 303
[알고리즘 9-9] 벨만-포드 알고리즘 = 308
[알고리즘 9-10] 플로이드-워샬 알고리즘 = 316
[알고리즘 9-11] 싸이클이 없는 유향 그래프(DAG)에서 최단경로 구하기 = 317
07 강연결 요소 = 321
[알고리즘 9-12] 강연결요소 구하기 = 321
요약 = 326
연습문제 = 327
Chapter 10 문자열 매칭
01 원시적인 매칭 방법 = 333
[알고리즘 10-1] 원시적인 매칭 알고리즘 = 334
02 오토마타를 이용한 매칭 = 336
[알고리즘 10-2] 매칭을 체크하는 알고리즘 = 338
03 라빈-카프 알고리즘 = 340
[알고리즘 10-3] 수치화를 이용한 매칭 알고리즘 = 342
[알고리즘 10-4] 라빈-카프 알고리즘 = 344
04 KMP 알고리즘 = 345
[알고리즘 10-5] KMP 알고리즘 = 347
05 보이어-무어 알고리즘 = 349
[알고리즘 10-6] 보이어-무어-호스풀 알고리즘 = 352
요약 = 356
연습문제 = 357
Chapter 11 NP-완비
01 문제의 종류 = 361
02 Yes／No 문제와 최적화 문제 = 363
03 NP = 365
04 변환 = 368
05 NP-완비 = 373
06 NP-완비 문제들 = 380
07 NP-하드를 최적화 문제로 확장하기 = 391
08 근사해 구하기 = 394
요약 = 399
연습문제 = 399
[Drift] 비운의 천재 알란 튜링과 정지문제 = 402
Chapter 12 상태공간 트리의 탐색
01 상태공간 트리 = 407
02 백트래킹 = 410
01 미로 찾기 문제 = 410
02 색칠 문제 = 412
[알고리즘 12-1] 미로 찾기 문제를 위한 백트래킹 알고리즘 = 412
[알고리즘 12-2] 색칠 문제를 위한 백트래킹 알고리즘 = 414
03 한정분기 = 416
04 A* 알고리즘 = 422
01 최단경로 찾기 문제 = 422
02 TSP = 428
[알고리즘 12-3] 그래프에서 최단경로를 찾기 위한A* 알고리즘 = 427
요약 = 432
연습문제 = 433
[Drift] 공간탐색과 끌개 = 435
참고문헌 = 438
찾아보기 = 448