[알고리즘] 2. Divide and conquer 내용 정리

이전 내용

 

[알고리즘] 1. Brute Force 내용 정리

 

 

1. Brute force
2. Divide and conquer
3. Decrease and conquer
4. Transform and conquer
5. Greedy Method
6. Dynamic Programming
7. Backtracking
8. Branch and Bound

여기서는 8가지 알고리즘 중 Divide and conquer에 대해 다룬다.

---

Divide and conquer란

분할 정복이라 불리는 알고리즘이다. 주어진 문제의 입력을 분할하여 최소 단위로 나눈다. 그리고 이렇게 최소단위로 나눈 부분문제에 대한 부분해를 구하고, 이를 취합한다. 총 3가지 분할 -> 정복 -> 통합 3가지의 과정을 거치는 것이다. 이렇게 큰 문제를 작은 문제로 쪼개어 접근하는 방식을 하향식 top-down 접근 방법이라고 한다. Divde and Conquer는 한 번에 몇 덩어리로 쪼개는지에 따라 달라지지만, 일반적으로 절반씩 쪼개어 접근한다.

---

Divide and conquer 예시

• merge sort
• quick sort
• binary tree traversal
• multiplicatoin of large integers (카라추바 알고리즘)
• matrix multiplication(행렬 곱셈)
• closet-pair algorithm
• convex-hull algorithm

---

 

merge sort 

#include<iostream>
#include <ctime>
#include <cstdlib>
using namespace std;

void merge(int arr[], int left, int mid, int right) { //합치는 함수
    int n1 = mid - left + 1; //왼쪽 값 배열들의 크기
    int n2 = right - mid; //오른쪽 값 배열들의 크기

    int* leftArr = new int[n1]; 
    int* rightArr = new int[n2];

    for (int i = 0; i < n1; i++)
        leftArr[i] = arr[left + i];
    for (int j = 0; j < n2; j++)
        rightArr[j] = arr[mid + 1 + j]; //배열 복제하기

    int i = 0, j = 0, k = left;
    while (i < n1 && j < n2) { //둘의 배열중 어느 한쪽이 끝나기 전까지
        if (leftArr[i] <= rightArr[j]) { //하나씩 arr에 집어넣기
            arr[k] = leftArr[i];
            i++;
        } else {
            arr[k] = rightArr[j];
            j++;
        }
        k++;
    }
    //두 배열에서 남은 값들 마저 집어 넣기

    while (i < n1) {
        arr[k] = leftArr[i];
        i++;
        k++;
    }

    while (j < n2) {
        arr[k] = rightArr[j];
        j++;
        k++;
    }

    delete[] leftArr; //할당된 메모리들을 지워준다.
    delete[] rightArr;
}

void mergeSort(int arr[], int left, int right) { //분할하기 위해서 전체 배열과 시작점, 끝점을 입력받는다.
    //분할하기
    if (left < right) {
        int mid = left + (right - left) / 2;
        // 최소단위로 나눠질때까지 가운데 점을 잡는다.

        mergeSort(arr, left, mid); // 다시 나눈 둘을 재귀적으로 또 나눈다.
        mergeSort(arr, mid + 1, right);

        merge(arr, left, mid, right); // 재귀함수로 모든 mergeSort가 끝나고 나면 합치는 게 시작된다.
    }
}




int main(){
    int randombox[101];
    for (int i = 0; i < 100; ++i)
		randombox[i] = rand() % 100;
	clock_t start_time = clock();
    
    //mergesort 시작
    mergeSort(randombox, 0, 99);
	
	// 결과 보여주기
	cout << "Sorted array: ";
    for (int i = 0; i < 100; ++i)
        cout << randombox[i] << " ";
    cout << endl;

    clock_t end_time = clock();
    double time_taken = static_cast<double>(end_time - start_time) / CLOCKS_PER_SEC;
    cout << "Time taken: " << time_taken << " seconds" << endl;
    return 0;
}

 

• 주어진 배열을 계속해서 절반씩 쪼갠다. (분할)
• 최소 단위(2개 이하)로 쪼갰으면 그때부터 앞부분끼리 합치기 시작한다. 
• 이 과정에서 재귀함수가 쓰인다. 재귀적으로 선언하면 함수 안의 처음재귀문이 다 끝나야지 그 아래의 다른 코드 혹은 다른 재귀문이 실행된다.
• 이 과정에서 divide 하는 일괄적인 작업을 더 짧은 코드로 쓸 수 있다.   

---

 

quick sort

#include<iostream>
#include <ctime>
#include <cstdlib>
using namespace std;

void quickSort(int arr[], int start, int finish) {
    if (start >= finish) return; //재귀함수에서 꼭 필요한 종료조건
    int left = start;
    int right = finish;
    int pivot = arr[(left + right) / 2]; //꼭 pivot이 가운데일 필요는 없다.

    while (left <= right) {
        while (arr[left] < pivot) left++;
        while (arr[right] > pivot) right--;

        if (left <= right) { //좌우 포인터의 위치가 역전되지 않았다면. 마지막 swap에서 문제 생기는 것 방지하는 if문 
            swap(arr[left], arr[right]);
            left++; // 같은 swap 계속해서 반복실행하는 걸 막기 위한 전진과 후퇴
            right--;
        }
    }

    quickSort(arr, start, right);  // 오른쪽 포인터가 위치한 부분까지 정렬
    quickSort(arr, left, finish);   // 왼쪽 포인터가 위치한 부분부터 끝까지 정렬
}

int main() {
    int randombox[1000];
    srand(static_cast<unsigned int>(time(0)));
    for (int i = 0; i < 1000; ++i)
        randombox[i] = rand() % 1000;

    clock_t start_time = clock();
    quickSort(randombox, 0, 999);

    // 결과 보여주기
    cout << "Sorted array: ";
    for (int i = 0; i < 1000; ++i)
        cout << randombox[i] << " ";
    cout << endl;

    clock_t end_time = clock();
    double time_taken = static_cast<double>(end_time - start_time) / CLOCKS_PER_SEC;
    cout << "Time taken: " << time_taken << " seconds" << endl;
    return 0;
}

• pivot이라는 기준원소를 하나 잡고 그보다 큰 수는 왼쪽으로, 그보다 작은 수는 오른쪽으로 보낸다. 피봇을 기준으로 좌우 포인터가 확인하는 것이다. 이 과정을 재귀적으로 반복한다.
• 즉 똑같은 분할-정복 알고리즘이지만 mergesort와는 다르게 큰 덩어리를 먼저 나누면서 세세한 부분들을 맞추어 간다. merge sort와 이런부분에서는 반대 같다.
• 그리고 pivot은 어디에 위치하든 왼쪽과 오른쪽 사이에만 있다면 중요하지 않은 게 포인트다. 어차피 피봇을 고르는 타이밍에는 오른쪽이 왼쪽보다 큰 경향을 띄지 않기 때문이다. 

---

Binary Tree Traversal

#include <iostream>
using namespace std;

struct TreeNode {
    int value;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : value(x), left(nullptr), right(nullptr) {} //자동 초기화 코드
};

// 트리 생성 (주어진 이미지의 구조에 맞게 노드들을 설정)
TreeNode* createTree() {
    TreeNode* root = new TreeNode(60);
    root->left = new TreeNode(41);
    root->right = new TreeNode(74);
    root->left->left = new TreeNode(16);
    root->left->right = new TreeNode(53);
    root->left->left->right = new TreeNode(25);
    root->left->right->left = new TreeNode(46);
    root->left->right->right = new TreeNode(55);
    root->left->right->left->left = new TreeNode(42);
    root->right->left = new TreeNode(65);
    root->right->left->left = new TreeNode(63);
    root->right->left->right = new TreeNode(70);
    root->right->left->left->left = new TreeNode(62);
    root->right->left->left->right = new TreeNode(64);
    return root;
}

// 전위 순회 (Pre-order)
void preOrder(TreeNode* node) {
    if (node == nullptr) return;
    cout << node->value << " ";   // 루트 노드 방문
    preOrder(node->left);         // 왼쪽 서브트리 방문
    preOrder(node->right);        // 오른쪽 서브트리 방문
}

// 중위 순회 (In-order)
void inOrder(TreeNode* node) {
    if (node == nullptr) return;
    inOrder(node->left);          // 왼쪽 서브트리 방문
    cout << node->value << " ";   // 루트 노드 방문
    inOrder(node->right);         // 오른쪽 서브트리 방문
}

// 후위 순회 (Post-order)
void postOrder(TreeNode* node) {
    if (node == nullptr) return;
    postOrder(node->left);        // 왼쪽 서브트리 방문
    postOrder(node->right);       // 오른쪽 서브트리 방문
    cout << node->value << " ";   // 루트 노드 방문
}

int main() {
    TreeNode* root = createTree();

    cout << "Pre-order traversal: ";
    preOrder(root);
    cout << endl;

    cout << "In-order traversal: ";
    inOrder(root);
    cout << endl;

    cout << "Post-order traversal: ";
    postOrder(root);
    cout << endl;

    return 0;
}

 

• 이진트리 순회다. 여기서는 주어진 트리를 각각 전위순회(Root->Left->Right), 중위순회(Left->Right->Root), 후위순회(Left->Right->Root)로  3가지 방식으로 탐색하는 알고리즘을 짰다. 
• 각각의 순회방식을 결정하는 것은 ROOT 값을 몇 번째로 처리하느냐 이다. left 다음에 right가 오는 건 정해진 수순이다.
• 위에서 말한 대로 재귀함수 안의 다른 재귀함수와 코드 순서만 바꾸어도 쉽게 전혀 다른 방식으로 알고리즘을 변경할 수 있다.
• 위 코드에서는 생성자를 두어 별도의 생성 후 초기화 과정 없이 간편하게 예시 트리를 생성했다. 
• 하지만 이러한 트리순회 방식은 과정을 왼쪽 서브트리와 오른쪽 서브트리로 재귀적으로 분할하여 처리하지만, 별도의 통합과정을 걸치지는 않는다.

 

---

karatsuba alogrithm

#include <iostream>
#include <cmath>
using namespace std;

// 카라추바 알고리즘을 적용한 곱셈 함수
long long karatsuba(int x, int y) {
    // 기본적인 종료 조건 (1자리 수의 곱셈)
    if (x < 10 || y < 10) {
        return x * y;
    }

    // x와 y를 절반으로 나눔
    int n = max(log10(x), log10(y)) + 1;
    int half = n / 2;

    // 분할
    int a = x / pow(10, half);
    int b = x % (int)pow(10, half);
    int c = y / pow(10, half);
    int d = y % (int)pow(10, half);

    // 세 개의 곱셈
    long long ac = karatsuba(a, c);
    long long bd = karatsuba(b, d);
    long long ab_cd = karatsuba(a + b, c + d);

    // 최종적으로 결과를 합산
    return ac * pow(10, 2 * half) + (ab_cd - ac - bd) * pow(10, half) + bd;
}

int main() {
    int x = 2462;
    int y = 8014;

    long long result = karatsuba(x, y);

    cout << "Result of " << x << " * " << y << " = " << result << endl;

    return 0;
}

• 카라추바 알고리즘이다. 컴퓨터는 덧셈 연산은 빠르게 하지만 곱셈연산은 그렇지 못하다. 하지만 시프트 연산은 빠르게 한다. 그래서 큰 수의 곱셈을 빠르게 하기 위해 나온 알고리즘이다.
• 일반적으로 두 수를 곱할 때 우리는 각 자릿수별로 곱한 후에 더하는 과정을 반복하므로, 곱셈 연산만 자릿수의 곱만큼 반복해야 한다.(두 자릿수와 세 자릿수의 곱이면 곱셈 연산만 6번)
• 하지만 카라추바 알고리즘은 자릿수를 절반으로 줄여 덧셈과 시프트연산을 이용한다.
• 추가적인 덧셈과 시프트 연산 과정이 들어가기에 대략 97 자릿수 이상부터 일반 곱셈보다 더 빨라진다.
• 1234 * 5678이라는 예시를 들어 설명하면 다음과 같은 과정을 거친다.
  • 1. 1234를 12와 34, 5678을 56과 78이라는 두 부분으로 나눈다.
  • 2. (12 + 34) * (56 +78) - 12 * 56 - 34 * 78 =2840
  •  3. 12 * 56 * 10^4 + 2840 * 10^2  + 34 *78 = 70002652
• 위처럼 계산한다. 위의 과정에서 12를 a, 34를 b, 56을 c, 78을 d라고 하면 (100a+b)(100c+d)가 된다.
• 그러면 결국 최종 식은 10000ac +100(ad+bc) +bd가 된다.
• 그래서 ac, ad+bc, bd만 알고 있다면 빠르게 답을 구할 수 있는 것이다.
• 그리고 ad+bc도 그대로 계산하는 것이 아니라 (a+b)(c+d)를 구하고 구했던 ac와 bd를 빼주면 곱셈 연산을 2번에서 한 번으로 줄일 수 있다
• 종합적으로 곱셈을 3번만 하는, 다른 연산은 늘리고 곱셈을 최소로 줄인 알고리즘이다.
• 위에서 써진 10000과 100은 들어오는 숫자 자릿수에 따라 10의 n승 형태로 유연하게 바꿀 수 있다. 모두 10 단위로 곱해지므로 곱셈할 필요 없이 자릿수만 맞추어 주면 된다. 
• 한 자릿수 * 한자리수 형태를 띠는 최소곱셈으로 나누어질 때까지 계속해서 재귀적으로 카라추바를 돌리면 된다.
• 위에서 다른 알고리즘들은 재귀문 안의 순서들이 달라지면 아예 다른 알고리즘이 되었다. 하지만 여기서는 나온 세 개의 곱을 더해주기만 하면 되므로, 덧셈의 교환법칙이 성립해 재귀문끼리의 순서가 중요하지 않다. 

---

matrix multiplication

#include <iostream>
#include <vector>
#include <cmath>
using namespace std;

// 행렬 덧셈
vector<vector<int>> addMatrix(const vector<vector<int>>& A, const vector<vector<int>>& B) {
    int n = A.size();
    vector<vector<int>> C(n, vector<int>(n, 0));
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < n; j++) {
            C[i][j] = A[i][j] + B[i][j];
        }
    }
    return C;
}

// 행렬 뺄셈
vector<vector<int>> subtractMatrix(const vector<vector<int>>& A, const vector<vector<int>>& B) {
    int n = A.size();
    vector<vector<int>> C(n, vector<int>(n, 0));
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < n; j++) {
            C[i][j] = A[i][j] - B[i][j];
        }
    }
    return C;
}

// 부분 행렬 추출
vector<vector<int>> getSubMatrix(const vector<vector<int>>& A, int row, int col, int size) {
    vector<vector<int>> sub(size, vector<int>(size));
    for(int i = 0; i < size; i++) {
        for(int j = 0; j < size; j++) {
            sub[i][j] = A[i + row][j + col];
        }
    }
    return sub;
}

// 부분 행렬을 원래 행렬에 복사
void copySubMatrix(vector<vector<int>>& dest, const vector<vector<int>>& src, int row, int col) {
    int size = src.size();
    for(int i = 0; i < size; i++) {
        for(int j = 0; j < size; j++) {
            dest[i + row][j + col] = src[i][j];
        }
    }
}

// Strassen 알고리즘 구현
vector<vector<int>> strassen(const vector<vector<int>>& A, const vector<vector<int>>& B) {
    int n = A.size();
    
    // 기저 사례: 1x1 행렬
    if(n == 1) {
        return {{A[0][0] * B[0][0]}};
    }
    
    // 새로운 크기는 현재 크기의 절반
    int newSize = n/2;
    
    // 부분 행렬들
    vector<vector<int>> a11 = getSubMatrix(A, 0, 0, newSize);
    vector<vector<int>> a12 = getSubMatrix(A, 0, newSize, newSize);
    vector<vector<int>> a21 = getSubMatrix(A, newSize, 0, newSize);
    vector<vector<int>> a22 = getSubMatrix(A, newSize, newSize, newSize);
    
    vector<vector<int>> b11 = getSubMatrix(B, 0, 0, newSize);
    vector<vector<int>> b12 = getSubMatrix(B, 0, newSize, newSize);
    vector<vector<int>> b21 = getSubMatrix(B, newSize, 0, newSize);
    vector<vector<int>> b22 = getSubMatrix(B, newSize, newSize, newSize);
    
    // Strassen의 7개 곱셈
    vector<vector<int>> M1 = strassen(addMatrix(a11, a22), addMatrix(b11, b22));
    vector<vector<int>> M2 = strassen(addMatrix(a21, a22), b11);
    vector<vector<int>> M3 = strassen(a11, subtractMatrix(b12, b22));
    vector<vector<int>> M4 = strassen(a22, subtractMatrix(b21, b11));
    vector<vector<int>> M5 = strassen(addMatrix(a11, a12), b22);
    vector<vector<int>> M6 = strassen(subtractMatrix(a21, a11), addMatrix(b11, b12));
    vector<vector<int>> M7 = strassen(subtractMatrix(a12, a22), addMatrix(b21, b22));
    
    // 결과 행렬의 부분들 계산
    vector<vector<int>> c11 = addMatrix(subtractMatrix(addMatrix(M1, M4), M5), M7);
    vector<vector<int>> c12 = addMatrix(M3, M5);
    vector<vector<int>> c21 = addMatrix(M2, M4);
    vector<vector<int>> c22 = addMatrix(subtractMatrix(addMatrix(M1, M3), M2), M6);
    
    // 결과 행렬 조립
    vector<vector<int>> C(n, vector<int>(n, 0));
    copySubMatrix(C, c11, 0, 0);
    copySubMatrix(C, c12, 0, newSize);
    copySubMatrix(C, c21, newSize, 0);
    copySubMatrix(C, c22, newSize, newSize);
    
    return C;
}

// 다음 2의 거듭제곱 크기 찾기
int nextPowerOfTwo(int n) {
    return pow(2, ceil(log2(n)));
}

// 행렬 크기를 2의 거듭제곱으로 맞추기
vector<vector<int>> padMatrix(const vector<vector<int>>& matrix, int targetSize) {
    vector<vector<int>> padded(targetSize, vector<int>(targetSize, 0));
    int originalSize = matrix.size();
    for(int i = 0; i < originalSize; i++) {
        for(int j = 0; j < matrix[0].size(); j++) {
            padded[i][j] = matrix[i][j];
        }
    }
    return padded;
}

// 결과 출력 함수
void printMatrix(const vector<vector<int>>& matrix, int originalSize) {
    for(int i = 0; i < originalSize; i++) {
        for(int j = 0; j < originalSize; j++) {
            cout << matrix[i][j] << " ";
        }
        cout << endl;
    }
}

int main() {
    // 테스트용 행렬
    vector<vector<int>> A = {
        {10, 8},
        {12, 11}
    };
    vector<vector<int>> B = {
        {4, 9},
        {8, 13}
    };
    int originalSize = A.size();
    int paddedSize = nextPowerOfTwo(originalSize);
    // 행렬 크기를 2의 거듭제곱으로 패딩
    vector<vector<int>> paddedA = padMatrix(A, paddedSize);
    vector<vector<int>> paddedB = padMatrix(B, paddedSize);
    
    // Strassen 알고리즘으로 행렬 곱셈 수행
    vector<vector<int>> result = strassen(paddedA, paddedB);
    
    // 결과 출력
    cout << "결과 행렬:" << endl;
    printMatrix(result, originalSize);
    
    return 0;
}

• 행렬곱셈을 빠르게 계산하는 방법이다. 
• 일반 행렬곱은 앞의 행과 뒤의 열끼리 대응 곱하여 나열한다.
  예시(a의 1행* b의 1열, a의 1행, b의 2열, a의 2행 * b의 1열, a의 2행 *b의 2열)
• 이 방법대로라면 a행렬을 행 불러오는데 for문 1번, b행렬의 열 불러오는데 for문 1번, 그리고 그 안의 성분들끼리 불러오는데 for문 1번이 쓰여 총 for문이 3번이나 쓰인다.
• 하지만 strassen은 이 행렬곱을 빠르게 구하기 위해 분할정복하는 방법을 썼다. 
• starassen의 방법은 행렬을 계속 2*2 4분 할로 쪼개기에 행렬의 크기가 2의 거듭제곱이어야만 한다. 
• M1~M7까지의 값을 미리 구한다. 그리고 분할정복으로 계산한다. 이 2가지 아이디어가 맞물려서 거대한 행렬 곱계산을 빠르게 할 수 있게 해 준다. 

 

---

closet- pair algorithm

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <set>
using namespace std;

struct Point {
    int x, y;
};

// 두 점 간의 유클리드 거리 계산
double distance(const Point& p1, const Point& p2) {
    return sqrt((p1.x - p2.x) * (p1.x - p2.x) + (p1.y - p2.y) * (p1.y - p2.y));
}

// x 좌표 기준으로 점을 정렬하는 비교 함수
bool compareX(const Point& p1, const Point& p2) {
    return p1.x < p2.x;
}

// y 좌표 기준으로 점을 정렬하는 비교 함수
bool compareY(const Point& p1, const Point& p2) {
    return p1.y < p2.y;
}

// Closest Pair를 찾는 분할 정복 알고리즘
double closestPairRec(vector<Point>& pointsX, vector<Point>& pointsY) {
    int n = pointsX.size();
    
    // 기본 경우: 점이 2개 또는 3개 이하일 경우, 직접 계산
    if (n <= 3) {
        double minDist = INFINITY;
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                minDist = min(minDist, distance(pointsX[i], pointsX[j]));
            }
        }
        return minDist;
    }

    // 점들을 두 부분으로 분할
    int mid = n / 2;
    Point midPoint = pointsX[mid];

    vector<Point> leftX, rightX;
    vector<Point> leftY, rightY;
    
    for (int i = 0; i < n; i++) {
        if (pointsX[i].x <= midPoint.x) leftX.push_back(pointsX[i]);
        else rightX.push_back(pointsX[i]);
    }
    
    for (int i = 0; i < n; i++) {
        if (pointsY[i].x <= midPoint.x) leftY.push_back(pointsY[i]);
        else rightY.push_back(pointsY[i]);
    }

    // 왼쪽과 오른쪽 그룹에서 가장 가까운 점을 찾음
    double leftDist = closestPairRec(leftX, leftY);
    double rightDist = closestPairRec(rightX, rightY);
    
    double minDist = min(leftDist, rightDist);

    // 두 부분 사이에서의 가장 가까운 점을 찾음
    vector<Point> strip;
    for (int i = 0; i < n; i++) {
        if (abs(pointsY[i].x - midPoint.x) < minDist) {
            strip.push_back(pointsY[i]);
        }
    }

    for (int i = 0; i < strip.size(); i++) {
        for (int j = i + 1; j < strip.size() && (strip[j].y - strip[i].y) < minDist; j++) {
            minDist = min(minDist, distance(strip[i], strip[j]));
        }
    }

    return minDist;
}

// 가장 가까운 점을 찾는 함수
double closestPair(vector<Point>& points) {
    vector<Point> pointsX = points;
    vector<Point> pointsY = points;
    
    // 점들을 x, y 기준으로 정렬
    sort(pointsX.begin(), pointsX.end(), compareX);
    sort(pointsY.begin(), pointsY.end(), compareY);
    
    return closestPairRec(pointsX, pointsY);
}

// 중복되지 않는 100개의 점을 생성하는 함수
vector<Point> generatePoints() {
    vector<Point> points;
    set<int> x_coords;  // x 좌표가 중복되지 않도록 보장
    srand(time(0));  // 난수 초기화

    // 100개의 점을 생성
    while (points.size() < 100) {
        int x = rand() % 1000;  // x 좌표 (0~999)
        int y = rand() % 1000;  // y 좌표 (0~999)
        
        // x 좌표가 중복되면 다시 생성
        if (x_coords.find(x) == x_coords.end()) {
            points.push_back({x, y});
            x_coords.insert(x);  // x 좌표 추가
        }
    }

    return points;
}

int main() {
    // 중복되지 않는 100개의 점을 생성
    vector<Point> points = generatePoints();

    double result = closestPair(points);
    cout << "The closest pair distance is: " << result << endl;

    return 0;
}

• 2차원 평면상의 n개의 점이 주어질 때 거리가 가장 가까운 한쌍의 점은 무엇인지 찾는 문제이다. 
• x좌표를 기준으로 index를 매겨 정렬한다.
• 만약에 점이 14개라면 일반적으로는 14*13/2 =91가지의 거리를 일일이 확인해야 했다.
• 하지만 점이 속한 면을 7개의 점들끼리, 왼쪽과 오른쪽의 sub문제로 분할한다면?
• 7*6/2*2로 42번만 비교하면 된다.
• 그러면 나올 수 있는 최단거리는 왼쪽 그룹에서의 최단거리와 오른쪽 그룹에서의 최단거리만 비교하면 되는 것 같다.
• 하지만, 왼쪽 그룹의 오른쪽에 있는 점과 오른쪽 그룹의 왼쪽에 있는 점이 최단거리 일 수도 있다. 
• 따라서 그룹을 둘로 나누고 비교하여 나온  최단거리만큼의 x좌표 이내에 각각 점이 하나씩만 있는지 확인해야 한다.
• 서로 나온 최솟값만큼 각각의 방향에서 중앙에서 떨어져 있다면 왼쪽그룹과 오른쪽 그룹을 건너는 점이 최소일리가 없기 때문이다. 
• 만약 그 범위 안에 있다면 그 범위 안에 있는 점들끼리 따로 비교하여 계산을 해준다.
• 이 문제 역시 반복해서  최소단위(점 3개 이하)의 그룹으로 쪼개고 정복하는 방식이다. 그러면 42번보다도 더 적은 비교만을 필요로 한다.  
• 절반씩 쪼개는 방법이므로 O(nlogn)의 시간복잡도를 가진다.
• 이 closet pair 알고리즘은 컴퓨터 그래픽이나 비전, GIS  등 많은 곳에서 쓰인다.

 

---

convex hull

• 2차원 평면에서 점들이 주어졌을 때 점들을 이어 최소개수의 꼭짓점으로 안에 다른 모든 점들을 포함하는 볼록 다각형을 만드는 게 목표인 알고리즘이다.
• 여기서는 Graham scan 알고리즘을 통해 설명한다.
• 가장 아래점을 1번으로 시작해 반시계 방향으로 모든 점을 정렬해 index를 부여한다.
• 그리고 다시 1번부터 탐색하여 1번과 2번을 잇는 선의 왼쪽에 3번이 있는지 오른쪽에 있는지 확인한다.
• 왼쪽에 있다면 성공하여 push인 것이고 오른쪽에 있다면 push 하지 않고 다음점으로 넘어간다.
• 이렇게 통과한 점들끼리 이으면 도형이 완성된다!
• 이렇게 만든 convex hull 끼리도 분할정복으로 합칠 수 있다. 즉 서로 겹치지 않는 convex hull 끼리 합쳐 더 큰 하나의 convex hull로 만들 수 있다는 뜻이다.
• 서로 좌우에 있다 가정할 때 x좌표가 가장 가까운 두 점을 찾고 각각의 꼭짓점 둘 중 하나를 기준으로 계속 돌려가며 각각 위쪽을 연결하는 선과 아래쪽을 연결하는 선을 만들어 갈 수 있다.
• 위의 자세한 과정은 생략하겠다. 

---

 

결론

지금까지 Divide and conquer방식을 알아보았다. 대부분 쪼개고 합치는 과정이 있기에 재귀함수를 사용하여 모두 쪼개고 합치는 식으로 표현하는 문제가 많았다.

 

 

이어지는 내용

[알고리즘] 3. Decrease and Conquer 내용 정리