분할정복(Divide and Conquer) 알고리즘에 대하여.java

*본 포스팅은 분할정복 알고리즘에 관한 학습을 위해 작성되었습니다.

---

 

#분할정복 알고리즘 ✍

 

하나의 큰 문제를 작은 문제들로 나누어 문제를 해결하는 방법

 

 

---

 

#설계과정

 

분할 (Divide) : 해결할 문제를 여러 개의 작은 부분으로 나눈다.

 

정복 (Conquer) : 나눈 작은 문제를 각각 해결한다.

 

통합 (Combine) : (주어진 문제 요구 시) 해결된 해답을 통합한다.

 

 

 

---

#분할정복의 종류

• 이진검색
• 병합정렬
• 퀵정렬 ( 호어파티션, 로무토파티션)

 

---

#이진검색 (Binary Search)

 

:자료의 중앙값과 찾으려는 값의 비교를 통해 다음 검색의 위치를 결정하여 키 값을 찾는 검색 방법

👉  검색 범위를 반으로 줄여가며, 검색 수행 ( 자료 정렬 선행 필수 )

 

 

#시간복잡도 ⏰

 

입력데이터가 N이라 할 때, 한 번 시행 할때마다, 자료의 갯수는 N/2로 줄어듭니다.

이를 통해 시행 횟수가 증가할 때마다, 자료의 개수 나누기 2를 한 값이 시행 횟수임을 알 수 있습니다.

따라서 시행 횟수를 k라 할때, 찾으려는 하나의 자료(키)가 나타나고 이를 식으로 쓰면 

 

(1/2)^k * N = 1 이며 밑 2에 대한 로그로 변형시키면 k = log N

 

 

따라서 이진검색의 시간복잡도 Big-O(log N)  ( log N : 밑이 2이고 진수가 N인 로그 값)

 

 

 

#이진검색의 코드 구현💻

public class 분할정복_이진검색 {
    public static void main(String[] args) {
        int[] num_arr = {4, 5, 9, 12, 17, 26, 28, 29};
        //정렬된 상태 전제!
        System.out.println(binarysearch(num_arr, 29));
        //있어 없어 대답해
    }

    static boolean binarysearch(int[] num_arr, int key) {
        int left = 0;
        int right = num_arr.length - 1;

        while (left <= right){
            int mid_idx = (left + right) / 2; //홀짝 상관X 
            if(num_arr[mid_idx] == key) return true; 

            else if(num_arr[mid_idx] > key) //오른쪽 idx 옮기기
                right = mid_idx - 1;

            else if(num_arr[mid_idx] < key) //왼쪽 idx 옮기기
                left = mid_idx + 1;
        }
        return false;
    }
}

import java.util.Arrays;

public class 분할정복_이진검색_재귀활용 {
    static int[] num_arr;
    static int key;

    public static void main(String[] args) {
        num_arr = new int[] {4, 6, 10, 15, 19, 26, 27};
        key = 27;
        System.out.println(binarysearch(0, num_arr.length -1));
    }

    static boolean binarysearch(int left, int right){
        if( left > right) return false; //왼쪽과 오른쪽이 교차되면 곤란하지

        int mid = (left + right) / 2;

        if(num_arr[mid] == key) return true; //같으면 찾은거야!

        else if(num_arr[mid] > key) return binarysearch(left, mid-1); //key가 작네, 범위 줄이자

        else return binarysearch(mid+1, right); //key가 크네?, 범위 줄이자
    }
}

import java.util.Arrays;

public class 분할정복_이진검색_API {
    static int[] num_arr;
    static int key;

    public static void main(String[] args) {
        num_arr = new int[] {4, 6, 10, 15, 19, 26, 27};
        key = 26;
        System.out.println(Arrays.binarySearch(num_arr, key)); //idx 출력!
    }
}

 

---

#병합정렬

: 여러 개의 정렬된 자료의 집합을 병합하여 한 개의 정렬된 집합으로 만드는 정렬방식

👉 자료를 최소 단위의 문제까지 나눈 뒤 차례대로 정렬

 

 

 

#시간복잡도 ⏰

 

O(NlogN) = 분할과정에서의 시간 복잡도(log N)  *병합과정에서의 시간 복잡도(N)

 

 

#병합정렬의 코드 구현 💻

import java.util.Arrays;

public class 분할정복_병합정렬 {
    static int[] num_arr = {4, 26, 12, 9, 17, 7, 28, 29};
    static int[] sortedArr = new int[num_arr.length]; //정렬할 배열 선언

    public static void main(String[] args) {
        mergeSort(0, num_arr.length -1 );
        System.out.println(Arrays.toString(num_arr));
    }

    static void mergeSort(int left, int right){
        if(left >= right) return;

        else {
            int mid = (left + right) / 2;
            mergeSort(left,mid); //왼쪽 영역 분할
            mergeSort(mid+1,right); // 오른쪽 영역 분할
            merge(left,mid,right); //병합
        }
    }
    static void merge(int left, int mid, int right) {
        int L = left; //왼쪽구간의 시작 포인트
        int R = mid+1; //오른쪽구간의 시작 포인트
        int idx = left; //정렬된 원소 저장할 위치

        //서로 아직 비교할 수 있는 값들이 남아있을때
        while(L <= mid && R <= right) {
            if(num_arr[L] <= num_arr[R]) sortedArr[idx++] = num_arr[L++];
            else sortedArr[idx++] = num_arr[R++];
        }
        //왼쪽구간 남았어
        if(L<= mid) {
            for(int i = L; i<=mid; i++)
                sortedArr[idx++] = num_arr[i];
        }
        //오른쪽구간 남았어
        else {
            for(int i = R; i<=right; i++) {
                sortedArr[idx++] = num_arr[i];
            }
        }

        //원본에 반영하기
        for(int i = left; i<=right; i++)
            num_arr[i] = sortedArr[i];
    }
}

 

 

읽어주셔서 감사합니다.