목 차

머리말

이 책의 사용 설명서

Chapter 01 알고리즘이란

01 알고리즘은 문제 해결 과정을 묘사하는 것

02 알고리즘은 생각하는 방법을 훈련하는 것

03 알고리즘은 자료구조의 확장

Drift 알고리즘 단어의 유래 : 알-콰리즈미

Chapter 02 알고리즘 설계와 분석의 기초

01 몇 가지 기초 사항들

1 알고리즘 분석의 필요성

2 알고리즘의 수행 시간

3 재귀(자기호출)와 귀납적 사고

4 알고리즘으로 어떤 문제를 푸는가

02 점근적 표기

1 Θ-표기법

2 O-표기법

3 Ω-표기법

★ 03 점근적 표기의 엄밀한 정의

1 O-표기법

2 Ω-표기법

3 Θ-표기법

4 o-표기법

5 ω-표기법

요약/연습문제

Drift 에너지의 천재 크누스

Chapter 03 점화식과 알고리즘 복잡도 분석

01 점화식

02 점화식의 점근적 분석 방법

1 반복 대치

2 추정 후 증명

3 마스터 정리

요약/연습문제

Drift 천재 알고리즘의 재현 : 스트라센 알고리즘의 재고

Chapter 04 정렬

01 기본적인 정렬 알고리즘

1 선택 정렬Selection Sort

2 버블 정렬Bubble Sort

3 삽입 정렬Insertion Sort

02 고급 정렬 알고리즘

1 병합 정렬Merge Sort

2 퀵 정렬Quick Sort

3 힙 정렬Heap Sort

03 비교 정렬 시간의 하한

04 특수 정렬 알고리즘

1 기수 정렬Radix Sort

2 계수 정렬Counting Sort

요약/연습문제

Drift 재귀와 관계 중심의 사고방식

Chapter 05 선택 알고리즘

01 평균 선형 시간 선택 알고리즘

02 최악의 경우에도 선형 시간을 보장하는 선택 알고리즘

요약/연습문제

Chapter 06 검색 트리

01 레코드, 키의 정의 및 검색 트리

02 이진 검색 트리

1 이진 검색 트리에서 검색

2 이진 검색 트리에서 삽입

3 이진 검색 트리에서 삭제

03 레드 블랙 트리

1 레드 블랙 트리에서 삽입

2 레드 블랙 트리에서 삭제

3 레드 블랙 트리의 작업 성능 분석

04 B-트리

1 B-트리에서 검색

2 B-트리에서 삽입

3 B-트리에서 삭제

4 B-트리의 작업 성능 분석

★ 05 다차원 검색 트리

1 KD-트리

2 KDB-트리

3 R-트리

4 그리드 파일

요약/연습문제

Chapter 07 해시 테이블

01 해시 테이블 : 검색 효율의 극단

02 해시 함수

1 나누기 방법

2 곱하기 방법

03 충돌 해결

1 체이닝

2 개방 주소 방법

04 해시 테이블에서 검색 시간 분석

요약/연습문제

Chapter 08 집합의 처리

01 연결 리스트를 이용한 집합의 처리

1 작업의 개요

2 수행 시간

02 트리를 이용한 집합의 처리

1 기본 원리

2 연산의 효율을 높이는 방법

요약/연습문제

Drift 추상화와 은유

Chapter 09 동적 프로그래밍

01 어떤 문제를 동적 프로그래밍으로 푸는가

02 행렬 경로 문제

03 돌 놓기 문제

04 행렬 곱셈 순서 문제

05 최장 공통 부분 순서LCS

요약/연습문제

Chapter 10 그래프

01 그래프

02 그래프의 표현

1 인접 행렬을 이용한 방법

2 인접 리스트를 이용한 방법

3 인접 배열과 인접 해시 테이블

03 너비 우선 탐색BFS과 깊이 우선 탐색DFS

04 최소 신장 트리

1 프림 알고리즘

2 크루스칼 알고리즘

3 안전성 정리

05 위상 정렬Topological Sorting

06 최단 경로

1 다익스트라 알고리즘(음의 가중치를 허용하지 않는 경우 )? 331

2 벨만-포드 알고리즘(음의 가중치를 허용하는 경우)

3 모든 쌍 최단 경로 알고리즘

4 사이클이 없는 그래프의 최단 경로

07 강연결 요소

요약/연습문제

Chapter 11 그리디 알고리즘

01 전형적인 그리디 알고리즘의 구조

02 그리디 알고리즘으로 최적해가 보장되지 않는 예

1 이진 트리의 최적합 경로 찾기

2 보따리 문제

3 동전 바꾸기

03 그리디 알고리즘으로 최적해가 보장되는 예

1 최소 신장 트리

2 회의실 배정 문제

3 그 밖의 예

04 매트로이드 : 그리디 알고리즘으로 최적해가 보장되는 공간 구조

1 매트로이드의 정의와 예

2 매트로이드의 확장과 포화

3 매트로이드 구조이면 그리디 알고리즘으로 최적해 보장

★ 4 문제 공간 탐색 관점에서 본 매트로이드

요약/연습문제

Chapter 12 문자열 매칭

01 원시적인 매칭 방법

02 오토마타를 이용한 매칭

03 라빈-카프 알고리즘

★ 04 KMP 알고리즘

05 보이어-무어 알고리즘

요약/연습문제

Chapter 13 NP-완비

01 문제의 종류

02 Yes/No 문제와 최적화 문제

03 NP

04 다항식 시간 변환

05 NP-완비

06 NP-완비 문제들

07 NP-하드를 최적화 문제로 확장하기

★ 08 근사해 구하기

★ 09 현상금 걸린 문제들

요약/연습문제

Drift 비운의 천재 알란 튜링과 정지 문제

Chapter 14 상태 공간 트리의 탐색

01 상태 공간 트리

02 백트래킹

1 미로 찾기 문제

2 색칠 문제

03 한정 분기

04 A* 알고리즘

1 최단 경로 찾기 문제

2 TSP

요약/연습문제

Drift 공간 탐색과 끌개

6. 알고리즘 목차

알고리즘 2-1 병합 정렬

알고리즘 4-1 선택 정렬

알고리즘 4-2 버블 정렬

알고리즘 4-3 삽입 정렬

알고리즘 4-4 병합 정렬

알고리즘 4-5 퀵 정렬

알고리즘 4-6 분할

알고리즘 4-7 힙 만들기

알고리즘 4-8 힙 정렬

알고리즘 4