목 차
머리말
이 책의 사용 설명서
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