[알고리즘] 분할 정복 - Selection, Closest Pair 문제 해결

* 공부를 하며 정리한 글입니다. 수정할 점이 있다면 댓글 남겨주세요.

 

 

 

선택(Selection) 문제

 

 

 

 

주어진 수들 중 k 번째로 작은 수를 찾아야 하는 문제는 꽤나 자주 등장한다. 실제로 이러한 문제를 해결하는 알고리즘도 간단한 것이 많다. 예를 들어 최소 숫자를 k번 찾는 방법, 숫자를 정렬하고 k번째 숫자를 찾는 방법 등이 있다.

 

 

 

하지만, 앞서 말한 알고리즘의 시간 복잡도를 고려해보자. 각각 최악의 경우 O(kn)과 O(nlogn)이 소요된다. 그렇다면 이보다 더 효율적인 시간으로 k 번째 작은 수를 찾을 수 있을까? 여기에 있어 우리는 "Selection" 알고리즘을 사용할 수 있다.

 

 

 

미리 말하자면 선택(Selection) 알고리즘은 이진 탐색 알고리즘과 매우 유사하다. 이진 탐색은 원하는 수를 찾기 위해서 분할을 하고, 선택 알고리즘은 k번째 작은 수를 찾기 위해서 피봇으로 분할한다. 결국, 두 그룹으로 나누어 무언가을 하는 것은 동일하다는 것이다.

 

 

 

단, 이진 탐색은 분할 시 1/2로 분할하며, 정렬이 되어 있다. 반면 선택 문제는 입력이 정렬되어 있지 않고 퀵정렬과 같이 피봇을 기준으로 분할 한다.

 

 

 

 

 

 

 

선택(Selection) 문제의 수도 코드(Pseudo Code)

 

 

 

 

 

 

다음은 Selection 문제에 대한 수도 코드이다. 퀵정렬과 많이 비슷해서 크게 어렵지는 않을 것이다.

 

Selection(A, left, right, k)

입력 : A[left] ~ A[right]와 k, 단 1<=k<=|A|, |A| = right - left + 1
출력: A[left] ~ A[right]에서 k번째 작은 원소

partition(A, left, right) 과정(아래 1~3과정)
1. 피봇(Pivot)을 A[left] ~ A[right]에서 랜덤하게 선택한다. 
2. A[left]와 자리를 바꾸고, 피봇과 각 배열의 원소를 비교한다.
3. 피봇보다 작은 값은 A[left] ~ A[p-1]로 옮기고, 피봇보다 큰 값은 A[p+1] ~ A[right]로 옮긴다. 피봇은 A[p]에 둔다.


S = (p-1) - left + 1 // small group의 크기

if (k <= S) Selection(A, left, p-1, k) // small group에서 찾기

else if (k = S+1) return A[p] // 피봇 = k 번째 작은 숫자.

else Selection(A, p+1, right, k-S-1) // large group에서 찾기

 

 

 

 

🔲 S = (p-1) - left + 1

p는 피벗을 뜻하고, p-1은 small group의 제일 오른쪽 값이다. -left + 1을 해주어 그 크기를 구할 수 있다.

 

 

🔲 large group에서 k-S-1을 해주는 이유

k는 현재 찾고자 하는 k번째 큰 수이며, -S를 해주어 small group 자체를 빼준다. 1은 피봇 값을 의미한다.

즉, large group에서의 찾고자하는 k번째 큰 수를 찾기 위해 작성해 준 것이다.

 

 

 

 

Selection 알고리즘(Java)

public class Selection {

    public static int partition(int S[], int first, int last) {
        int i, j, temp;

        i = first + 1;
        j = last;

        while(i <=j) {
            if (S[i] <= S[first])  i = i+1;
            else if (S[j] > S[first]) j = j-1;
            else {
                temp = S[i];
                S[i] = S[j];
                S[j] = temp;
                i = i+1;
                j = j-1;
            }
        }

        temp = S[first];
        S[first] = S[j];
        S[j] = temp;
        return j;
    }

    public static int selection(int[] A, int first, int last, int k) {
        int  p, S;

        p = partition(A, first, last);
        S = (p-1) - first + 1;
        if (k <= S)
            return selection(A, first, p-1, k);
        else if (k == S+1) return A[p];
        else
            return selection(A, p+1, last, k-S-1);
    }
    public static void main(String[] args) {
        int A[] = { 48, 12, 70, 38, 75, 67, 96, 52, 81 };
        int k = 5;
        System.out.println(k + "번째로 작은 요소 : " + selection(A, 0, A.length - 1, k));
    }
}

 

앞서 설명한 수도 코드와 별 다를 게 없다. 대신 random 피벗의 값은 first 값으로 고정시켜 주었다.

 

 

 

 

 

 

 

 

 

Closest Pair(최근접 점의 쌍) 구하기

 

 

 

 

x와 y 좌표 값이 주어진 여러 개의 점들 중 가장 거리가 짧은 점들간의 거리를 구하는 것이 목적인 문제이다. 물론 깡으로도 구현할 수 있다. n개의 점들이 주어졌다고 할 때, 그 중 2개의 길이를 전부 구해 비교하면 그만이기 때문이다. 하지만 n개 중에서 2개를 뽑는 모든 경우의 수를 확인해야 하기에 O(n^2)의 시간 복잡도가 소요된다.

 

 

 

결국은 시간 복잡도다. 이를 위해 우리는 "분할 정복" 하는 알고리즘을 사용할 것이다. n개의 점을 반으로 분할하고, 각 부분문제에서 최근접 점의 쌍을 찾아 짧은 점의 쌍을 획득해야 한다.

 

 

 

 

지금까지 배운 "분할 정복"의 의미를 코드 영역에서 생각해보면, 재귀적으로 영역이 부분화되며 결국은 제일 작은 부분이 될 때까지 파고 들었다. 이후에 가장 작은 부분에서 간단하게 해결한 것들을 재귀 함수를 빠져나가며 "병합"하는 과정을 거쳤다. 

 

 

 

 

즉, 최근접 점의 쌍을 구하는 문제도 마찬가지다. 영역이 가장 작은 부분이 될 때까지 재귀적으로 파고들어야 한다. 가장 작은 부분에서는 점의 거리만 구하면 되는 비교적 간단한 작업이 기다리고 있을 것이다. 그 후에 "병합"의 과정에서 해당 거리의 값이 최소인지 검증하면 되는 것이다.

 

 

 

 

뭐 그냥 "분할 정복"의 응용 버전 아니야? 라고 생각이 들 수 있다. 하지만 이 문제에서 제대로 고려해야 할 사항은 따로 있다. 바로 영역과 영역 사이의 거리이다.

 

 

 

 

최근접 쌍의 거리를 구하는 문제는 좌표들로 이루어진 2차원 평면이라는 것을 다시 한번 생각해보자. 2차원 평면에서 왼쪽 부분과 오른쪽 부분의 점의 갯수가 동일해지도록 반으로 나누었을 때, 중간 영역은 생길 수 밖에 없다. 이는 두 영역에 동시에 속하는 점은 없다고 여겼기 때문이다.

 

 

 

 

그렇게 되면 왼쪽 영역과 오른쪽 영역 사이의 거리만 비교하면 끝나는 것이 아니다. 우리는 중간 영역도 확인해 주어야 한다. 그나마 다행인 점은 왼쪽 영역과 오른쪽 영역에서 구한 가장 짧은 쌍의 길이보다는 클 수 없으므로, 어느정도 범위를 지정해 주면된다. 아래 그림을 한번 보자.

 

 

 

 

 

 

 

 

우리가 중간 영역에서 확인해 줄 정점은 모든 점이 아니다. 위 그림과 같이 왼쪽 영역의 가장 오른쪽 점에서 d만큼 뺀 거리, 그리고 오른쪽 영역에서 가장 왼쪽 점에서 d만큼 더한 거리안에 속하는 점들을 확인하면 그만이다.

 

 

 

 

조금 가볍게 생각해보자. 왼쪽 영역 최소, 오른쪽 영역 최소, 중간 영역 최소 중 가장 작은 값을 구하면된다. 이 때 중간 영역의 최소를 구할 때 조금 더 간단하게 구하고자 약간의 트릭을 사용한 것처럼 느껴지기도 한다.

 

 

 

 

그러면 중간 영역에서는 어떻게 최소 값을 구할 것인가? 이 부분에 대해서 우리는 "정렬"을 사용할 것이다. y축으로 정렬된 모든 점들에 대한 배열을 가지고 있다고 해보자. 그 영역에서 중간 영역에 해당되는 점만 따로 보관했다고 했을 때, 비교 횟수는 눈에 띄게 적어진다.

 

 

 

 

예를 들어, 중간 영역에 속하는 왼쪽 영역과 오른쪽 영역에 속한 점들을 비교할 때, 왼쪽 영역에 속하는 1번 점과의 거리를 비교하기 위해서, 1-2, 1-3, 1-4... 와 같은 식으로 전부 비교해 주어야 최소 거리를 찾을 수 있었다.

 

 

 

하지만, "정렬" 이라는 도구를 사용한다면 어떨까? 비교해야 할 점들이 y축으로 정렬되어 있기에 1-2, 2-3, 3-4 와 같이 각자 최소의 거리를 유지한다. 즉, 정렬만 한다면 O(1)의 시간으로 비교적 쉽게 최소 거리를 구할 수 있다.

 

 

 

 

 

 

Closest Pair(최근접 점의 쌍)의 수도 코드(Pseudo code)

 

 

 

ClosestPair(S)

입력 : x-좌표의 오름차순으로 정렬된 배열 S에 있는 i 개의 점. 단, 각 점은 (x, y)로 표현한다.
출력 : S에 있는 점들 중 최근접 점의 쌍의 거리

 if (i <= 3) return (2 또는 3개의 점들 사이의 최근접 쌍)

정렬된 S를 같은 크기의 Sl과 Sr로 분할한다. |S|가 홀수이면, |Sl| = |Sr| + 1이 되도록 분할한다.

Cpl = ClosestPair(Sl)
Cpr = ClosestPair(Sr)

d = min{dist(Cpl), dist(Cpr)} 일 때, 중간 영역에 속하는 점들 중에서 최근접 점의 쌍을 찾아서 이를 Cpc라고 하자. 단, dist()는 두 점 사이의 거리를 말한다.

return (Cpl, Cpr, Cpc 중에서 거리가 가장 짧은 쌍)

 

 

 

 

다음은 해당 수도코드를 구현한 Java 코드 예시이다.

 

 

import java.lang.reflect.Array;
import java.util.ArrayList;
import java.util.List;
import java.util.Random;

public class CloseSet {
    static List<List<Integer>> pointsCopy;
    // 분할 정복 수행하는 함수
    static List<List<Integer>> closestPair(List<List<Integer>> points, int low, int high) {
        int size = high - low + 1;
        List<List<Integer>> result = new ArrayList<>();

        // 사이즈가 2일 때는 그냥 result에 추가
        if (size == 2) {
            result.add(points.get(low));
            result.add(points.get(high));
            return result;
        }

        // 사이즈가 3일 때는 3개의 거리 중 가장 짧은 거리를 result에 추가
        if (size == 3) {
            double dist1 = dist(points.get(low), points.get(low + 1));
            double dist2 = dist(points.get(low), points.get(high));
            double dist3 = dist(points.get(low + 1), points.get(high));

            if (dist1 <= dist2 && dist1 <= dist3) {
                result.add(points.get(low));
                result.add(points.get(low + 1));
            } else if (dist2 <= dist1 && dist2 <= dist3) {
                result.add(points.get(low));
                result.add(points.get(high));
            } else {
                result.add(points.get(low + 1));
                result.add(points.get(high));
            }
            return result;
        }

        int mid = size / 2 + low - 1;

        List<List<Integer>> leftPair = closestPair(points, low, mid);
        List<List<Integer>> rightPair = closestPair(points, mid + 1, high);

		// 왼쪽 영역과 오른쪽 영역의 최소 거리 중 더 작은 것을 d로 선언
        double d = Math.min(dist(leftPair.get(0), leftPair.get(1)), dist(rightPair.get(0), rightPair.get(1)));

        // 아래 점들에서 +/-d 를 한 영역
        List<List<Integer>> strip = new ArrayList<>();
        // 왼쪽 영역의 가장 오른쪽 점
        int leftX = points.get(mid).get(0);
        // 오른쪽 영역의 가장 왼쪽 점
        int rightX = points.get(mid + 1).get(0);

        for (List<Integer> point : pointsCopy) {
            int x = point.get(0);
            if (x >= leftX - d && x <= rightX + d) {
                strip.add(point);
            }
        }

        double centerDist = Double.POSITIVE_INFINITY;
        List<Integer> centerPoint1 = null;
        List<Integer> centerPoint2 = null;

		// 두 점씩만 비교하면됨(이미 y축으로 정렬되있기 때문)
        for (int i = 0; i < strip.size() - 1; i++) {
            List<Integer> p1 = strip.get(i);
            List<Integer> p2 = strip.get(i + 1);
            double currentDist = dist(p1, p2);

            if (currentDist < centerDist) {
                centerDist = currentDist;
                centerPoint1 = p1;
                centerPoint2 = p2;
            }
        }

        // 중앙에서 구한 거리가 현재까지의 거리보다 짧다면 갱신
        if (centerPoint1 != null && centerPoint2 != null && centerDist < d) {
            result.add(centerPoint1);
            result.add(centerPoint2);
            return result;
        }

        return d == dist(leftPair.get(0), leftPair.get(1)) ? leftPair : rightPair;
    }

        // 두 점 간의 거리를 계산하는 함수
        static double dist(List<Integer> p, List<Integer> q) {
        int deltaX = p.get(0) - q.get(0);
        int deltaY = p.get(1) - q.get(1);
        return Math.sqrt(deltaX * deltaX + deltaY * deltaY);
    }

    public static void main(String[] args) {
        int N = 20;
        List<List<Integer>> points = new ArrayList<>();
        Random random = new Random(System.currentTimeMillis());

        for (int i = 0; i < N; i++) {
            int x = random.nextInt(201); // 0부터 200까지의 랜덤 x 좌표
            int y = random.nextInt(101); // 0부터 100까지의 랜덤 y 좌표
            List<Integer> point = new ArrayList<>();
            point.add(x);
            point.add(y);
            points.add(point);
        }

        // x 좌표를 기준으로 점들을 정렬
        points.sort((p1, p2) -> Integer.compare(p1.get(0), p2.get(0)));
        for (int i = 0; i < N; i++) {
            points.get(i).add(i);
        }
        System.out.print("[");
        for(int i=0; i<N; i++) {
            if (i != N-1) {
                System.out.print("[" + points.get(i).get(0) + ", " + points.get(i).get(1) + ", " +points.get(i).get(2) + "], ");
            } else {
                System.out.print("[" + points.get(i).get(0) + ", " + points.get(i).get(1) + ", " +points.get(i).get(2) + "]");
            }
        }
        System.out.print("]");

        pointsCopy = new ArrayList<>(points);
        pointsCopy.sort((p1, p2) -> Integer.compare(p1.get(1), p2.get(1)));


        List<List<Integer>> result = closestPair(points, 0, points.size() - 1);

        System.out.println();
        System.out.println("================================================");

        System.out.print("[");
        for(int i=0; i<N; i++) {
            if (i != N-1) {
                System.out.print("[" + pointsCopy.get(i).get(0) + ", " + pointsCopy.get(i).get(1) + ", " +pointsCopy.get(i).get(2) + "], ");
            } else {
                System.out.print("[" + pointsCopy.get(i).get(0) + ", " + pointsCopy.get(i).get(1) + ", " +pointsCopy.get(i).get(2) + "]");
            }
        }
        System.out.print("]");

        System.out.println();
        System.out.println("================================================");
        System.out.println("분할 정복 해 = \t" + result.get(0) + " \t" + result.get(1) + " \t" + String.format("%.2f", dist(result.get(0), result.get(1))));


        double closestDist = Double.MAX_VALUE;

        List<Integer> closestPoint1 = null;
        List<Integer> closestPoint2 = null;

        for (int i = 0; i < N; i++) {
            for (int j = i + 1; j < N; j++) {
                double currentDist = dist(points.get(i), points.get(j));
                if (currentDist < closestDist) {
                    closestDist = currentDist;
                    closestPoint1 = points.get(i);
                    closestPoint2 = points.get(j);
                }
            }
        }

        System.out.println("N^2 해 = \t" + closestPoint1 + " \t" + closestPoint2 + " \t" + String.format("%.2f", closestDist));
        System.out.println(closestDist == dist(result.get(0), result.get(1)));
    }
}