분할 정복(Divide and Conquer)

☑️ 분할 정복이란?

분할 정복(Divide and Conquer)은 큰 문제를 작은 하위 문제로 분할하고, 각 하위 문제를 해결한 다음, 그 해답을 합쳐서 원래의 큰 문제를 해결하는 방법입니다. 즉, 분할 → 정복 → 결합의 단계로 이루어집니다. 대표적인 예로,  퀵 정렬(Quick Sort)이나 병합 정렬(Merge Sort)과 같은 정렬 알고리즘 문제와 이진 탐색 문제가 있습니다.

 

 ☑️ 재귀 함수를 통한 분할 정복의 구현

분할 정복 알고리즘은 주로 재귀 함수를 통해 구현됩니다. 재귀 함수는 자기 자신을 호출하는 함수로, 하위 문제를 해결하기 위해 반복적으로 자신을 호출합니다. 전체적인 과정은 아래와 같습니다.

 

1. 분할 : 큰 문제를 작은 하위 문제로 나누는 단계에서 재귀 함수를 호출하면서 하위 문제를 생성하여 호출 스택에 추가합니다.

2. 정복 : 재귀 함수를 통해 하위 문제를 해결하고 해답을 반환합니다. 각 하위 문제는 독립적으로 해결됩니다.

3. 결합 : 하위 문제의 해답을 결합하여 원래의 큰 문제에 대한 해답을 얻습니다. 즉, 재귀 호출의 결과를 결합하고 반환값을 상위 호출로 전달됩니다.

 

분할 정복은 더 작고 쉬운 문제로 나누어 해결한다는 점에서 문제 해결 시간을 줄이고 대규모 문제를 해결하기 용이하다는 장점이 있지만, 재귀적으로 구현된다는 점에서 추가적인 메모리가 필요하는 등의 문제가 발생할 수도 있습니다. 따라서 문제에 따라 효율성과 스택 오버 플로우 등을 따지며 적절하게 사용해야 합니다.

 

분할 정복 알고리즘의 간단한 예시로 아래의 코드를 확인합시다.

public class Fibonacci {
	public static int fibonacci(int n) {
    	if (n <= 1) {
        	return n;
        } else {
        	return fibonacci(n - 1) + fibonacci(n - 2);
        }
    }
    
    public static void main(String[] args) {
    	int n = 10;
        int result = fibonacci(n);
        System.out.pringln("Fibonacci result : " + result);
    }
}

 

fibonacci 메서드는 재귀적으로 피보나치 수열의 n번째 항을 계산합니다. n에 대하며 문제를 해결할 때,  n - 1과 n - 2에 대한 재귀 호출을 수행하며, 작은 하위 문제로 나누어 문제를 해결하는 방식입니다.

☑️ 분할 정복의 시간 복잡도

분할 정복의 시간 복잡도는 주로 하위 문제의 개수와 각 하위 문제의 크기에 따라 결정되며, 일반적으로 아래와 같은 형태를 가집니다.

T(n) = aT(n / b) + f(n)

 

여기서 T(n)은 크기가 n인 원래 문제를 해결하는데 필요한 시간입니다. a는 원래 문제를 분할한 하위 문제의 개수이며, n / b는 각 하위 문제의 크기를 의미합니다. f(n)은 분할과 병합 단계에서 필요한 추가적인 작업 시간을 의미합니다. (분할 정복 알고리즘의 시간 복잡도는 마스터 정리(Master Theorem)를 통해 결정됩니다.)

 

일반적으로 분할 정복은 O(nlogn)의 시간 복잡도를 가지지만, 이는 문제의 종류에 따라 달라질 수 있습니다. 병합 정렬의 경우 O(nlogn), 퀵 정렬의 경우 평균적으로 O(nlogn), 이진탐색의 경우 O(logn)의 시간 복잡도를 가집니다.

 

☑️ 분할 정복을 활용한 알고리즘 예시

퀵 정렬 (Quick Sort)

퀵 정렬은 아래와 같은 단계로 수행됩니다.

 

1.1 배열에서 pivot을 선택합니다.

(이때, pivot을 왼쪽 값 / 중간 값 / 오른쪽 값으로 설정할 수 있는데 여기서는 중간 값으로 설정하겠습니다.)

1.2 pivot을 기준으로 작은 요소는 왼쪽으로, 큰 요소는 오른쪽으로 분할합니다.

1.3 왼쪽과 오른쪽 부분 배열을 재귀적으로 정렬합니다.

1.4 정렬된 부분 배열을 결합하여 정렬이 완료됩니다.

import java.util.Arrays;

public class QuickSort {
	public static void main(String[] args) {
        int[] arr = {10, 7, 8, 9, 1, 5};
        quickSort(arr);

        System.out.println("Sorted array: " + Arrays.toString(arr));
    }

    public static void quickSort(int[] arr) {
        if (arr == null || arr.length <= 1) {
            return;
        }
        // arr의 전체 범위를 정렬
        quickSort(arr, 0, arr.length - 1);
    }

    private static void quickSort(int[] arr, int low, int high) {
        if (low < high) {
            int pivot = partition(arr, low, high);

            // 피벗을 기준으로 왼쪽과 오른쪽 부분 배열을 재귀적으로 정렬
            quickSort(arr, low, pivot - 1);
            quickSort(arr, pivot + 1, high);
        }
    }

    private static int partition(int[] arr, int low, int high) {
        int middle = (low + high) / 2;
        int pivot = arr[middle];  // 중간 값을 pivot으로 선택
        swap(arr, middle, high);  // pivot을 배열의 마지막 요소에 위치

        int i = low - 1;  // i는 pivot보다 작은 요소의 마지막 인덱스를 추적하는 변수

        for (int j = low; j < high; j++) {  // 배열을 low에서 high - 1까지 순회
        	// 현재 요소 arr[j]를 pivot과 비교하여 작거나 같으면 왼쪽 부분 배열에 포함시키기 위해 i를 증가시키고, 
            // swap 함수를 사용하여 arr[i]와 arr[j]를 교환
            if (arr[j] <= pivot) {
                i++;
                swap(arr, i, j);
            }
        }
		
        // pivot을 기준으로 작은 값들을 왼쪽으로 모두 이동한 후, i + 1 위치에 있는 요소와 pivot 값을 교환
        swap(arr, i + 1, high);
        // pivot의 최종 위치 반환
        return i + 1; 
    }

    private static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}