[알고리즘] Divide and conquer

1. Divide and conquer

• 문제를 하위 문제로 나누고, 하위 문제들을 각각 해결한 후, 각 해결책들을 결합하여 원래 문제를 해결하는 알고리즘 입니다.

 

2. 과정

분할

• 원래의 문제를 비슷하지만 더 간단한 여러 하위 문제로 나눕니다.

 

정복

• 각 하위 문제를 해결합니다.

 

결합

• 하위 문제의 해결책들을 결합하여 원래 문제의 해결책을 찾습니다.

 

3. 예시

Merge Sort

• 주어진 두 리스트를 하나의 정렬된 리스트로 병합하는 알고리즘 입니다.
• 재귀적으로 반복하면서 전체를 정렬하는 방식입니다.

 

동작 방식

• 분할: 리스트를 반으로 나눕니다.  - 크기가 1이 될 때까지
• 정복: 각 부분 리스트를 정렬합니다.
• 병합: 정렬된 부분 리스트들을 하나의 정렬된 리스트로 병합합니다.

 

코드

public class MergeSort {
    public int[] sort(int[] arr, int l, int r) {
        if (l < r) {
            int m = (l+r)/2;
            sort(arr, l, m);
            sort(arr, m+1, r);

            merge(arr, l, m, r);
        }

        return arr;
    }

    private void merge(int[] arr, int l, int m, int r) {
        int[] merged = new int[r-l+1];
        int i = l, j = m+1, k = 0;

        while (i <= m && j <= r) {
            if (arr[i] < arr[j]) {
                merged[k++] = arr[i++];
            } else {
                merged[k++] = arr[j++];
            }
        }

        while (i <= m) {
            merged[k++] = arr[i++];
        }

        while (j <= r) {
            merged[k++] = arr[j++];
        }

        System.arraycopy(merged, 0, arr, l, merged.length);
    }
}

 

Binary Search

• 정렬된 리스트에서 특정 항목을 찾는 알고리즘 입니다.
• 찾고자 하는 항목을 찾거나 검색 범위가 더 이상 줄어들지 않을 때까지 반복합니다.

 

동작 방식

• 분할: 리스트를 반으로 나누어 찾고자 하는 항목이 있는지 결정합니다.
• 정복: 찾고자 하는 항목이 있는 부분 리스트를 선택하여 검색 범위를 좁힙니다.
• 결과: 반복적으로 검색 범위를 좁혀가면서 특정 항목을 찾습니다.

 

코드

private Node search(Node node, int data) {
    if (node == null) {
        return null;
    }

    if (node.data == data) {
        return node;
    }

    if (node.data > data) {
        return search(node.left, data);
    }

    return search(node.right, data);
}

 

 

 

출처

• Wiki - Divide and conquer algorithm
• Wiki - Binary Search algorithm