한빛출판네트워크

알고리즘 학습과 진화의 길잡이

전 세계 알고리즘 학습의 바이블로 자리매김한 명저의 최신 개정판이다. 알고리즘의 깊이와 넓이를 두 아우르고 이론과 실습을 균형 있게 다룬다는 전판의 강점은 그대로 유지하되, 많은 변화를 통해 완성도를 한층 업그레이드했다. 4판에서는 이분 그래프 매칭, 온라인 알고리즘, 머신러닝 알고리즘 등3 개 주제를 새롭게 다루며, 여러 절에서 각 분야의 최신 연구 결과와 기술 변화를 반영한 알고리즘으로 갱신되었다. 또한 설명이 한층 명확해졌으며, 140개의 새로운 연습문제와 22개의 종합문제가 추가되고 기존 문제들도 독자들의 피드백을 반영하여 다수 개선되었다.

PART 01 기초

Chapter 01 알고리즘의 역할 
1.1 알고리즘 
1.2 기술로서의 알고리즘

Chapter 02 시작하기 
2.1 삽입 정렬 
2.2 알고리즘의 분석 
2.3 알고리즘의 설계
 

Chapter 03 수행 시간 특성화 
3.1 Ο-표기, Ω-표기, Θ-표기 
3.2 점근적 표기: 공식적인 정의 
3.3 표준 표기법과 흔히 사용되는 함수

Chapter 04 분할 정복 
4.1 정사각형 행렬 곱하기 
4.2 행렬 곱셈을 위한 스트라센 알고리즘 
4.3 점화식을 풀기 위한 치환법 
4.4 점화식을 풀기 위한 재귀 트리 방법 
4.5 점화식을 풀기 위한 마스터 방법 
4.6 연속 마스터 정리의 증명 
4.7 아크라-바지 점화식

Chapter 05 확률적 분석과 랜덤화된 알고리즘 
5.1 고용 문제 
5.2 지표 확률 변수 
5.3 랜덤화된 알고리즘 
5.4 확률적 분석과 지표 확률 변수의 기타 활용 

PART 02 정렬과 순서 통계량

Chapter 06 힙 정렬
6.1 힙 
6.2 힙 특성 유지하기 
6.3 힙 만들기 
6.4 힙 정렬 알고리즘 
6.5 우선순위 큐
 

Chapter 07 퀵 정렬 
7.1 퀵 정렬 소개 
7.2 퀵 정렬 성능 
7.3 랜덤화된 퀵 정렬 
7.4 퀵 정렬 분석
 

Chapter 08 선형 시간 정렬
8.1 정렬의 하한 
8.2 계수 정렬 
8.3 기수 정렬 
8.4 버킷 정렬
 

Chapter 09 중앙값과 순서 통계량
9.1 최솟값과 최댓값 
9.2 평균 선형 수행 시간에 선택하기 
9.3 최악의 경우 선형 시간에 선택하기 
    
PART 03 자료구조

Chapter 10 기본 자료구조 
10.1 간단한 배열 기반 자료구조: 배열, 행렬, 스택, 큐 
10.2 연결 리스트 
10.3 루트 있는 트리 표현하기
 

Chapter 11 해시 테이블
11.1 직접 주소 테이블 
11.2 해시 테이블 
11.3 해시 함수 
11.4 개방 주소 방법 
11.5 실용적 고려 사항
 

Chapter 12 이진 검색 트리
12.1 이진 검색 트리의 개념 
12.2 이진 검색 트리에 대한 질의 
12.3 삽입과 삭제 

Chapter 13 레드 블랙 트리 
13.1 레드 블랙 트리의 특성 
13.2 회전 
13.3 삽입 
13.4 삭제 

PART 04 고급 설계 및 분석 기법

Chapter 14 동적 프로그래밍
14.1 막대 자르기 
14.2 행렬 체인 곱 
14.3 동적 프로그래밍의 요소 
14.4 최장 공통 부분 시퀀스(LCS) 
14.5 최적 이진 검색 트리

Chapter 15 그리디 알고리즘 
15.1 활동 선택 문제 
15.2 그리디 방법의 요소들 
15.3 허프만 코드 
15.4 오프라인 캐싱

Chapter 16 분할 지불 분석 
16.1 총계 분석 
16.2 결산 방법 
16.3 잠재 함수 방법 
16.4 동적 테이블

PART 05 고급 자료구조

Chapter 17 자료구조의 확장 
17.1 동적 순서 통계량 
17.2 자료구조 확장 기법 
17.3 구간 트리

Chapter 18 B-트리 
18.1 B-트리의 정의 
18.2 B-트리에 대한 기본 연산 
18.3 B-트리에서 키 삭제

Chapter 19 서로소 집합의 자료구조 
19.1 서로소 집합의 연산 
19.2 서로소 집합의 연결 리스트 표현 
19.3 서로소 집합 포리스트 
19.4 경로 압축을 이용한 순위에 의한 유니온의 분석

PART 06 그래프 알고리즘

Chapter 20 기본 그래프 알고리즘 
20.1 그래프의 표현 
20.2 너비 우선 탐색 
20.3 깊이 우선 탐색 
20.4 위상 정렬 
20.5 강연결 요소 
    
Chapter 21 최소 신장 트리
21.1 최소 신장 트리의 확장 
21.2 크루스칼 알고리즘과 프림 알고리즘

Chapter 22 단일 출발점 최단 경로 
22.1 벨만-포드 알고리즘 
22.2 비순환 방향 그래프에서의 단일 출발점 최단 경로 
22.3 다익스트라 알고리즘 
22.4 차이 제약조건과 최단 경로 
22.5 최단 경로 특성의 증명

Chapter 23 모든 쌍 최단 경로
23.1 최단 경로와 행렬 곱셈 
23.2 플로이드-워샬 알고리즘 
23.3 희소 그래프에 대한 존슨 알고리즘

Chapter 24 최대 플로우
24.1 플로우 네트워크 
24.2 포드-풀커슨 방법 
24.3 최대 이분 매칭

Chapter 25 이분 그래프에서의 매칭 
25.1 최대 이분 매칭(재방문) 
25.2 안정적-결혼 문제 
25.3 배정 문제에 대한 헝가리안 알고리즘 

PART 07 알고리즘 분야의 중요한 토픽

Chapter 26 병렬 알고리즘 
26.1 포크-조인 병렬의 기초 
26.2 병렬 행렬 곱셈 
26.3 병렬 병합 정렬

Chapter 27 온라인 알고리즘 
27.1 엘리베이터 기다리기 
27.2 검색 목록 유지하기 
27.3 온라인 캐싱

Chapter 28 행렬 연산 
28.1 선형 연립 방정식 풀기 
28.2 역행렬 
28.3 양의 정부호 대칭 행렬과 최소 제곱 근사

Chapter 29 선형계획법 
29.1 선형계획법 공식과 알고리즘 
29.2 선형계획법으로 문제 표현하기 
29.3 쌍대성

Chapter 30 다항식과 FFT 
30.1 다항식의 표현 
30.2 DFT와 FFT 
30.3 FFT 회로

Chapter 31 정수론 알고리즘 
31.1 기초적인 정수론 개념 
31.2 최대공약수

PART 08 부록: 수학적 기초

Appendix A 합 
A.1 합 공식과 특성 
A.2 합의 한계

Appendix B 집합과 기타 
B.1 집합 
B.2 관계 
B.3 함수 
B.4 그래프 
B.5 트리

Appendix C 셈과 확률 
C.1 셈 
C.2 확률 
C.3 이산 확률 변수 
C.4 기하 분포와 이항 분포 
C.5 이항 분포의 꼬리

Appendix D 행렬 
D.1 행렬과 행렬 연산 
D.2 행렬의 기본 특성