[Week3] 분할 정복 (Divide and Conquer)

분할 정복

그대로 해결할 수 없는 문제를 작은 문제로 분할하여 문제를 해결하는 방법이다. 

대표적인 예로는 정렬 알고리즘 중에서 퀵 정렬이나 합병 정렬이 있으며,

이진 탐색, 선택 문제, 고속 푸리에 변환(FFT) 문제들이 대표적이다. 

 

분할 정복 설계

1) Divide

원래 문제를 더 작은 하위 문제로 분할하는 과정이다.

이 단계에서 문제를 해결하기 쉬운 형태로 나누어야 한다. 

이 과정은 주어진 문제가 분할하여 비슷한 유형의 더 작은 하위 문제로 나눌 수 있을 때까지 계속된다. 

 

2) Conquer

각 하위 문제를 재귀적으로 해결한다. 

하위 문제의 규모가 나눌 수 없는 단위가 되면 탈출 조건을 설정하고 해결한다. 

 

3) Combine (= Merge)

Conquer한 문제들을 통합하여 원래 문제의 답을 얻어 해결한다. 

 

※ Divide를 제대로 나누면 Conquer하는 과정은 자동으로 쉬워진다. 따라서, Divide를 잘 설계하는 것이 중요하다!

※ 분할 정복 알고리즘에는 재귀 알고리즘이 많이 사용되는데, 이 부분에서 분할 정복 알고리즘의 효율성을 깎아내릴 수 있다. 

 

 

분할 정복 특징 및 장단점

• 분할된 작은 문제는 원래 문제와 성격이 동일하다. → 입력 크기만 작아짐
• 분할된 문제는 서로 독립적이다. (중복 제거 x) → 순환적 분할 및 결과 결합 가능

분할 정복은 Top-Down 방식으로 재귀 호출의 장단점과 똑같다고 보면 된다. 

장점	단점
- Top-Down 재귀방식으로 구현하기 때문에     코드가 직관적이다.  - 문제를 나누어 해결한다는 특징상    병렬적으로 문제를 해결할 수 있다.	- 재귀 함수 호출로 오버헤드가 발생할 수 있다.  - 스택에 다량의 데이터가 보관되는 경우   오버플로우가 발생할 수 있다.

 

---

 

합병 정렬

하나의 리스트를 두 개의 균등한 크기로 분할하고 분할된 부분 리스트를 정렬한 다음, 

두 개의 정렬된 부분 리스트를 합하여 전체가 정렬된 리스트가 되게 하는 방법이다. 

 

동작 과정

1) Divide

입력 배열을 같은 크기의 2개의 부분 배열로 분할한다. 

 

2) Conquer

부분 배열을 정렬한다. 

부분 배열의 크기가 충분히 작지 않으면 (left < right) 순환 호출을 이용하여 다시 분할 정복 방법을 적용한다. 

 

3) Combine

정렬된 부분 배열들을 하나의 배열에 합병한다. 

 

---

 

퀵 정렬

특정 원소(pivot)을 기준으로 주어진 배열을 두 부분 배열로 분할하고

각 부분 배열에 대해 퀵 정렬을 순환적으로 적용하는 방식이다. 

 

동작 과정

1) Divide

피봇 하나를 선택하여 피봇을 기준으로 2개의 부분 배열로 분할한다. 

 

2) Conquer

피봇을 기준으로 피봇보다 큰 값, 혹은 작은 값을 찾는다.

왼쪽에서부터 피봇보다 큰 값을 찾고 오른쪽에서부터는 피봇보다 작은 값을 찾아서 두 원소를 교환한다. 

분할된 부분 배열의 크기가 0이나 1이 될 때까지 반복한다. 

 

3) Combine

Conquer 과정에서 값의 위치가 바뀌므로 따로 결합은 하지 않는다. 

 

---

 

이진 탐색

정렬된 데이터를 효과적으로 탐색할 수 있는 방법이다. 

(정렬된 데이터만 사용 가능)

 

동작 과정

1) Divide

배열의 가운데 원소를 기준으로 왼쪽, 오른쪽 부분 배열로 분할한다. 

탐색키와 가운데 원소가 같으면 분할을 종료한다. 

 

2) Conquer

탐색키가 가운데 원소보다 작으면 왼쪽 부분 배열을 대상으로 이진 탐색을 순환 호출하고,

크면 오른쪽 부분 배열을 대상으로 이진 탐색을 호출한다. 

 

3) Combine

탐색 결과가 직접 반환되므로 결합이 불필요하다. 

 

 

참고

https://loosie.tistory.com/237

[알고리즘] 분할정복 알고리즘 정리 (합병 정렬, 퀵 정렬, 이진 탐색) (Java)