분할정복 알고리즘
- 분할정복 알고리즘이란?
사전적 의미
-
병합정렬
2.1 정의
2.2 코드 -
퀵정렬
3.1 정의
3.2 코드 -
이진탐색
4.1 정의
4.2 코드 - 알고리즘 비교
1. 분할정복 알고리즘(Divide and conquer algorithm)
-
분할정복 알고리즘 (Divide and conquer algorithm)은 그대로 해결할 수 없는 문제를 작은 문제로 분할하여 문제를 해결하는 방법이다.
-
예시로는 병합정렬, 퀵정렬, 이진탐색이 있으며 후술할 예정이다.
2. 합병정렬(Merge sort)
- 합병정렬이란
하나의 리스트를 두 개의 균등한 크기로 분할하고 분할된 부분 리스트를 정렬한 다음, 두 개의 정렬된 부분 리스트를 합하여 전체가 정렬된 리스트가 되게 하는 방법이다.
-
동작과정
-
분할정복 알고리즘의 단계는 크게 Devide(나누기), Conquer(재귀적으로 문제 해결), Combine(통합) 의 단계로 이루어진다.
1) Divide
→ 입력 배열을 같은 크기의 2개의 부분 배열로 분할한다.
2) Conquer
→ 부분 배열을 정렬한다. 부분 배열의 크기가 충분히 작지 않으면 순환 호출을 이용하여 다시 분할 정복 방법을 적용한다.
3) Combine
→ 정렬된 부분 배열들을 하나의 배열에 합병한다.
- 예시코드
public class DivideAndConquer { private boolean isSomething(int start, int end) { return start >= end; } public int[] mergeSort(int[] arr, int start, int end) { if (isSomething(start, end)) { return null; } int mid = (start + end) / 2; mergeSort(arr, 0, mid); mergeSort(arr, mid+1, end); merge(arr, start, mid, end); return null; } private int[] merge(int[] arr, int start, int mid, int end) { int p = start; int q = mid + 1; int idx = p; int[] tmp = new int[arr.length]; while(p <= mid || q <= end) { if (q > end || (p <= mid && arr[p] < arr[q])) { tmp[idx++] = arr[p++]; } else { tmp[idx++] = arr[q++]; } } for (int i=start; i<=end; i++) { arr[i] = tmp[i]; } return null; } public static void main(String[] args) { int arr[] = {7, 6, 5, 4, 3, 2, 1, 0}; for (int i=0; i<arr.length; i++) { System.out.printf("%d ", arr[i]); } System.out.println(); DivideAndConquer dac = new DivideAndConquer(); dac.mergeSort(arr, 0, arr.length-1); for (int i=0; i<arr.length; i++) { System.out.printf("%d ", arr[i]); } System.out.println(); } }
3.퀵 정렬(Quick sort)
- 퀵 정렬이란
특정 원소 피봇(pivot)을 기준으로 주어진 배열을 두 부분 배열로 분할하고 각 부분 배열에 대해 퀵 정렬을 순환적으로 적용하는 방식이다.
- 동작과정
1) Divide
→ 피봇 하나를 선택하여 피봇을 기준으로 2개의 부분 배열로 분할한다.
2) Conquer
→ 피봇을 기준으로 피봇보다 큰 값, 혹은 작은 값을 찾는다. 왼쪽에서 부터 피봇보다 큰 값을 찾고 오른쪽에서 부터는 피봇보다 작은 값을 찾아서 두 원소를 교환한다. 분할된 부분 배열의 크기가 0이나 1일 될때까지 반복한다.
- 예시 코드
public class Main {
static int[] arr;
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
int n = Integer.parseInt(br.readLine());
arr = new int[n];
for(int i=0; i<n; i++) {
arr[i] = Integer.parseInt(br.readLine());
}
quickSort(0,n-1);
for(int num : arr) {
sb.append(num+"\n");
}
System.out.println(sb.toString());
}
static void quickSort(int left, int right) {
if(left>= right) {
return;
}
int pivot = partition(left, right);
quickSort(left,pivot-1);
quickSort(pivot+1,right);
}
static int partition(int left, int right) {
int pivot = arr[left];
int i = left;
int j = right;
while(i < j) {
while(arr[j] > pivot&& i<j) {
j--;
}
while(arr[i] <= pivot && i<j) {
i++;
}
swap(i,j);
}
swap(left,i);
return i;
}
static void swap(int i, int j) {
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
}
-
단점
퀵 정렬의 경우 피봇의 위치나 배열의 상태에 따라 최악의 경우 O($n^2$)이 나올 수도 있다.
4. 이진탐색(Binary search)
- 이진탐색이란
정렬된 데이터를 효과적으로 탐색할 수 있는 방법이다.
-
동작과정
1) Divide→ 배열의 가운데 원소를 기준으로 왼쪽, 오른쪽 부분배열로 분할한다. 탐색키와 가운데 원소가 같으면 분할을 종료한다.
2) Conquer
→ 탐색키가 가운데 원소보다 작으면 왼쪽 부분배열을 대상으로 이진 탐색을 순환 호출하고, 크면 오른쪽 부분배열을 대상으로 이진 탐색을 호출한다.
<br>
- 예시코드
static int binarySearch(int[] arr, int left, int right, int key) { int mid =0; while(left<= right) { mid = (left+right)/2; if(key == arr[mid]) return mid; if(arr[mid] < key) { left = mid+1; }else { right = mid; } } return -1; // 찾지못했을 경우 }
5. 알고리즘과 비교
| 정렬 알고리즘 | 최대 실행시간 | 최소 실행시간 | 평균 실행시간 |
|---|---|---|---|
| 병합 정렬 | O(log n) | O(log n) | O(log n) |
| 퀵 정렬 | O(n^2) | O(log n) | O(log n) |
Leave a comment