[목차] 알고리즘

1. 알고리즘 개요

1.1 알고리즘 정의

1.2 시간복잡도와 공간복잡도: Ο-표기, Ω-표기, Θ-표기

1.3 주요 함수

2. 정렬

2.1 삽입 정렬(Insertion Sort)

2.2 선택 정렬(Selection Sort)

2.3 버블 정렬(Bubble Sort)

2.4 퀵 정렬(Quick Sort)

2.5 병합 정렬(Merge Sort)

2.6 계수 정렬(Counting Sort)

2.7 기수 정렬(Radix Sort)

2.8 힙 정렬(Heap Sort)

3. 수학

3.1 소수 판별: 에라토스테네스의 체

3.2 최대공약수: 유클리드 호제법

3.3 행렬 연산

3.4 순열과 조합

3.5 

4. 동적계획법

 

5. 그리디

 

6. 시뮬레이션

 

7. 탐색

5.1 선형 탐색(Linear Search)

5.2 이분 탐색(Binary Search)

5.3 BFS(Breadth First Search)

5.4 DFS(Depth First Search)

5.5 최단경로탐색

5.6 최소신장트리

 

5. 

 

 

 

 

 

 

 

 

 

 

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 확률적 분석과 지표 확률 변수의 기타 활용

 

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 이항 분포의 꼬리