[알고리즘] 분할 정복 알고리즘(Divide and Conquer)

🟡 분할 정복 알고리즘(Divide and Conquer)

- 큰 문제를 작은 부분 문제로 분할하여 해결하는 알고리즘이다.

- 주어진 문제를 더 작은 하위 문제로 분할하고, 각 하위 문제를 재귀적으로 해결한 후, 그 해답을 결합하여 원래 문제의 해답을 얻는 방법이다.

 

 

🟡 분할 정복 알고리즘의 단계

① 분할(Divide): 주어진 문제를 더 작은 부분 문제로 분할한다.

② 정복(Conquer): 작은 부분 문제들을 재귀적으로 해결한다.

③ 결합(Combine): 작은 부분 문제들의 해답을 결합하여 원래 문제의 해답을 얻는다.

 

 

🟡 분할정복 알고리즘 예시

① 병합 정렬(Merge Sort)

② 퀵 정렬(Quick Sort)

③ 이진 검색(Binary Search)

④ 카라츠바 곱셈 알고리즘(Karatsuba)