목차
제1장 알고리즘과 복잡도 분석 = 13
1.1 알고리즘의 개념 = 13
1.2 알고리즘 분석 및 복잡도 측정 = 21
1.3 순환적 알고리즘 = 37
1.4 연습문제 = 43
제2장 자료구조 = 55
2.1 소개 = 55
2.2 배열과 레코드 = 55
2.2.1 배열 = 56
1차원 배열 = 57
다차원 배열 = 57
2.2.2 레코드 = 59
2.3 스택(stack)과 큐(queue) = 60
2.3.1 스택 = 60
삽입(PUSH) = 62
제거(POP) = 63
기타 스택 연산들 = 64
2.3.2 큐 = 65
큐의 개념 = 65
큐의 표현 = 67
큐의 연산 = 67
데크(deque) = 71
2.4 리스트 = 71
2.4.1 선형 리스트 = 71
2.5 트리 = 74
2.5.1 트리의 개념 및 용어들 = 74
트리에 관한 기본적인 용어들 = 75
2.5.2 이진트리 = 76
이진트리의 개념과 용어 = 77
이진트리의 표현 및 성질들 = 79
2.5.3 이진트리의 순회 = 82
2.5.4 스레드 된 이진트리 = 86
2.5.5 이진트리의 응용 = 87
이진 탐색트리 = 87
히프 트리(heap tree) = 89
2.6 그래프 = 96
2.6.1 그래프 개념 및 용어 = 96
2.7 해싱 = 101
2.7.1 해싱의 개념 = 101
2.7.2 해싱 함수 = 102
나눗셈 방법 = 103
폴딩(folding) 방법 = 103
중간제곱 방법 = 104
자릿수 분석방법 = 104
기수 변환 방법(radix transformation) = 104
2.7.3 충돌 및 해결책 = 105
개방주소 방법 = 105
2차 탐사방법 = 106
체이닝 방법 = 106
2.8 연습문제 = 107
제3장 분할 및 정복 = 119
3.1 분할 및 정복의 개념 = 119
3.2 이진탐색 (binary search) = 120
3.3 Strassen의 행렬식 곱셈 알고리즘 = 125
3.4 최대값 및 최소값 문제 = 131
3.5 합병정렬 (merge sort) = 137
3.6 퀵 정렬 (quick sort) = 147
3.7 연습문제 = 156
제4장 탐욕적 방법(Greedy Method) = 161
4.1 탐욕적 방법의 소개 = 161
4.2 단일 출발점에서의 최단경로 문제 = 167
4.3 배낭 문제 = 175
4.4 최소 신장트리 = 179
4.4.1 Prim 알고리즘 = 181
4.4.2 Kruksal 알고리즘 = 189
4.5 연습문제 = 195
제5장 동적 프로그래밍 = 201
5.1 동적 프로그래밍의 개념 = 201
최적의 원리 = 202
5.2 이항계수 = 206
5.3 행렬의 연속적인 곱셈 = 211
5.4 최적의 이진 탐색트리 = 222
5.5 외판원 문제 = 233
5.6 0-1 배낭문제 = 241
5.7 최단경로 문제 : Floyd 알고리즘 = 249
5.8 연습문제 = 258
제6장 백트랙킹 (Backtracking) = 265
6.1 개념소개 = 265
6.2 해밀턴 회로문제 = 270
6.3 0-1 배낭문제 = 274
0-1 배낭문제에 대한 동적 프로그래밍 방법과 백트래킹 방법의 비교 = 288
6.4 그래프 채색문제 = 289
6.5 서양장기에서의 n-여왕문제 = 294
6.6 Monte Carlo 알고리즘 = 298
6.7 연습문제 = 303
제7장 NP 이론 : 계산 복잡도 및 풀기 어려운 문제 = 307
7.1 개념의 소개 = 307
7.2 문제의 풀기 어려움 = 309
7.3 최적화 문제 및 결정 문제 = 315
7.4 P와 NP의 개념 = 319
7.5 NP-completeness = 325
7.6 NP-hard 문제들 = 339
7.7 근사 알고리즘 = 345
7.8 연습문제 = 352
제8장 병렬 컴퓨터 및 병렬 알고리즘 = 357
8.1 소개 = 357
8.2 PRAM (Parallel Random Access Machine) = 362
8.2.1 1차원 배열에서 최대값 구하기 = 364
8.2.2 병렬 합병정렬 = 372
8.2.3 이항 계수 = 375
8.2.4 정방행렬의 곱셈 = 377
8.3 다른 병렬 컴퓨터 모형들 = 379
8.4 연습문제 = 381
찾아보기 = 383
