Divide and conquer

Divide And conquer Algorithm

• DAC 소개
• DAC를 사용한 알고리즘들
• DAC의 주의점

 

---

Divde And Conquer 소개

Divide and conquer

 

Divide and conquer Algorithm은 알고리즘 전략 중 하나로써 일반적으로 다음 세단계를 거쳐 문제를 해결한다.

 

1. Divide

문제를 하위 문제(sub-problem)으로 나누는 과정

 

2. Conquer

하위 문제가 해결될 때 까지 재귀적인 호출을 해서 하위 문제를 풀어낸다.

 

3. Combine

풀어낸 하위 문제를 통해 문제의 해결책을 찾아낸다.

 

// P is Problem
DAC(P)
{
    if(small(P)
        return(Solution(P));
    else {
        divide P in P1, P2, P3 ... Pk;    // f1(n)
        Apply DAC(P1), DAC(P2)...;
        Combine(DAC(P1), DAC(P2), ...);
    }
}

 

 

 

DAC(a, i, j)
{
    if(small(a, i, j))
        return(Solution(a, i, j));
    else {
        m = divide(a, i, j);    // f1(n)
        b = DAC(a, i, mid);     // T(n/2)
        c = DAC(a, mid+1, j);   // T(n/2)
        d = combind(b, c);      // f2(n)
        return d;
    }
}

 

 

 

DAC를 사용한 알고리즘들

 

1. Binary Search

Searching 알고리즘 중 하나로 입력값과 배열의 중간의 값을 비교해 일치한다면 값을 반환하고 값이 더 작다면 중간 값의 왼쪽에서 이 과정을 반복하고 값이 더 크다면 중간 값의 오른쪽에서 이 과정을 반복한다

 

2. QuickSort

pivot element를 선택하고 선택한 피벗 요소보다 작은 모든 요소가 피벗의 왼쪽으로 이동하고 더 큰 요소는 오른쪽으로 이동하는 방식으로 재정렬 시킨 뒤에 왼쪽과 오른쪽에 있는 하위 배열들을 재귀적으로 정렬한다

 

3. Merge Sort

Sotring 알고리즘 중 하나로 배열의 중간을 기준으로 두 개로 나누고 재귀적으로 정렬한 다음 마지막으로 정렬 된 sub-array들을 병합하여 정렬을 수행하는 알고리즘

 

4. Closest Pair of Points

x-y평면의 점 집합에서 가장 가까운 점의 쌍을 찾는 문제이다. 모든 점 쌍의 거리를 구하는 Brute Force 방식을 통하면 O(n^2)의 시간이 걸리는 반면 DAC 방법을 사용하면 O(nLogn)의 시간에 문제를 해결 할 수 있다.

 

5. Straseen's Alogrithm

두 행렬을 곱하는 알고리즘으로 Brute Force를 이용하면 O(n^3)의 시간이 걸리는데 Straseen's Algorithm를 이용하면 O(n^2.8974)시간에 두개의 행렬을 곱해줄 수 있다

 

6. Cooley-Tukey Fast Fourier Transform(FFT) algorithm

FFT의 가장 일반적인 알고리즘으로 O(nlogn) 시간에 작동하는 DAC 알고리즘이다.

 

 

 

 

Divide and conquer의 주의점

  메인 Problem이 Divide되어진 sub-problem은 메인 Problem과 같아야 한다.

 

  예를들어 워크숍을 조직한다고 했을 때 이를 워크숍을 위한 포스터를 붙이고 게스트를 초청하고 사람을 모집하는 업무로 나눈다고 하자.

 

  이 때 나누어진 sub-problem들(포스터 붙이고, 게스트 초청하고 등등)이 메인 problem(워크숍을 조직한다)와 다르기 때문에 이는 divide and conquer라고 할 수 없다 

 

  만약 main problem이 sorting이라면 sub-problem도 sorting이여야 이를 재귀적으로 풀어낼 수 있기 때문에        Divide and conquer를 적용하려면 반드시 메인 Problem과 sub-problem은 같아야 한다

 

또한 divide를 하고 난 뒤에 이를 combine할 메소드를 만들어야 한다.

 

Example

주어진 배열에서 최소값과 최대값을 구하시오.

public class GFG {
    // Function to find the maximum no. in a given array
    static int DAC_MAX(int a[], int index, int l) {
        int max;
        if(index >= l - 2) {
            if(a[index] > a[index+1])
                return a[index];
            else
                return a[index+1];
        }
 
        // Logic to find the Maximum Element in the given array
        max = DAC_MAX(a, index+1, l);
 
        if(a[index] > max)
            return a[index];
        else
            return max;
    }
 
    // Function to find the minimum no. in the given array
    static int DAC_Min(int a[], int index, int l) {
        int min;
        if(index >= l - 2) {
            if(a[index] < a[index + 1])
                return a[index];
            else
                return a[index+1];
        }
        // Logic to find the Maximum Element in the given array
        min = DAC_Min(a, index+1, l);
 
        if(a[index] < min)
            return a[index];
        else
            return min;
    }
 
    // Driver Code
    public static void main(String[] args) {
        // Defining the variables
        int min, max;
 
        // Initializing the array
        int a[] = {70, 250, 50, 80, 140, 12, 14};
 
        // Recursion - DAC_Max function called
        max = DAC_MAX(a, 0, 7);
        min = DAC_Min(a, 0, 7);
 
        System.out.printf("The Minimum number in " + "a given array is : %d \n", min);
        System.out.printf("The Maximum number in " + "a given array is : %d \n", max);
    }
 
}
 

Output:

 

 

MergeSort

// Java Program for MergeSort
public class MergeSort {
 
    // Merges two subarrays of arr[].
    // First subarray is arr[l..m]
    // Second subarray is arr[m+1..r]
    void merge(int arr[], int l, int m, int r)
    {
        // Find sizes of two subarrays to be merged
        int n1 = m - l + 1;
        int n2 = r - m;
 
        /* Create temp arrays */
        int L[] = new int[n1];
        int R[] = new int[n2];
 
        /*Copy data to temp arrays*/
        for (int i = 0; i < n1; ++i)
            L[i] = arr[l + i];
        for (int j = 0; j < n2; ++j)
            R[j] = arr[m + 1 + j];
 
        /* Merge the temp arrays */
 
        // Initial indexes of first and second subarrays
        int i = 0, j = 0;
 
        // Initial index of merged subarry array
        int k = l;
        while (i < n1 && j < n2) {
            if (L[i] <= R[j]) {
                arr[k] = L[i];
                i++;
            }
            else {
                arr[k] = R[j];
                j++;
            }
            k++;
        }
 
        /* Copy remaining elements of L[] if any */
        while (i < n1) {
            arr[k] = L[i];
            i++;
            k++;
        }
 
        /* Copy remaining elements of R[] if any */
        while (j < n2) {
            arr[k] = R[j];
            j++;
            k++;
        }
    }
 
 
    // Main function that sorts arr[l...r] using merge()
    void sort(int arr[], int l, int r) {
        if(l < r) {
            // Find the middle point
            int m = l + (r-l)/2;
 
            // Sort first and second halves
            sort(arr, l, m);
            sort(arr, m+1, r);
 
            // Merge the sorted halves
            merge(arr, l, m, r);
        }
    }
 
    static void printArray(int arr[]) {
        int n = arr.length;
        for(int i = 0; i < n; i++) {
            System.out.print(arr[i] + " ");
        }
        System.out.println();
    }
 
    public static void main(String args[]) {
        int arr[] = {12, 11, 13, 5, 6, 7};
 
        System.out.println("Given Array");
        printArray(arr);
 
        MergeSort ob = new MergeSort();
        ob.sort(arr, 0, arr.length-1);
 
        System.out.println("\nSorted array");
        printArray(arr);
    }
}
 

Output:

 

 

 

Reference

www.geeksforgeeks.org/divide-and-conquer-algorithm-introduction/

Divide and Conquer Algorithm | Introduction - GeeksforGeeks

www.youtube.com/watch?v=2Rr2tW9zvRg