C언어로 설명한 알고리즘

1. 알고리즘 개요
1.1 알고리즘 정의 및 표현 방법 11
1.2 기본적인 데이터 구조 13
1.2.1 배열(Array) 16
1.2.2 연결 리스트(Linked List) 17
1.2.3 스택(Stack) 19
1.2.4 큐(Queue) 22
1.2.5 트리(Tree) 25
1.3 순환(Recursion) 25
1.3.1 순환 알고리즘 28
1.3.2 순환 함수 호출 32
연습문제 32
2. 알고리즘 분석 및 설계 방법
2.1 알고리즘 분석 35
2.1.1 알고리즘 분석 기준 37
2.1.2 평균과 최악의 경우 분석 43
2.1.3 점근적 복잡도 및 중요성 46
2.1.4 순환 알고리즘 복잡도 분석 51
2.2 알고리즘 설계 방법 60
2.2.1 분할 및 정복 방법 60
2.2.2 Greedy 선택 68
2.3 알고리즘의 선택 73
연습문제 76
3. 정렬
3.1 개요 80
3.2 내부 정렬 80
3.2.1 삽입 정렬 81
3.2.2 선택 정렬 83
3.2.3 버블 정렬 85
3.2.4 셸 정렬 87
3.2.5 퀵 정렬 90
3.2.6 2-원 합병 정렬 98
3.2.7 히프 정렬 100
3.2.8 기수 정렬 103
3.2.9 성능 비교 107
3.3 외부 정렬 108
3.3.1 자연 2-원 합병 110
3.3.2 균형 2-원 합병 112
3.3.3 균형 m-원 합병 114
3.3.4 다단계 합병 115
연습문제 119
4. 탐색
4.1 개요 123
4.2 기본 탐색 125
4.2.1 선형 탐색 125
4.2.2 개선된 선형 탐색 126
4.3 이진 탐색 128
4.4 트리 탐색법 130
4.4.1 이진 탐색 트리 130
4.4.2 균형 탐색 트리 141
4.5 외부 탐색 149
4.5.1 m-원 탐색 트리 149
4.5.2 B-트리 153
4.5.3 B*-트리 156
4.5.4 B`-트리 160
4.5.5 그 외 트리 165
4.6 해상(Hashing) 173
4.6.1 개요 173
4.6.2 해시 함수 174
4.6.3 충돌 해결 방안 178
연습문제 183
5 스트링 매칭
5.1 개요 187
5.2 Brute-Force 알고리즘 188
5.3 KMP(Knuth-Morris_Pratt) 알고리즘 189
5.4 Boyer-Mooer 알고리즘 195
5.5 Rabbin-Karp 알고리즘 198
연습문제 201
6. 그래프
6.1 정의 및 표현법 203
6.1.1 정의 및 용어 203
6.1.2 그래프 표현법 209
6.2 그래프의 순회 214
6.2.1 깊이 우선 탐색 215
6.2.2 반복적 깊이 우선 탐색 217
6.2.3 너비 우선 탐색 218
6.3 최소 신장 트리 219
6.3.1 신장 트리 219
6.3.2 최소 비용 신장 트리 221
6.4 최단 경로 226
6.4.1 단일점 출발-모든 종착점으로의 최단 경로 227
6.4.2 모든 쌍의 최단 경로 231
6.4.3 도착 가능성 234
6.5 그래프 연결성 235
6.5.1 이중 연결성 그래프 235
6.5.2 강 연결성 그래프 238
6.6 위상 정렬 241
6.6.1 위상 정렬 241
6.6.2 임계 경로 244
연습문제 249
7. 기하 알고리즘
7.1 기본적인 기하 알고리즘 253
7.2 볼록 껍질(Convex Hull) 찾기 261
7.3 Range 탐색 272
7.3.1 1차원 Range 탐색 273
7.3.2 기본적인 방법들 274
7.3.3 격자 방법 276
7.3.4 2차원 트리(Two-Dimensional Tree) 279
7.3.5 다차원(Multidimensional) Range 탐색 283
7.4 교차점 문제 284
7.4.1 수평선과 수직선 285
7.4.2 구현 288
7.4.3 일반적인 선 교차점 291
7.5 근접점 찾기 문제 294
7.5.1 근접쌍 문제 295
연습문제 303
8 동적 알고리즘
8.1 개요 305
8.2 K-단계(K-Stage) 그래프 308
8.3 배낭 문제 313
8.3.1 DKP의 구현 317
8.3.2 0/1 배낭 문제 알고리즘 분석 319
8.4 최소 삼각형 분할 321
8.5 게임 문제 327
8.6 작업 스케줄링 329
연습문제 334
9. 병렬 알고리즘
9.1 개요 337
9.2 병렬 처리 및 모델 분류 340
9.3 병렬 알고리즘 분석 및 표현 345
9.4 병렬 알고리즘의 예 348
9.4.1 선택 문제 348
9.4.2 병렬 퀵 정렬 352
9.4.3 비동기 병렬 퀵 정렬 355
9.4.4 홀수/짝수 전송 병렬 정렬 358
9.4.5 합병/분리 정렬 360
연습문제 363
10. NP 완전 문제
10.1 개요 365
10.2 비결정적 알고리즘 367
10.3 계층 NP-Hard와 NP-Complete 370
10.4 Cook 이론 371
10.5 NP-Hard 문제 376
10.5.1 NP-Hard 그래프 376
10.5.2 NP-Hard 스케줄링 379
10.6 NP-Hard 문제 예 382
연습문제 385
참고문헌 386
색인 387