[심화] 분할정복 Divide and Conquer

dia·2023년 9월 22일
0

분할정복 Divide and Conquer (DAC, D&C)

개념

하나의 작업을 그와 같은 형태의 그보다 작은 작업으로 해결하는 알고리즘
같은 모양의 더 작은 문제가 없을 때까지 작게 만든 후, 가장 작은 문제부터 점점 더 큰 문제를 해결함
양파 같은 형태

구조

  • 분할 divide
    해결할 문제를 동일한 형태의 작은 작업으로 분할
  • 정복 conquer
    분할한 작은 문제를 해결
  • 통합 combine
    해결한 작은 문제의 답으로 큰 문제를 해결

적용

  1. 정렬
  2. 큰 숫자 곱하기
  3. 이진 탐색
  4. Closest Pair of Points 문제 -> ?
  5. Strassens's 알고리즘 -> ?
  6. Cooley-Tukey Fast Fourier Transform(FFT) 알고리즘 -> ?

(참고: https://hongjw1938.tistory.com/193)


예시

https://velog.io/@dia218/합병-정렬

profile
CS 메모장

0개의 댓글