p. 175 ~ p. 205
분할 정복
- 주어진 문제를 둘 이상의 부분문제로 나눈 뒤, (Divide)
- 각 문제의 답을 재귀호출을 통해 계산 후 (Merge)
- 각 답으로부터 원래 문제의 답을 계산하는 알고리즘 (Base case)
순수 재귀호출 방식과 다른 점
재귀호출 |
분할 정복 |
1 문제 + 나머지 (재귀호출) |
부분문제 (재귀호출) + 부분문제 (재귀호출) |
1 ~ N 합 | |
N 번의 호출 | lgN 번의 호출 |
sum(n-1) + n |
|
병합 정렬과 퀵 정렬
병합 정렬 (Merge Sort) |
퀵 정렬 (Quick Sort) |
O(nlgn) |
O(nlgn) |
병합 단계에서 연산 수행 |
분할 단계에서 연산 수행 |
pivot 잘못 선택 시 최악의 경우 O(n²) 이 될 수 있음 |
문제
쿼드 트리 뒤집기
울타리 잘라내기
'스터디 > 알고리즘 정리' 카테고리의 다른 글
| 탐욕법 (0) | 2018.12.02 |
|---|---|
| 동적 계획법 테크닉 (not yet) (0) | 2018.12.02 |
| 동적 계획법 문제 풀이 (not yet) (0) | 2018.12.02 |
| 동적 계획법 (0) | 2018.12.01 |
| 알고리즘 시간 복잡도 (0) | 2018.11.26 |