상세정보

이 책은 총 12장으로 구성되어 있으며 다음과 같은 내용을 다룬다.

-도입(1장~2장): 알고리즘의 효율성 분석을 위한 기본 도구인 점근적 표기법과 점화식, 점화식의 점근적 분석법을 공부한다.
-정렬과 선택(3장~4장): 알고리즘에서 다루는 관계 중심의 사고 기법을 훈련할 수 있는 좋은 주제인 정렬과 선택을 통해 생각하는 훈련을 한다.
-자료의 저장과 검색(5장~6장): 알고리즘의 중요한 응용 분야의 하나인 자료의 저장 및 검색을 위한 자료구조와 알고리즘을 공부한다.
-집합의 처리(7장): 집합을 처리하는 자료구조와 알고리즘을 배운다.
-그래프 알고리즘(9장): 다채로운 쓰임새를 가진 그래프를 표현하는 방법과 그래프를 이용하는 다양한 알고리즘을 배운다.
-동적 프로그래밍과 문자열 매칭(8장, 10장): 다른 장들과 색다른 주제로 사고력을 훈련할 수 있는 동적 프로그래밍과 문자열 매칭을 공부한다.
-계산의 한계(11장): 10장까지의 주제는 빠른 시간에 해결할 수 있는 문제를 대상으로 하였으나 이것이 항상 가능하지 않다는 사실, 그리고 이러한 사실을 안다는 것의 유용함을 공부한다.
-문제 해결에 관한 다른 시각(12장): 문제의 해를 찾는 풀이 과정을 상태 공간 트리로 파악하는 방법을 공부한다.

정보제공 :

목차
저자 머리말 = 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