분할정복(Divide And Conquer)은, 문제를 작게 쪼게서 각각 해결한 후, 다시 전체가 되게 합쳐서 문제를 해결하는 알고리즘이다.
기본 프로세스는 다음과 같다.
1. Divide: 문제를 여러개의 작은 문제로 나누다.
2. Conquer: 각 문제를 재귀적으로 호출하면서 푼다. 작게 나누다가, 직관적인 방법으로 풀 수 있는 상태까지 도달하면 풀고, 리턴
3. Combine: 작게 나눠진 문제를 결합하면서, 원래의 문제가 될 때까지 결합
여기서 들 수 있는 의문은, '문제를 잘게 쪼게서 푼다고 해서, 전체 해결해야 할 문제의 양은 줄어 드는게 아닐 텐데, 왜 괜히 쪼게는 것인가?'일 것이다. (이런 의문이 안 들었다면, 할 수 없고..^^)
맞는 말이다. 그냥 쪼게면 안된다. 기하 급수적인 갯수가 되도록 나눠야 하고, 최종 나눠진 상태에서 문제를 해결할 때 쉽게 문제가 해결되도록 쪼게져야 한다.
무슨 말인지는 좀 더 설명을 들어야겠지만, 위에서 말한 사항을 염두에 두고 설명을 들어보자.
* 본격적인 설명
분할정복 알고리즘을 사용한 대표적인 문제로는 Merge Sort가 있다. 이 Merge Sort를 이해하면, 분할정복 알고리즘이 이해된다.
Merge Sort는 다음과 같은 알고리즘이다.
1. Divide: 주어진 배열을 잘게 쪼겐다.
2. Conquer: 각 쪼게진 배열내에서 수를 정렬한다.
3. Combine: 각 정렬되어진 쪼게진 배열들을, 처음 배열크기가 되기까지 조금씩 큰 덩어리로 합친다.(merge)
위 프로세스만으로는 감이 잘 안올 수 있다. 아래 예제 그림을 보면 감이 올것이다.
{6,5,3,1,8,7,2,4} 이렇게 8개의 수를 정렬하는 예를 생각해보자.
이 배열을 아래와 같이, 각각 절반씩 나눠서 최종 2개 이하의 원소를 가지는 배열로 만든다.
가장 밑에 있는, 2개씩의 수를 가진 배열들을 각각 정렬한다.
이제 4개씩 수를 가진 배열이 생겼는데, 이를 다시 배열내부에서 정렬한 후, 다른 배열과 합쳐 나간다.
이제 어떤 식으로 Merge Sort가 동작되는 지는 대강 감이 잡혔을 것이다. 작은 단위까지로 분할한 후, 각자 소팅 한 후, 다시 다른 작은 단위들과 합쳐가면서 소팅.
근데, 다시 드는 의문이겠지만, 왜 이렇게 해야하는 걸까? (이런 의문이 안 드시는 분은...이 페이지를 더 이상 안 봐도 됨)
최종 해답은 소팅 속도를 빨리하게 위함 이겠지만, 왜 이렇게 하면 속도가 빨라질까?
이 질문에 대한 답을 얻기 위해서는, 우선 무식한 방법에 의한 소팅이 O(n2)의 Running Time을 가지고 있고, Merge Sort가 O(n log n)이 된다는 것을 알아야 한다.
O(n2)은 Big-O 노테이션으로, 해당 알고리즘의 수행시간이 최대 (C x n2)을 넘지 않는다는 것을 만한다. 여기서 C는 임의의 상수.
예를 들어, 알고리즘의 수행 횟수를 예상해 봤더니 n개의 입력값에 대해 (2n2+3) 정도의 수행 횟수가 예상된다면, 이 알고리즘은 O(n2)이다. 왜냐하면 n>=1이상일 때, 2n2+3 <= Cn2되는 C가 존재하기 때문(C>=5이면 성립)
먼저, 무식한 방법에 의한 소팅이 O(n2) 이라는 것을 알아보자.
어떤 수들이 주어졌을 때, 이를 소팅하는 가장 간단한 방법은, 첫번째 수를 선택 후, 이 수와 나머지 수 전체를 비교해서 제일 작은 수를 첫번째 위치로 옮기고, 그 다음 나머지 수에 대해서 다시 제일 작은 수를 찾아서 그 다음 위치에 놓고..하는 것을 반복하는 것이다.
예를 들어, 1에서 n까지의 수가 있을 때,
첫번째 수: n개 수에 대해서 가장 작은 값 찾는다. (n-1)회 비교 연산
두번째 수: 첫번쨔 수를 제외한 나머지 n-1개 수 중에서 가장 작은 값을 찾는다. (n-2)회 비교 연산
...
n-1번째 수: 2개 수에 대해서. 1회 비교
n번째 수: 1개수에 대해서. 비교 없음.
이렇게 되면 전체 비교연산 횟수는 (n-1) + (n-2) + ... + 1 = n2/2 이 된다. (등차수열의 합=n(초항+종항)/2)
Big-O 노테이션으로 표현하면 O(n2)
이제, Merger Sort에 의한 정렬이 O(n log n)이 됨을 알아보자.
먼저, 가장 작은 단위들로 나눠져 있을 때, 이 것들에 대해서 각각 소팅하는 것이, 어느 만큼의 비교연산이 이루어지는 가를 생각해 보자.
답은 n 회이다. (입력되는 수가 n개 일 때)
위쪽에서 예를 들었던 것을 가지고 생각해 보자.
(6,5) (3,1) (8,7) (2,4) -> (5,6) (1,3) (7,8) (2,4)
모두 8개의 수이고, 4개 그룹으로 되어 있다. 각 그룹마다 비교 한 번씩 하면 되므로, 총 4회면 된다.
이제 4개의 수를 가진 두 개의 그룹으로 소팅해서 합치는 데 걸리는 횟수를 생각해 보자.
(5,6) (1,3) (7,8) (2,4) -> (1,3,5,6) (2,4,7,8)
총 8회면 된다. 아래 그림을 보고 이해해 보자.
왼쪽편 그룹내 인덱스 포인트를 i로, 오른편 인덱스를 j, 소팅될 배열의 인덱스를 k라 할 때, k를 하나씩 증가시키면서, 그 때마다 현재의 i, j의 값을 비교해서 작은 것을 소팅배열에 집어넣는 구조.
첫번 째 k=1일 때 보면, 왼쪽 그룹에서 i번째 값과 오른쪽 그룹의 j번째 값을 비교해 보면, 오른편 값 1이 더 작기에, 이 값을 소팅되는 배열에 넣고, 오른편 인덱스인 j를 하나 증가 시킨다.
이제 k=2일 때도, 위에서와 동일하게 왼쪽 i=1일 때의 값과, 이제는 증가되어 값이 2가 된 오른편 j=2일 때의 값을 비교해서, 오른편 값인 3이 더 작으므로 소팅배열값에 3을 넣는다.
이렇게 진행하면 총 4회 비교를 통해, 소팅배열 완성. (6,5) (3,1) -> (1,3,5,6)
(7,8) (2,4)에 대해서도 마찬가지로 진행하면 4회 비교가 소요되고, 따라서 (5,6) (1,3) (7,8) (2,4) -> (1,3,5,6) (2,4,7,8) 처럼 정렬하는 데는 총8회의 비교연산이면 된다.
이제 다시, (1,3,5,6) (2,4,7,8)를 (1,2,3,4,5,6,7,8)로 되게 해야하는데, 이것도 마찬가지로 생각하면 총 8회 비교면 된다.
따라서, 정리해 보면,
(6,5) (3,1) (8,7) (2,4) -> (5,6) (1,3) (7,8) (2,4) : 4회
(5,6) (1,3) (7,8) (2,4) -> (1,3,5,6) (2,4,7,8) : 8회
(1,3,5,6) (2,4,7,8) -> (1,2,3,4,5,6,7,8) : 8회
--------------------------------------------
총20회
이제 n개의 수에 대해서 생각해 보자.
(a1,a2) (a3,a4) (a5,a6) ... (an-1,an) 정렬 : n/2 회
(a1,a2) (a3,a4) (a5,a6) ... (an-1,an) -> (a1,a2, a3,a4)(a5,a6, a7,a8) ... (an-3,an-2, an-1,an) : n회
.... : n회
...
n개의 수에 대해서, 이미 소팅된 그룹들을 소팅하면서 합치는데는 n회 비교만 수행되는 것을 알 수 있다.
(물론, 가장 처음에 정렬만 하는 데는 n/2회 만큼이지만)
그렇다면, 이러한 합치는 과정이 몇 번이나 이뤄질까? 답은 log n 번이다.
위에서 예를 든 8개 수에 대해서는 3번 이뤄졌다. 8을 계속해서 2로 나눠서 1이 될 때까지 나누는 것과 동일
8 -> 4 -> 2 -> 1
즉, 2x = 8 , x = log 8 = 3
n개 수에 대해서는 log n 번 수행됨.
즉, MergerSort에서 전체 실행횟수는 (log n - 1)n + n/2 = n x log n - n/2 = O(n log n)
O(n2)과 O(nlogn)은 엄청난 차이다. 특히, n이 커질수록 그 차이는 더 심해진다.
만약 1회 수행하는데 1마이크로초(10-6)걸린다고 했을 때, n이 100이라면, n2은 0.01초이고 nlogn은 0.001초(뭐 그닥 차이를 모르겠다.)
근데, n이 십만(100,000)일 때는, n2은 10,000초(약2.7시간) 걸리고 nlogn은 1.66초 !!!
(100만개가 넘은 것에 대해서 처리할 때, n2 수행시간을 가지는 알고리즘은 사실상 사용 불가. 몇 년 정도 돌려야 되니깐. 그치만, nlogn 수행시간을 가지는 알고리즘으로 구현가능하다면 100만이어도 수십초 이내에 수행가능)
* MergeSort 구현
MergeSort를 실제 구현해보면 아래와 같을 것이다.
package divideandconquer;
public class MergeSort {
public static void main(String[] args){
MergeSort mergeSort = new MergeSort();
int[] a = {6,5,3,1,8,7,2,4};
println(a);
mergeSort.sort(a);
println(a);
}
private static void println(int[] a){
for(int i=0;i<a.length;i++){
System.out.print(a[i]+" ");
}
System.out.println("");
}
public MergeSort(){
}
public void sort(int[] src){
int[] buf = new int[src.length];
mergeSort(src,0,src.length-1,buf);
}
private void mergeSort(int[] src, int s, int e, int[] buf){
//System.out.println("mergeSort(a,"+s+","+e+")");
if((e-s)<1) return;
int m = (s+e)/2;
mergeSort(src,s,m,buf);
mergeSort(src,m+1,e,buf);
merge(src,s,m,e,buf);
System.arraycopy(buf, s, src, s, (e-s)+1);
}
private void merge(int[] a, int s, int m, int e, int[] buf){
//System.out.println("merge("+s+","+m+","+e+")");
int left=s,right=m+1;
for(int k=s;k<=e;k++){
buf[k] = (left<=m && (right>e || a[left]<=a[right] )) ? a[left++] : a[right++];
/*
if(left<=m && (right>e || a[left]<=a[right] )){
buf[k]=a[left];
left++;
}else{
buf[k]=a[right];
right++;
}
*/
}
//println(sorted);
}
}
핵심이 되는 메서드는 mergeSort()와 merge() 인데,
mergeSort()의 입력 파라미터를 보면
- int[] a : 입력 대상이되는 배열
- int s: start
- int e: end
- int[] buf: 소팅된 값을 보관하는 buffer 배열
이 mergeSort() 내에서,
mergeSort(src,s,m,buf) : 왼쪽편에 대한
mergeSort(src,m+1,e,buf): 오른편에 대한
merge(src,s,m,e,buf) : merge
merge() 메서드에서는,
왼쪽편 배열과 오른쪽편 배열의 인덱스를 증가시키면서 값을 비교해서, 작은 값을 buffer배열에 넣는 구조.
여기서 주의할 것은,
-왼쪽편 인덱스인 left값이 m보다 커졌다는 것은, 왼쪽편 배열에는 비교 대상이되는 수가 없다는 것이기에, 무조건 오른편 값을 선택
if(left > m) --> buf[k] = a[right]
-오른편 인덱스인 right값이 e보다 커졌다는 것은, 오른편 배열에 비교 대상이되는 수가 없는 것이기에, 무조건 왼편 배열값 선택
if(right > e) --> buf[k] = a[left]
이러한 조건들을 다 고려해서 한 줄로 코딩한 것이,
private void merge(int[] a, int s, int m, int e, int[] buf){
int left=s,right=m+1;
for(int k=s;k<=e;k++){
buf[k] = (left<=m && (right>e || a[left]<=a[right] )) ? a[left++] : a[right++]; }
}
* Divide And Conquer에 대한 복기
다시 한번 분할정복 알고리즘에 대해 생각해보면,
- 쉽게 생각해서, O(n2) 정도 걸리는 것을 O(nlogn)이 되게 하는 알고리즘
- O(nlogn)이 되게 할려면, 재귀적으로 절반씩 계속 나눠서(급격하게 나눠질 수 있게 해서), 전체 나누는 횟수가 log n 정도가 되게.
- 이 때, 각 나눠진 상태에서 원래 원하는 작업(=정렬)은 n회에 가능해야 함
위 조건을 만족하게 할 수 있다면, 분할정복 알고리즘이 되는 것
* 다음 주제
MergeSort를 위와 같은 접근방법말고(TopDown), 다른 접근 방법이 있다(BottomUp)
이 방법을 알아볼 것이다.
-끝-
'알고리즘 > 알고리즘(Java)' 카테고리의 다른 글
| [분할정보]Counting Inversions (0) | 2015.10.27 |
|---|---|
| [분할정복]MergeSort_BottomUp (0) | 2015.10.26 |
| 25. [다이나믹]효율적인 행렬곱 순서 (0) | 2015.04.26 |
| 24.[다이나믹]조립라인 스케줄링(Assembly Line Scheduling) (0) | 2015.04.25 |
| 23. [다이나믹]옷 (0) | 2015.04.24 |