분할정복 Divide and Conquer (DAC, D&C)
개념
하나의 작업을 그와 같은 형태의 그보다 작은 작업으로 해결하는 알고리즘
같은 모양의 더 작은 문제가 없을 때까지 작게 만든 후, 가장 작은 문제부터 점점 더 큰 문제를 해결함
양파 같은 형태
구조
- 분할 divide
해결할 문제를 동일한 형태의 작은 작업으로 분할
- 정복 conquer
분할한 작은 문제를 해결
- 통합 combine
해결한 작은 문제의 답으로 큰 문제를 해결
적용
- 정렬
- 큰 숫자 곱하기
- 이진 탐색
- Closest Pair of Points 문제 -> ?
- Strassens's 알고리즘 -> ?
- Cooley-Tukey Fast Fourier Transform(FFT) 알고리즘 -> ?
(참고: https://hongjw1938.tistory.com/193)
예시
https://velog.io/@dia218/합병-정렬