분할 정복 (Divide and Conquer)

분할 정복 알고리즘 : 문제를 더 이상 나눌 수 없을 때까지 나누고, 이렇게 나누어진 문제들을 각각 풂으로써 결국 전체 문제의 답을 얻는 알고리즘

 

ex) 퀵 정렬

-> 임의의 기준 요소(pivot)을 정하고 기준 요소보다 작은 요소들을 왼편으로, 큰 요소들은 오른편으로 옮긴다. 그 다음에 기준 요소에 의해 나누어진 양 편에 있는 요소들에 대해 왼쪽/오른쪽에 대하여 각각 분할을 수행한다. 그리고 이렇게 분할된 데이터 집합들을 더 이상 분할 할 수 없을 때까지 계속해서 분할한다. 더 이상 분할 할 수 없을 때는 이미 정렬이 끝난 경우 이다.

 

핵심 : 문제를 잘게 쪼개기

<요령>

1. 분할(Divide) : 문제가 분할이 가능한 경우, 2개 이상의 하위 문제로 나눈다.

2. 정복(Conquer) : 하위 문제가 여전히 분할이 가능한 상태라면 하위 집합에 대해 1을 수행한다. 그렇제 않다면 하위 문제를 푼다.

3. 결합(Combine) : 2과정에서 정복된 답을 취합한다.

 

분할 정복 기법으로 문제를 나눌 때 생기는 각 하위 문제는 완전히 독립적이다.

-> 이 사실은 곧 큰 문제로부터 나뉘어 떨어진 문제들은 여러 프로세스, 네트워크 상의 여러 컴퓨터에 의해 병렬 처리가 가능해진다.

 

분할 정복 알고리즘을 구현하는 데에는 재귀 호출이 많이 사용된다.

-> 문제를 잘게 나눔으로써 얻어진 알고리즘의 효율성을 재귀 호출 비용이 깎아 내린다는 단점이 존재

 

- 병합 정렬(Merge Sort)

- 거듭 제곱

- 피보나치 수

---

- 병합 정렬 (Merge Sort) : 퀵 정렬과 같이 분할 정복에 기반한 알고리즘이다.

 

1) 정렬한 데이터 집합을 반으로 나눈다.

2) 나누어진 하위 데이터 집합의 크기가 2이상이면 이 하위 데이터 집합에 대해 1)을 반복한다.

3) 원래 같은 집합에서 나뉘어져 나온 하위 데이터 집합 둘을 병합하여 하나의 데이터 집합으로 만든다.

단, 병합할 때 데이터 집합의 원소는 순서에 맞춰 정렬한다.

4) 데이터 집합이 하나가 될 때까지 3)을 반복한다.

 

알고리즘을 구현할 때 두 하위 데이터 집합을 병합하는 부분은 조금 더 관심을 기울여줘야한다.

-> 병합 정렬의 성능을 좌우하므로

 

두 데이터 집합을 정렬하며 합치는 방법

1) 두 데이터 집합을 합한 것만큼의 비어 있는 데이터 집합을 마련한다.

2) 두 데이터 집합의 첫 번째 요소들을 비교하여 작은 요소를 새 데이터 집합에 추가한다.

그리고 새 데이터 집합에 추가된 요소는 원래의 데이터 집합에서 삭제한다.

3) 양쪽 데이터 집합이 빌 떄까지 2)과정을 반복한다.

 

<병합 정렬 알고리즘의 구현>

분할 정복에 기반하여 설계된 모든 알고리즘은 재귀 호출을 이용하면 자연스럽게 구현이 가능합니다. 병합 정렬도 마찬가지입니다. 나누고, 병합하는 과정을 재귀 호출을 이용하여 구현할 수 있다.

---

- 거듭제곱 

 

1)

C^8 = C  *  C  *  C  *  C  *  C  *  C  *  C  *  C

C^8 = C^4  *  C^4 = (C^4)^2 = ((C^2)^2)^2

 

2)

C^n = C^(n/2)  *  C^(n/2)                (n은 짝수)

      = C^((n-1)/2)  *  C^((n-1)/2)  *  C (n은 홀수)

 

1)의 방법에서 2)의 방법으로 변경하는 경우 O(n)에서 O(log 2 n)으로 줄어든다.

---

- 피보나치 수

 

재귀 함수를 이용하는 경우 O(2^n)

분할 정복을 이요하는 경우 O(log 2 n)