쉽게 배우는 알고리즘

머리말
이 책의 사용 설명서

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 다익스트라 알고리즘(음의 가중치를 허용하지 않는 경우 )o 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-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* 알고리즘