자료검색

책소개

저명한 프로그래머와 전산학자들이 극찬한 알고리즘 분야 최고의 고전, 드디어 완역 출간!

이 책은 많은 알고리즘을 제시하고 상당히 심도 있게 다루면서도 어떤 수준의 독자라도 이해하기 쉽게 알고리즘을 설계하고 분석했다. 각 장은 비교적 독립적으로 완결된 형식을 갖추고 있으며, 연구 주제로도 쓰일 수 있다. 각 알고리즘은 조금이라도 프로그래밍 경험이 있는 독자라면 누구라도 이해할 수 있는 '의사코드(pseudocode)'로 작성했다. 그리고 내용의 깊이나 수학적 정확성은 저해하지 않으면서 알고리즘을 가능한 쉽게 설명하려고 노력했다.

초판은 교수를 위한 표준 참고 도서로 인정받아 미국과 유럽 대부분의 대학에서 교재로 채택되었다. 개정판에는 알고리즘의 역할, 확률적인 분석과 랜덤화된 알고리즘, 선형 계획법에 대한 내용이 추가되고, 전체 내용이 새롭게 수정됐다. 미묘하지만 중요한 변화로는 초판에서는 루프 불변성을 2장에서 소개한 후 책 전반에 걸쳐 루프 불변성을 사용해 알고리즘의 정확성을 증명하는 데 사용했다. 그렇지만 이번 개정판에서는 수학적이면서도 분석적이라는 초점을 흐리지 않기 위해, 초판의 I부에 있던 수학적 배경 지식에 대한 내용 상당 부분을 부록으로 옮겼으며, 도입부에 동기를 부여하는 내용을 추가했다.

● 난이도: 중,고급

목차

Ⅰ 기초
1. 알고리즘의 역할
2. 시작하기
3. 함수의 증가
4. 점화식
5. 확률적 분석과 랜덤화된 알고리즘

Ⅱ 정렬 순서와 통계량
6. 힙 정렬
7. 퀵 정렬
8. 선형 시간 정렬
9. 중앙값과 순서 통계량

Ⅲ. 자료구조
10. 기본 자료구조
11. 해시 테이블
12. 이진 검색 트리
13. 레드블랙 트리
14. 자료구조의 확장

Ⅳ. 고급 설계 및 분석 기법
15. 동적 프로그래밍
16. 그리디 알고리즘
17. 분할상환 분석

Ⅴ. 고급 자료구조
18. B-트리
19. 이항 힙
20. 피보나치 힙
21. 서로 소 집합의 자료구조

Ⅵ. 그래프 알고리즘
22. 기초적인 그래프 알고리즘
23. 최소 신장 트리
24. 단일 출발지 최단 경로
25. 모든 쌍의 최단 경로
26. 최대 플로우

Ⅶ. 알고리즘 분야의 중요한 토픽
27. 정렬 네트워크
28. 행렬의 연산
29. 선형 계획법
30. 다항식과 FFT
31. 수리 이론 알고리즘
32. 스트링 매칭
33. 계산 기하학
34. NP-완비성
35. 근사 알고리즘

Ⅷ. 부록: 수학적 기초
A. 합 구하기
B. 집합, 기타
C. 계산과 통계