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

 독일의 천재 수학자 가우스는 초등학교 시간에 1부터 100까지의 숫자를 모두 더하라는 선생님의 질문에 계산을 순식간에 끝냈다고 한다. 1부터 100의 숫자는 등차수열로 연속된다. 따라서 1과 100, 2와 99, 3과 98이 서로 짝지어져 있고, 이 계산이 총 50번 반복되는 구조를 갖는다. 따라서 101 * 50이라는 단 한번의 연산으로 1부터 100까지의 모든 합계를 구해냈다. 이 공식은 나중에 등차수열의 합계를 구하는 기본 공식이된다. 이 처럼 1부터 100까지 더하는 문제를 두개씩 짝지어 풀어야 되는 부분은 50개로 나눈다면 쉽게 풀어낼 수 있다. 이처럼 일정한 문제를 동일한 크기의 n개로 나누어 푸는 방식을 분할 정복 알고리즘 (Divide and Conquer)라고 한다.

  분할 정복 알고리즘은 부분 정복 알고리즘에 속한다. 분할 정복 역시 문제를 풀기 위해 크기를 줄여 나가는 방식이다. 하지만, 분할 정복이 경우 나누는 크기가 일정해야 한다. 부분 정복 알고리즘 중에서 문제를 동일한 크기의 n개로 나눌 수 있다면 부분 정복 알고리즘에 해당된다. 분할 정복의 기본 매커니즘은 큰 문제를 여러개로 쪼갠뒤 다시 합쳐 정답을 구하는 방식이다. 이를 단계로 나눈다면 크게 3가지로 나뉜다. 첫번째 문제의 분할(Divide), 그리도 두번째 정복(Conquer) 마지막으로 알고리즘의 정답을 구하기 위한 병학(Combine)과정이다. 아래 여러 문제들을 보며 대표적인 분할 정복 알고리즘을 살펴보자. 

1. 합병정렬(Merge Sort)

  대표적인 정렬 세가지(선택, 삽입, 버블)의 시간 복잡도는 O(n^2)이다. 이를 분할 정복법을 활용한다면 O(n log n)으로 줄일 수 있다. 합병정렬의 이론은 간단하다. 전체 데이터 셋을 절반의 크기로 나눠 나간다. 그렇게 하나의 원소가 남을때 까지 계속 나눠 나간 뒤, 나눈 순서의 역순으로 데이터를 다시 합쳐나가는 방식이다. 합병하는 과정에서 전체 데이터 n개에 대해 비교 연산을 진행하게 되고. 합병을 총 log n번 진행하게 된다. 잘 이해가 되지 않는다면 아래의 Pseudo Code를 살펴보자.

  총 8개의 숫자에 대해 합병 정렬을 수행한다고 가정하자. 자료를 총 8개로 나누게 되고 0번과 1번 자료를 정렬하고, 2번과 3번 자료를 정렬하고, 최종적으로 6번과 7번자료를 정렬하며 합병 정렬의 첫번째 Merge가 완료된다. 이 때 총 8번의 자료 비교를 실시한다. 그리고. 0,1번 자료를 정렬한 배열과 2,3번자료를 정렬한 배열 2개에 대한 합병을 위의 코드와 같이 실행하고, 이 경우 총 4번의 자료 검색을 한다. 마찬가지로 4,5번과 6,7번을 정렬한 배열도 같이 수행한다. 이번 단계에서도 총 8번의 비교가 수행 되었다. 마지막으로 0~3번 정리 세트와 4~7번 정리 세트를 정렬한다. 이렇게 총 8(n)번의 수행을 log 8=3(log n)번 수행하게 된다. 따라서, 시간 복잡도는 O(n log n)이 된다.

  합병 정렬의 장점은 별도의 사전 작업 없이 모든 자료에 적용이 가능하다는 점이다. 두 번째는 Stable Sort라는 점이다. 뒤에 다시 소개하겠지만, 예를 들어 A[3] = 100 과 A[11] = 100처럼 동일한 자료가 있다면 두 자료 형의 순서가 바뀌지 않고 정렬되게 된다. 정렬이 끝나고 난 뒤에도 A[3]이 A[11]보다 앞에 오게 된다. 이런 장점으로 인해 Merge Sort는 정렬 방법 중에서 인기가 높은 방법이다. 정렬에 필요한 시간 복잡도를 크게 줄일 수 있다. 또한 자료형의 정렬 정도에 따라 시간의 차이가 많이 발생하는 다를 정렬과 달리 합병 정도는 평균적으로 비슷한 결과를 출력하게 된다. 

  물론 단점도 존재한다. 위에서 살펴 보듯이 분할과 합병 과정이 재귀적으로 작동하기 때문에 자료형이 커지게 되면 컴퓨터에 심각한 과부화를 가져온다. 재귀적으로 함수를 불러오게 되면 컴퓨터에서 스택 오버플로우가 발생되 프로그램이 제대로 작동하지 않을 가능성도 충분하다. 그리고 합병을 위해 n개의 자료형에 대한 추가 공간이 필요하다. 8개의 자료형을 합병 정렬 하기 위해서는 해당 자료형을 저장 할 수 있을 만한 크기의 배열이 추가적으로 필요하다.

 

 2. 퀵 정렬(Quick Sort)

  언뜻 보기에 합병 정렬은 기본 정렬보다 훨씬 빠르고 좋아 보이지만, 아래 단점으로 인해 많이는 쓰이지만 가장 많이 쓰이지는 않는다. 실제로 우리가 다루는 데이터는 수백만의 수치는 손쉽게 넘어가므로 재귀적으로 구현했다간 쉽게 오버플로우가 발생할 것이다. 그래서 우리가 가장 실제로 많이 쓰게 될 정렬 방식은 바로 퀵정렬이다.

  퀵 소트의 이론은 데이터에 있는 자료 중 하나를 Pivot으로 정한다. 그리고 그 값을 기준으로 좌우측에 해당 값보다 작은지 분류해가며 정리한다. 그리고 Pivot 위치를 기준으로 우측 절반과 좌측 절반에 대해 정렬을 재귀적으로 실행한다. 이 과정을 거친다면 조금 더 수월하게 정렬을 실시 할 수 있다. 예를 들어 1부터 16까지의 숫자가 무작위로 배열되어 있다고 생각해보자. 1번 원소가 5라고 하면 자료형 처음부터 비교해 가면서 5 원소 기준 좌측에 5보다 작은 수 우측에 5보다 큰 수를 배치한다. 총 n번의 작업으로 분류를 마칠 수 있다. 그 다음 5를 기준으로 다시 좌측에 대해 정렬을 실시하고, 우측으로 정렬을 실시한다. 매번 정 중앙의 수를 운 좋게 선택할 수 있다면 정 중앙으로 계속 떨어지게 되고 시간 복잡도는 O(n log n)이 된다.

  

퀵 정렬에서 수행하게 되는 비교를 도표로 설명하면 아래와 같다.

  Low의 경우 Pivot보다 작으면 그대로 통과하고. 크면 자리를 변경한다. 반대로 High는 Pivot보다 크면 통과하고, 작으면 low와 자리를 변경한다. 그리고, Low와 High의 자리가 바뀌게 되면 비교를 종료한다.

  퀵정렬과 합병 정렬은 Log n 방식으로 자료형을 나눈다는 점에서 매우 유사해 보이지만 몇가지 다른점이 존재한다. 합병 정렬은 자료 형에 따른 영향이 거의 없으나 퀵정렬은 자료형에 따라 걸리는 시간의 영향이 매우 크다. 예를들어 Pivot값으로 가장 큰 수나 작은수를 계속 고르게 된다면 알고리즘의 시간 복잡도는 O(n^2)이 된다. 물론, 자료형이 무작위로 정렬되어있다면 그럴 가능성은 매우 적기는 하지만, 위에서 보듯 Pivot값에 따라 나눠야 하는 기준이 달라질 수 있는 것이 퀵소트다. 

  그리고, 퀵 정렬을 합병 정렬과 달리 추가적 공간이 필요하지 않다. 배열 내부에서 서로 교환하는 과정을 거쳐 정렬을 완료할 수 있다. 또한, 합병 정렬 처럼 분할과 합병 과정이 필요하지 않고 정렬이 가능하다. 그래서, 합병 정렬보다 안정성은 떨어지지만, 컴퓨터 설계에서 추가적인 데이터가 필요 없고, 사전 작업이 최소화 된다는 점에서 큰 효율을 발휘하게 된다.

  퀵 정렬의 단점으로 지적 받게되는 자료에 따른 안정성 문제를 극복하기 위해 여러가지 방안이 있는데, 주로 쓰이는 방법이 전체 데이터 중에서 몇개를 선정하여 중앙 값을 Pivot으로 설정하는 것 혹은 데이터의 정 중앙 값을 Pivot으로 설정하는 방법이 있다.

 3. 최근접 점의 쌍 구하기(Closest Fair)

  두 점 사이의 거리를 구하는 공식은 다음과 같다.

  이 공식을 활용하여 평면 상에서 최근접 점의 쌍을 구하는 방법에 대해 생각해보자.

  

  위와 같은 평면 상에 존재하는 모든 점의 거리 중 가장 가까운 두 점이 무엇인지 구하는 문제를 푼다고 가정해보자. 만약 점이 총 20개가 있는 평면이 있다고 존재한다면 구해야 하는 거리의 개수는 190개가 나오게된다. 총 20개의 원소 중 2개를 선택하는 조합과 같은 횟수다. 이 문제에 분할 정복 알고리즘을 적용한다면 조금 더 간단한 문제로 변하게 된다. 평면상의 점들을 두부분으로 나눠보자.

  20개의 점들을 10개씩 나눈 다음에 각 평면에 대해 최소점을 구하게 된다면 우리가 검색해야 하는 두 점 사이의 길이는 한 평면당 45개로 줄어들게되고, 평면이 2개 이므로 45를 두번 수행하는 90번 연산으로 줄어든다. 그리고, 양 평면에서 나온 최근접 점을 비교한다면 더욱 쉽게 최근점 점을 구할 수 있다. 마찬가지로 평면을 4개로 줄이게 된다면 총 40번의 연산으로 줄어든다.

  하지만, 여기서 고려해야 되는 중요 요소는 바로 서로 다른 평면에 존재하는 점에서 최근접 점이 발생하는 경우이다. 위 그림과 같이 1번 평면에서 최소거리가 10, 2번 평면에서 최소거리가 15가 나왔지만, 다른 평면에 존재하는 두 점 중 최소거리가 7인 점이 존재하는 경우다. 이런 예외 처리를 막기위해서 아래와 같은 방법을 쓴다.

  두 평면이 서로 맞닿은 방향의 가장자리를 기준으로 최소 거리인 10을 기준으로 그 안에 있는 점들간의 간격을 구한다. 현재 좌측 평면에는 해당 범위에 속한 점이 총 5개가 있고, 우측 평면의 경우 총 4개가 존재한다. 좌측의 한 점과 우측의 한 점을 순차적으로 선택하여 10보다 짧은 두 점을 구하면 된다. 좌측의 점 5개에 대해 4개씩 거리를 구하게 되므로 20개의 거리 연산을 추가적으로 실시한다.

  BruteForce 알고리즘 기준으로 두 점 사이의 거리 연산을 총 190번 실시해야 한다. 반면 Divide & Conquer 방식을 적용한다면, 45번의 연산을 두 평면에서 진행하고, 20번의 추가 연산을 실시하면 되므로 총 110번의 연산이 실시된다. 물론, Divide & Conquer 에서는 두 평면 사이의 비교, 가장자리에 존재하는 점들 구하기, 가장자리에 존재한 접점간의 비교를 하는 3번의 추가 비교 연산이 존재한다.

  최근접 점의 쌍을 찾는 알고리즘을 Brute Force으로 구현한 코드는 아래와 같다.

import java.util.*;
 
public class Solution {
    
    static int[][] position;
 
    public static void main(String[] args) {
        // TODO Auto-generated method stub
 
        Scanner sc = new Scanner(System.in);
        
        int N =sc.nextInt(); // 점의 개수
        
        position = new int[N][2]; // 각 점의 위치
        
        // 위치 입력
        for(int i=0; i<N; i++){
            position[i][0]=sc.nextInt(); // x값 위치
            position[i][1]=sc.nextInt(); // y값 위치
        }
        
        // 거리 구하기
        double min = 1000;
        int minX=0;
        int minY=0;
        for(int i=0; i<N-1; i++){
            for(int j=i+1; j<N; j++){
                double tmp = calDist(i,j);
                if(tmp<min) {
                    min=tmp; minX=i; minY=j;
                }
                
            }
        }
        
        System.out.println(min+" "+minX+" "+minY);
        
    }
    
    public static double calDist(int a, int b){
    
        return Math.sqrt(Math.pow(position[a][0]-position[b][0],2)+Math.pow(position[a][1]-position[b][1],2));
        
    }
 
}
 

  아래의 코드는 Divide and Conquer로 구현한 코드이다.

import java.util.*;
 
public class Solution {
 
    static int[][] position;
    
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        
        Scanner sc = new Scanner(System.in);
        
        int N =sc.nextInt(); // 점의 개수
        
        position = new int[N][2]; // 각 점의 위치
        
        // 위치 입력
        for(int i=0; i<N; i++){
            position[i][0]=sc.nextInt(); // x값 위치
            position[i][1]=sc.nextInt(); // y값 위치
        }
        
        // x 중앙값 구하기
        int[] xArray = new int [N];
        for(int i=0; i<N; i++){
            xArray[i]=position[i][0];
        }
        double xMed = Xmedian(xArray);
        
        // 평면 2분할
        int firstNod=-1;
        int secondNod=-1;
        ArrayList<Integer> Divide1 = new ArrayList<Integer>();
        ArrayList<Integer> Divide2 = new ArrayList<Integer>();
        
        for(int i=0; i<N; i++){
            if(position[i][0]<=xMed){
                Divide1.add(i);
            }
            else{
                Divide2.add(i);
            }
        }
        
        // 각 분할에서 최소 값 선정
        double min1=1000;
        int node11 = -1; 
        int node12 = -1;
        for(int i=0; i<Divide1.size()-1;i++){
            for(int j=i+1; j<Divide1.size();j++){
                int a = Divide1.get(i);
                int b = Divide1.get(j);
                double tmp = calDist(a,b);
                if(tmp<min1) min1=tmp; node11=a; node12=b;
            }
        }
        
        // 각 분할에서 최소 값 선정
        double min2=1000;
        int node21 = -1;
        int node22 = -1;
        for(int i=0; i<Divide2.size()-1;i++){
            for(int j=i+1; j<Divide2.size();j++){
                int a = Divide2.get(i);
                int b = Divide2.get(j);
                double tmp = calDist(a,b);
                if(tmp<min2) min1=tmp; node21=a; node22=b;
            }
        }
        
        // 두 분할 중 더 최소값을 선정
        double falsemin=0;
        if(min1<=min2) {
            falsemin=min1; firstNod=node11; secondNod=node12; 
        }
        else {
            falsemin=min2; firstNod=node21; secondNod=node22;
        }
        
        // 중앙 부분 산정
        int medianXmin = (int) (xMed-falsemin)-1;
        int medianXmax = (int) (xMed+falsemin)+1;
        ArrayList<Integer> DivideMed = new ArrayList<Integer>();
        for(int i=0;i<N;i++){
            if((position[i][0]>medianXmin)&&(position[i][0]<medianXmax)){
                DivideMed.add(i);
            }
        }
        
        // 중앙 부분의 최소값 산정
        double realmin=falsemin;
        for(int i=0; i<DivideMed.size()-1;i++){
            for(int j=i+1; j<DivideMed.size();j++){
                int a = DivideMed.get(i);
                int b = DivideMed.get(j);
                double tmp = calDist(a,b);
                if(tmp<realmin) {
                    realmin=tmp; firstNod=a; secondNod=b;
                }
            }
        }
        
        System.out.println(realmin+" "+firstNod+" "+secondNod);
 
    }
    
    // 두점 사이의 거리를 구하는 공식
    public static double calDist(int a, int b){
        
        return Math.sqrt(Math.pow(position[a][0]-position[b][0],2)+Math.pow(position[a][1]-position[b][1],2));
        
    }
    
    // x 중앙값 구하기
    public static double Xmedian(int[] xArray){
        
        Arrays.sort(xArray);
        double answer=0;
        
        int size = xArray.length;
        // x 값이 짝수라면
        if(size % 2 == 0){
            int m = size / 2;
            int n = (size / 2) - 1;
            answer = (double)(xArray[m]+xArray[n])/2;
        }
        else{
            int m = size/2;
            answer = xArray[m];
        }
        
        return answer;
        
    }
 
}
 

  Divide Conquer 방법은 분할이 가능한 문제 내에서는 정말 좋은 효율을 발휘한다. 하지만, 이 알고리즘을 적용할 때 항상 주의해야 할 점이 바로 추가적으로 필요한 연산이 적어야 된다는 점이다. 위의 예시 같은 경우 정말 어마어마한 개수의 점을 입력하지 않는 이상 Brute Force의 실행속도가 더 빠를 것이다. 그 이유는 코드를 봐도 충분히 알 수 있다. Brute Force의 경우 불과 46줄의 코드밖에 되지 않는다. 컴퓨터가 해당 코드를 읽고 메소드를 수행해 최종적으로 컴파일 할때 소모되는 비용이 적다. 단지, 점들의 거리를 구하는 연산만 많을 뿐이다. 반면에, Divide Conquer 방식은 코드도 길어서 개발 시간도 오래 걸릴 뿐더러, 비교 연산이 2번이나 활용된다. 또 중앙값을 구하는 연산과 중앙 부분의 거리를 구하는 연산도 진행하게 된다. 종합적으로 분석했을 때, Divide Conquer 방법이 더 유리하다고 장담할 수 없다. 

  앞선 두 알고리즘 모두 적용에 신중해야한다. 문제 정확도는 떨어지면서, 오히려 시간이 더 오래 걸릴지도 모르게 된다. 물론, 프로그래밍 적으로 적용 했을때의 의미이다. 하지만, 분명 제대로 적용한다면 더 쉽고 빠르게 문제를 풀 수 있고 공간복잡도 문제도 쉽게 해결이 가능할 것이다. 이번 시간까지 시간 복잡도를 한단계 단축 할 수 있는 두개의 알고리즘에 대해 배웠다. 다음 시간에는 문제의 크기를 줄이는 방법이 아니라 형태 자체를 아예 변환화여 문제를 푸는 변환 정복 알고리즘(Transform and Conquer)에 대해 배워볼 것이다.