목차
1. 분할 정복 알고리즘
- 엄청나게 크고 방대한 문제를 나누어 쉽게 풀 수 있는 작은 크기로 나누어 문제를 해결 한 뒤 합쳐서 해결하는 방식이다.
- 어려운 문제를 간단하고 빠르게 해결 할 수 있다.
- 함수 재귀 호출을 이용하여 구현하므로 오버플로가 발생할 수 있고 쪼갠 문제를 저장해야 하므로 메모리 사용량이 크다.
※ 3가지 단계를 거쳐 해결한다.
가. 분할: 문제를 더이상 분할할 수 없을 때까지 동일한 유형의 여러 하위 문제로 나눈다.
나. 정복: 가장 작은 단위의 하위 문제를 해결하여 정복한다.
다. 조합: 하위 문제에 대한 결과를 원래 문제에 대한 결과로 조합한다.
※ 분할 정복을 사용하는 대표적인 알고리즘
- 병합 정렬, 퀵 정렬
- 고속 푸리에 변환
2. 병합 정렬 (Merge Sort)
- 분할 정복 알고리즘
- 배열의 가운데를 기준으로 반으로 나누어 분할 한다. (나뉜 배열에도 재귀로 더이상 나눌수 없을 때 까지 반복한다)
- 나뉜 배열을 정렬 기준에 따라 정렬하고 합병하여 다시 정렬하기를 반복한다.
가. 구현하기
3. 퀵 정렬 (Quick Sort)
- 분할 정복 알고리즘
- 배열의 첫번째 요소를 기준(피벗 : pivot)으로 비교해 두 파티션으로 분리해 나눈다
- 나뉜 두 배열에 대해서도 해당 배열의 첫번째 요소를 기준으로 나누는 것을 반복하여 배열의 길이가 0 또는 1이 될 때 까지 반복한다.
- 한번 나뉠 때 마다(재귀 1회마다) 피벗의 위치는 정해진다.
가. 구현하기
※ 참조
위키 백과 합병 정렬
https://ko.wikipedia.org/wiki/%ED%95%A9%EB%B3%91_%EC%A0%95%EB%A0%AC
위키 백과 퀵 정렬
https://ko.wikipedia.org/wiki/%ED%80%B5_%EC%A0%95%EB%A0%AC
'C++ > 자료구조' 카테고리의 다른 글
| [C++] 정렬 #2 삽입 정렬 & 힙 정렬 (Insertion Sort & Heap Sort) (0) | 2023.06.30 |
|---|---|
| [C++] 정렬 #1 버블 정렬 & 선택 정렬 (Bubble Sort & Selection Sort) (0) | 2023.06.29 |
| [C++] 트리 #3 BFS (0) | 2023.06.28 |
| [C++] 트리 #2 DFS (0) | 2023.06.26 |
| [C++] 트리 #1 Tree (0) | 2023.06.24 |