머리말 이 책의 사용 설명서 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 공간 탐색과 끌개 알고리즘 목차 알고리즘 2-1 병합 정렬 알고리즘 4-1 선택 정렬 알고리즘 4-2 버블 정렬 알고리즘 4-3 삽입 정렬 알고리즘 4-4 병합 정렬 알고리즘 4-5 퀵 정렬 알고리즘 4-6 분할 알고리즘 4-7 힙 만들기 알고리즘 4-8 힙 정렬 알고리즘 4-9 기수 정렬 알고리즘 4-10 계수 정렬 알고리즘 5-1 평균 선형 시간 선택 알고리즘 알고리즘 5-2 최악의 경우 선형 시간 선택 알고리즘 알고리즘 6-1 이진 검색 트리에서 검색 알고리즘 6-2 이진 검색 트리에서 삽입 스케치 알고리즘 6-3 이진 검색 트리에서 삽입 알고리즘 6-4 이진 검색 트리에서 삽입(비재귀적 버전) 알고리즘 6-5 이진 검색 트리에서 삭제 스케치 알고리즘 6-6 이진 검색 트리에서 삭제 알고리즘 6-7 B-트리에서 삽입 스케치 알고리즘 6-8 B-트리에서 삭제 스케치 알고리즘 7-1 체이닝을 사용하는 해시 테이블에서 작업 알고리즘 7-2 개방 주소 방법 알고리즘 8-1 트리를 이용한 집합의 처리에서 Make-Set, Union, Find-Set 알고리즘 8-2 랭크를 이용한 Union과 Make-Set 알고리즘 8-3 경로 압축을 이용한 Find-Set 알고리즘 9-1 피보나치 수 (재귀호출) 알고리즘 9-2 피보나치 수 (동적 프로그래밍 1) 알고리즘 9-3 피보나치 수 (동적 프로그래밍 2) 알고리즘 9-4 행렬 경로 문제 (재귀호출) 알고리즘 9-5 행렬 경로 문제 (동적 프로그래밍) 알고리즘 9-6 돌 놓기 문제 (재귀호출) 알고리즘 9-7 돌 놓기 문제 (동적 프로그래밍) 알고리즘 9-8 행렬 곱셈 순서 문제 (재귀호출) 알고리즘 9-9 행렬 곱셈 순서 문제 (동적 프로그래밍) 알고리즘 9-10 최장 공통 부분 순서 길이( 재귀호출) 알고리즘 9-11 최장 공통 부분 순서 길이( 동적 프로그래밍) 알고리즘 10-1 BFS 알고리즘 알고리즘 10-2 DFS 알고리즘 알고리즘 10-3 프림 알고리즘(버전 1) 알고리즘 10-4 프림 알고리즘(버전 2) 알고리즘 10-5 크루스칼 알고리즘 알고리즘 10-6 위상 정렬 알고리즘 1 알고리즘 10-7 위상 정렬 알고리즘 2 알고리즘 10-8 다익스트라 알고리즘 알고리즘 10-9 벨만-포드 알고리즘 알고리즘 10-10 플로이드-워샬 알고리즘 알고리즘 10-11 사이클이 없는 유향 그래프DAG에서 최단 경로 구하기 알고리즘 10-12 강연결 요소 구하기 알고리즘 11-1 전형적인 그리디 알고리즘 알고리즘 11-2 프림 알고리즘 알고리즘 11-3 그리디 알고리즘 알고리즘 11-4 이진 트리의 그리디 탐색 알고리즘 11-5 보따리 문제를 위한 그리디 알고리즘 알고리즘 11-6 프림 알고리즘 알고리즘 11-7 회의실 배정을 위한 그리디 알고리즘 알고리즘 11-8 최대 가중치 합을 구하는 그리디 알고리즘 알고리즘 11-9 매트로이드에서 개선형 그리디 알고리즘 알고리즘 12-1 원시적인 매칭 알고리즘 알고리즘 12-2 매칭을 체크하는 알고리즘 알고리즘 12-3 수치화를 이용한 매칭 알고리즘 알고리즘 12-4 라빈-카프 알고리즘 알고리즘 12-5 KMP 알고리즘 알고리즘 12-6 보이어-무어-호스풀 알고리즘 알고리즘 14-1 미로 찾기 문제를 위한 백트래킹 알고리즘 알고리즘 14-2 색칠 문제를 위한 백트래킹 알고리즘 알고리즘 14-3 그래프에서 최단 경로를 찾는 A* 알고리즘 |