분할 정복(Divide and Conquer)
알고리즘 디자인 패러다임 중 하나로, 큰 문제를 작은 부분 문제로 분할하여 해결하고, 이를 결합하여 원래 문제의 해를 구하는 방법입니다. 분할 정복은 다음과 같은 세 가지 단계로 구성됩니다.
분할(Divide)
원래 문제를 작은 부분 문제로 분할합니다. 일반적으로 문제를 동일한 구조를 가진 여러 하위 문제로 나눕니다.
정복(Conquer)
분할된 작은 부분 문제를 재귀적으로 해결합니다. 부분 문제의 크기가 충분히 작으면 직접 해결합니다.
결합(Combine)
작은 부분 문제의 해를 결합하여 원래 문제의 해를 구합니다. 이 단계에서 각 부분 문제의 해를 조합하거나 합산하여 최종 결과를 얻습니다.
분할 정복은 일반적으로 재귀적인 방법으로 구현됩니다. 큰 문제를 작은 부분 문제로 재귀적으로 나누어 해결하고, 작은 문제들의 해를 결합하여 전체 문제의 해를 얻습니다. 이를 통해 문제를 더 작고 해결하기 쉬운 부분으로 분해하여 해결할 수 있습니다.
분할 정복은 다양한 문제에 적용될 수 있으며, 효율적인 알고리즘을 설계하는 데에 유용합니다. 대표적인 예시로는 병합 정렬(Merge Sort), 퀵 정렬(Quick Sort), 이진 검색(Binary Search), 최대 부분 배열 문제(Maximum Subarray Problem) 등이 있습니다. 이러한 알고리즘들은 분할 정복의 원리에 따라 작동하며, 분할 정복을 통해 시간 복잡도를 효과적으로 개선할 수 있습니다.
Example
import java.util.Arrays;
public class QuickSort {
public static void quickSort(int[] arr) {
quickSort(arr, 0, arr.length - 1);
}
private static void quickSort(int[] arr, int left, int right) {
if (left < right) {
int pivotIndex = partition(arr, left, right);
quickSort(arr, left, pivotIndex - 1);
quickSort(arr, pivotIndex + 1, right);
}
}
private static int partition(int[] arr, int left, int right) {
int pivot = arr[right];
int i = left - 1;
for (int j = left; j < right; j++) {
if (arr[j] < pivot) {
i++;
swap(arr, i, j);
}
}
swap(arr, i + 1, right);
return i + 1;
}
private static void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
public static void main(String[] args) {
int[] arr = {5, 2, 9, 1, 7, 6, 3};
quickSort(arr);
System.out.println(Arrays.toString(arr));
}
}
위의 예시 코드에서 quickSort메서느는 정렬할 배열 arr을 매개변수로 받아 퀵 정렬을 수행합니다.quickSort 메서드는 오버로딩되어서 quickSort(arr, left, right)형태로 재귀적으로 호출합니다. left와 right는 현재 분할된 부분 배열의 시작 인덱스와 끝 인덱스를 나타냅니다.
partition 메서드는 배열의 맨 오른쪽 요소를 기준으로 작은 값은 왼쪽으로 큰 값은 오른쪽으로 분할합니다. i 변수는 작은 값들의 구역을 나타내며 j변수는 탐색하는 인덱스를 나타냅니다. 작은 값이 나타날 때마다 i 와 j 인덱스의 요소를 교환하여 작은 값들을 왼쪽으로 모으고, 마지막으로 기준 요소인 povot과 i+1 인덱스의 요소를 교환하여 정렬을 완료합니다.
주어진 arr은 { 5,2,9,1,7,6,3 }이며 결과로 [1,2,3,5,6,7,9]를 출력합니다.
