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

---

1. 분할정복 알고리즘

 분할정복(Divide and Conquer) 알고리즘은 여러알고리즘의 기본이 되는 방법중 하나로 복잡한 문제를 더 단순하고 작은 문제로 나누어 해결하는 방식으로 이루어집니다. 잘 알려진 예로는 병합 정렬(Merge Sort)과 퀵 정렬(Quick Sort)등이 있습니다. 

---

2. 분할 정복 알고리즘의 과정

 분할정복 알고리즘의 설계 과정은 세 단계로 이루어집니다. 이 각각의 과정은 분할(Divide), 정복(Conquer), 결합(Combine)이라고부릅니다. 

1. 분할(Divide): 해결하려는 문제를 더 작은 하위 문제로 나누는 과정.

 

2. 정복(Conquer): 나눈 하위 문제를 재귀적으로 해결. 단, 하위 문제를 더이상 분할할 수 없다면 직접 해결.

 

3. 결합(Combine): "정복" 과정이 끝난 문제의 해를 결합하여 원래 문제의 정답을 구함.

 

 

 모든 분할 정복 문제에서 이 과정의 기본적인 아이디어는 동일합니다.

※ 문제를 쪼개는 과정에서의 아이디어가 중요하다.

※ 재귀함수를 사용함으로, stack over flow등의 메모리 관련 이슈가 잦아 주의할 필요가 있다.

---

3. 분할 정복을 쓰는 문제들

 분할 정복은 정말 유용한 알고리즘입니다. 그렇다면 어떤 문제일때 이런 알고리즘이 사용될까요?

① 문제해결 과정의 재귀적 구조

 하위 문제들을 다시 분할하고 해결하는 과정이 재귀적으로 이루어질 수 있어야 합니다. 각 단계에서 문제를 계속 나누고 해결할 수 있는 구조를 가지고 있어야 합니다.

② 하위 문제의 독립성

 각 하위 문제는 다른 하위 문제와 독립적이어야 합니다. 이는 각 하위 문제를 병렬로 해결할 수 있어야 하기 때문이죠. 하위 문제 간의 의존성이 클 경우 분할정복 알고리즘의 효율성이 떨어질 수 있습니다.

③ 효율적인 분할 및 정복

 분할 과정과 정복 과정이 모두 효율적이어야 합니다. 예를 들어, 분할 과정에 O(n) 시간이 걸리고, 정복 과정에 O(n log n) 시간이 걸리는 경우 전체 알고리즘의 효율성이 높아지게 됩니다. 만약 이러한 과정들이 비효율적이라면 분할정복 알고리즘의 이점을 살리기 어렵습니다.

 

 분할정복 알고리즘은 위 조건들이 충족되는 문제에 적용할 때 매우 강력한 알고리즘입니다. 이를 통해 복잡한 문제를 보다 간단하고 효율적으로 해결할 수 있습니다.

 

---

4. 분할 정복의 대표적 예시

- 병합 정렬(Merge Sort)

 

- 퀵 정렬(Quick Sort)

 

- 이진 탐색(Binary Search)