목차

역자 서문………………………………………………………………. xiii
서문 …………………………………………………………………… xiv
감사의 글………………………………………………………………. xvi
1장 소개 1
1.1 변수…………………………………………………………………….1
1.2 데이터형………………………………………………………………..2
1.3 데이터 구조…………………………………………………………….3
1.4 추상 데이터형 …………………………………………………………4
1.5 알고리즘이란 무엇인가?……………………………………………….5
1.6 왜 알고리즘을 분석하는가?……………………………………………5
1.7 알고리즘 정렬의 목적………………………………………………….6
1.8 수행 시간 분석이란 무엇인가?…………………………………………6
1.9 어떻게 알고리즘을 비교하는가?……………………………………….6
1.10 증가율이란 무엇인가?………………………………………………..7
1.11 많이 사용되는 증가율………………………………………………..7
1.12 분석의 종류…………………………………………………………..9
1.13 점근적 표기법………………………………………………………. 10
1.14 빅-오 표기법……………………………………………………….. 10
1.15 오메가 표기법………………………………………………………. 13
1.16 세타 표기법………………………………………………………… 14
1.17 왜 점근적 분석이라고 불리는가?…………………………………… 16
1.18 점근적 분석 가이드라인……………………………………………. 16
1.19 각 표기법의 특성…………………………………………………… 19
1.20 자주 사용되는 로그 함수와 급수………………………………….. 19
1.21 분할 정복을 위한 마스터 정리……………………………………… 20
1.22 분할 정복 마스터 정리 연습문제…………………………………… 21
1.23 차감 정복 점화식을 위한 마스터 정리……………………………… 23
1.24 차감 정복 마스터 정리의 변형……………………………………… 23
1.25 상각 분석…………………………………………………………… 23
1.26 상각 분석 연습문제………………………………………………… 25
2장 재귀와 백트래킹 41
2.1 소개…………………………………………………………………. 41
2.2 재귀란 무엇인가?……………………………………………………. 41
2.3 왜 재귀를 사용하는가?……………………………………………… 42
2.4 재귀 함수의 형식……………………………………………………. 42
2.5 재귀와 메모리(시각화)……………………………………………… 43
2.6 재귀와 반복 비교……………………………………………………. 44
2.7 재귀에 대한 참고 사항………………………………………………. 45
2.8 재귀 알고리즘의 예………………………………………………….. 45
2.9 재귀 연습문제……………………………………………………….. 46
2.10 백트래킹은 무엇인가?……………………………………………… 47
2.11 백트래킹 알고리즘의 예……………………………………………. 47
2.12 백트래킹 연습문제…………………………………………………. 48
3장 연결 리스트 51
3.1 연결 리스트란 무엇인가?……………………………………………. 51
3.2 연결 리스트 ADT……………………………………………………. 52
3.3 왜 연결 리스트를 사용하는가?……………………………………… 52
3.4 배열 개요……………………………………………………………. 52
3.5 연결 리스트와 배열 그리고 동적 배열의 비교………………………. 55
3.6 단일 연결 리스트……………………………………………………. 55
3.7 이중 연결 리스트……………………………………………………. 63
3.8 원형 연결 리스트……………………………………………………. 70
3.9 메모리-효율적인 이중 연결 리스트………………………………….. 79
3.10 연결 리스트 연습문제……………………………………………… 81
4장 스택 107
4.1 스택이란 무엇인가?…………………………………………………107
4.2 스택은 어떻게 사용되는가?…………………………………………108
4.3 스택 ADT……………………………………………………………108
4.4 스택의 적용 사례들…………………………………………………109
4.5 스택의 구현………………………………………………………… 110
4.6 각 구현 방법의 비교………………………………………………… 117
4.7 스택 연습문제………………………………………………………. 118
5장 큐 145
5.1 큐란 무엇인가?……………………………………………………… 145
5.2 어떻게 큐가 사용되는가?……………………………………………146
5.3 큐 ADT……………………………………………………………..146
5.4 예외들……………………………………………………………….147
5.5 큐의 적용 사례들……………………………………………………147
5.6 큐의 구현……………………………………………………………147
5.7 큐 연습문제………………………………………………………… 155
6장 트리 161
6.1 트리란 무엇인가?…………………………………………………… 161
6.2 용어 설명…………………………………………………………… 162
6.3 이진 트리…………………………………………………………… 163
6.4 이진 트리의 종류……………………………………………………164
6.5 이진 트리의 속성…………………………………………………… 165
6.6 이진 트리 탐색………………………………………………………167
6.7 범용 트리(N항 트리)………………………………………………..200
6.8 스레드 이진 트리 탐색……………………………………………… 210
6.9 수식 트리…………………………………………………………… 219
6.10 XOR 트리………………………………………………………….. 222
6.11 이진 검색 트리…………………………………………………….. 223
6.12 균형 이진 검색 트리………………………………………………..246
6.13 AVL 트리…………………………………………………………..247
6.14 기타 트리의 변형들……………………………………………….. 261
7장 우선순위 큐와 힙 267
7.1 우선순위 큐란 무엇인가?……………………………………………267
7.2 우선순위 큐 ADT……………………………………………………268
7.3 우선순위 큐의 적용…………………………………………………268
7.4 우선순위 큐의 구현…………………………………………………269
7.5 힙과 이진 힙………………………………………………………… 271
7.6 이진 힙………………………………………………………………272
7.7 우선순위 큐와 힙 연습문제………………………………………… 281
8장 분리집합 ADT 297
8.1 소개…………………………………………………………………297
8.2 동치 관계와 동치 류………………………………………………..297
8.3 부분집합 ADT………………………………………………………299
8.4 적용 사례……………………………………………………………299
8.5 분리집합 ADT 구현에서의 타협점들……………………………….299
8.6 요약…………………………………………………………………309
8.7 분리집합 연습문제…………………………………………………. 310
9장 그래프 알고리즘 313
9.1 소개………………………………………………………………… 313
9.2 용어………………………………………………………………… 313
9.3 그래프의 적용 사례………………………………………………… 318
9.4 그래프의 표현………………………………………………………. 318
9.5 그래프 탐색………………………………………………………… 323
9.6 위상 정렬 ………………………………………………………….. 332
9.7 최단 경로 알고리즘…………………………………………………334
9.8 최소 신장 트리………………………………………………………343
9.9 그래프 알고리즘 연습문제………………………………………….349
10장 정렬 385
10.1 정렬은 무엇인가?…………………………………………………..385
10.2 왜 정렬하는가?…………………………………………………….385
10.3 분류………………………………………………………………..385
10.4 다른 분류………………………………………………………….387
10.5 버블 정렬…………………………………………………………..387
10.6 선택 정렬…………………………………………………………..389
10.7 삽입 정렬…………………………………………………………..390
10.8 쉘 정렬 …………………………………………………………….393
10.9 병합 정렬 ………………………………………………………….395
10.10 힙 정렬 ……………………………………………………………397
10.11 퀵 정렬 ……………………………………………………………398
10.12 트리 정렬 …………………………………………………………402
10.13 정렬 알고리즘 비교……………………………………………….403
10.14 선형 정렬 알고리즘 ………………………………………………403
10.15 계수 정렬 …………………………………………………………404
10.16 버킷 정렬………………………………………………………….405
10.17 기수 정렬………………………………………………………….405
10.18 위상 정렬………………………………………………………….406
10.19 외부 정렬 …………………………………………………………407
10.20 정렬 연습문제…………………………………………………….408
11장 검색 425
11.1 검색은 무엇인가?………………………………………………….. 425
11.2 왜 검색을 하는가?…………………………………………………. 425
11.3 검색의 종류………………………………………………………..426
11.4 무순서 선형 검색 ………………………………………………….426
11.5 정렬/순서 선형 검색………………………………………………..426
11.6 이진 검색…………………………………………………………..427
11.7 기본적인 검색 알고리즘의 비교……………………………………428
11.8 심볼 테이블과 해싱………………………………………………..429
11.9 문자열 검색 알고리즘……………………………………………..429
11.10 검색 연습문제…………………………………………………….429
12장 선택 알고리즘 467
12.1 선택 알고리즘은 무엇인가?………………………………………..467
12.2 정렬에 의한 선택…………………………………………………..467
12.3 분할에 기반한 선택 알고리즘……………………………………..468
12.4 선형 선택 알고리즘 – 중간값의 중간값 알고리즘………………….468
12.5 정렬된 순서에서 K개의 작은 항목들을 찾기………………………468
12.6 선택 알고리즘 연습문제……………………………………………468
13장 심볼 테이블 485
13.1 소개………………………………………………………………..485
13.2 심볼 테이블이란 무엇인가?………………………………………..486
13.3 심볼 테이블의 구현………………………………………………..486
13.4 심볼 테이블 구현의 비교…………………………………………..488
14장 해싱 489
14.1 해싱이란 무엇인가?………………………………………………..489
14.2 왜 해싱을 하는가?………………………………………………….489
14.3 해시 테이블 ADT…………………………………………………..489
14.4 해싱을 이해하기……………………………………………………490
14.5 해싱의 구성 요소…………………………………………………..492
14.6 해시 테이블………………………………………………………..492
19.3 동적 계획법 전략의 속성들?……………………………………….608
19.4 동적 계획법이 어떤 문제라도 풀 수 있는가?………………………608
19.5 동적 계획법 접근…………………………………………………..608
19.6 동적 계획법 알고리즘의 예…………………………………………609
19.7 동적 계획법 이해하기……………………………………………… 610
19.8 동적 계획법 연습문제……………………………………………… 619
20장 복잡도 클래스 671
20.1 소개……………………………………………………………….. 671
20.2 다항적/지수적 시간………………………………………………..672
20.3 결정 문제란 무엇인가?…………………………………………….672
20.4 결정 절차 ………………………………………………………….673
20.5 복잡도 클래스란 무엇인가?……………………………………….673
20.6 복잡도 클래스의 종류……………………………………………..673
20.7 환원………………………………………………………………..677
20.8 복잡도 클래스 연습문제…………………………………………..682
21장 기타 개념들 687
21.1 소개………………………………………………………………..687
21.2 비트 연산 프로그래밍 공략………………………………………..687
21.3 기타 프로그래밍 연습문제…………………………………………695
참고 도서……………………………………………………………….699
찾아보기………………………………………………………………..702