[Algorithm:알고리즘] 03 Divide and Conquer

목차

0. Introduction: 분할정복 소개

- 에피소드

- DnC를 이용한 토너먼트 알고리즘

- DnC의 키 아이디어

- DnC의 추상 알고리즘

- DnC의 성능 분석

1. Recurrence Relation: 점화식

- 연습 문제

  1) Characteristic equation(특성 다항식)

  2) Repeated substitution(반복 치환)

  3) Master theorem

2. DnC Algorithm : 분할정복 알고리즘

- 토너먼트

- 이진탐색

3. Multiplication : 곱셈

- DnC를 이용한 곱셈 알고리즘

4. Sorting : 정렬

- 병합정렬

- 퀵 정렬

5. Medians : 중앙값

- K번째로 작은 값 찾기

6. Matrix Multiplication : 행렬 곱셈