📖 분할 정복
📌 분할 정복
✅ 분할 정복 기법
-
분할(Divide) : 해결할 문제를 여러 작은 부분으로 나눈다.
-
정복 (Conquer) : 나눈 작은 문제를 각각 해결한다.
-
통합 (Combine) : 해결된 해답을 모은다.
✅ 반복(Iterative) 알고리즘 : O(N)
Iterative Power(x, n)
result <- 1
FOR i in 1 -> n
result <- result * X
RETURN result✅ 거듭 제곱
- 분할 정복 기반 알고리즘 O(log N)
Recursive_Power(x, n)
IF n == 1 : RETURN x
IF n is even
y <- recursive_Power(x, n/2)
RETURN y*y
ELSE
y <- Recucrsive_Power(x, (n-1)/2)
RETURN y * y * x📌 이진 검색
✅ 이진 검색 (Binary Search)
-
자료의 가운데에 있는 항목의 키 값과 비교하여 다음 검색의 위치를 결정하고 검색을 계속 진행하는 방법
- 목적 키를 찾을 때까지 이진 검색을 순환적으로 반복 수행함으로써 검색 범위를 반으로 줄여가면서 보다 빠르게 검색 수행
-
자료가 정렬된 상태이어야 한다.
✅ 이진 검색 과정
- 자료의 중앙에 있는 원소를 고른다.
- 중앙 원소의 값과 찾고자 하는 목표 값을 비교한다.
- 중앙 원소의 값과 찾고자 하는 목표 값이 일치하면 탐색을 종료한다.
- 목표 값이 중앙 원소의 값보다 작으면 자료의 왼쪽 반에 대해서 새로 검색을 수행하고, 크다면 자료의 오른쪽 반에 대해서 새로 검색을 수행한다.
- 찾고자 하는 값을 찾을 때까지 1~4 과정을 반복한다.
✅ 이진 검색 알고리즘 : 반복구조
binarySearch(S[], n, k)
low <- 0
high <- n - 1
WHILE low <= high
mid <- (low + high) / 2
IF S[mid] == key
RETURN mid
ELIF S[mid] > key
high <- mid - 1
ELSE
low <- mid + 1
RETURN -1✅ 이진검색 자바 코드
public class BinarySearch {
private static int[] arr;
public static void main(String[] args) {
arr = new int[] {1, 3, 3, 5, 7, 8, 9};
System.out.println(binarySearch1(arr.length-1, 5));
System.out.println(binarySearch2(0, arr.length-1, 5));
}
public static int binarySearch1(int n, int key) {
int low = 0;
int high = n - 1;
while(low <= high) {
int mid = (low + high) / 2;
if(arr[mid] == key)
return mid;
else if(arr[mid] > key)
high = mid - 1;
else low = mid + 1;
}
return -1;
}
public static int binarySearch2(int low, int high, int key) {
if(low > high)
return -1;
else {
int mid = (low + high) / 2;
if(arr[mid] == key)
return mid;
else if(arr[mid] > key)
return binarySearch2(low, mid-1, key);
else
return binarySearch2(mid+1, high, key);
}
}
}
✅ 알고리즘 : 재귀구조
binarySearch(S[], low, high, key)
IF low > high
RETURN -1
ELSE
mid <- (low + high) / 2
IF key == S[mid]
RETURN mid
ELIF key < S[mid]
RETURN binarySearch(S[], low, mid - 1, key)
ELSE
RETURN binarySearch(S[], mid + 1, high, key)✅ 이진 검색 API
- java.util.Arrays.binarySearch
📌 병합 정렬
✅ 병합 정렬 (Merge Sort)
-
여러 정렬된 자료의 집합을 병합하여 한 개의 정렬된 집합으로 만드는 방식
-
분할 정복 알고리즘 활용
-
자료를 최소 단위의 문제까지 나눈 후에 차례대로 정렬하여 최종 결과를 얻어냄.
-
top-down 방식
-
안정 정렬
-
시간 복잡도 : O(nlogn)
✅ 병합 정렬 과정
- 분할 단계 : 전체 자료 집합에 대해서, 최소 크기의 부분집합이 될 때까지 분할 작업 계속
- 병합 단계 : 2개의 부분 집합을 정렬하면서 하나의 집합으로 병합
✅ 병합 정렬 pseudo code
- 분할 과정
mergeSort(arr[], left, right) {
IF left < right :
mid <- (left + right) / 2
mergeSort(arr, left, mid)
mergeSort(arr, mid+1, right)
merge(arr, left, mid, right)
}- 병합 과정
merge(arr[], left, mid, right) {
L <- left, R <- mid+1
idx <- left
while L <= mid && R <= right {
if arr[L] <= arr[R]
sortedArr[idx++] <- arr[L++]
else
sortedArr[idx++] <- arr[R++]
}
if L <= mid {
for i in L to mid
sortedArr[idx++] <- arr[i]
} else {
for j in R to right
sortedArr[idx++] <- arr[j]
}
for i in left to right
arr[i] <- sortedArr[i]
}✅ 병합 정렬 자바 코드
import java.io.IOException;
import java.util.Arrays;
public class mergesort {
private static int[] arr;
private static int[] sortedArr;
public static void main(String[] args) throws IOException {
arr = new int[]{7, 2, 2, 3, 9, 8, 0, 6, 1, 5};
sortedArr = new int[10];
MergeSort(0, arr.length - 1);
System.out.println(Arrays.toString(arr));
}
public static void MergeSort(int left, int right) {
if(left < right) {
int mid = (left + right) / 2;
MergeSort(left, mid);
MergeSort(mid+1, right);
Merge(left, right, mid);
}
}
public static void Merge(int left, int right, int mid) {
int idx = left;
int leftPointer = left;
int rightPointer = mid+1;
while(leftPointer <= mid && rightPointer <= right) {
if(arr[leftPointer] <= arr[rightPointer])
sortedArr[idx++] = arr[leftPointer++];
else
sortedArr[idx++] = arr[rightPointer++];
}
if(leftPointer <= mid) {
for(int i=leftPointer; i<=mid; i++)
sortedArr[idx++] = arr[i];
}
else {
for(int j=rightPointer; j<=right; j++)
sortedArr[idx++] = arr[j];
}
for(int i=left; i<=right; i++)
arr[i] = sortedArr[i];
}
}
📌 퀵 정렬
✅ 퀵 정렬
-
주어진 배열을 두 개로 분할하고, 각각을 정렬
- 병합 정렬과 비슷한가?
-
병합 정렬과의 차이 1 : 병합 정렬은 그냥 두 부분으로 나누지만, 퀵 정렬은 분할 할 때, 기준 (pivot)을 중심으로, 이보다 작은 것은 왼편, 큰 것은 오른편에 위치시킨다.
-
각 부분 정렬이 끝난 후, 병합 정렬은 병합이라는 후처리 작업이 필요하지만, 퀵정렬은 필요로 하지 않는다.
-
불안정 정렬
-
시간 복잡도 : =O(nlogn), 최악의 경우 O(n^2)
✅ 동작 과정
-
정렬한 배열 입력
-
임의의 한 점을 pivot으로 선정 (Partition 방법)
1) pivot 보다 작은 값들은 왼쪽으로, 큰 값들은 오른쪽으로 이동
- 정렬할 범위가 0이나 1이 될 때까지 분할 정복
✅ 알고리즘
quickSort(A[], l, r)
if l < r
pivot <- partition(a, l, r)
quickSort(A[], l, pivot - 1)
quickSort(A[], pivot + 1, r)✅ Hoare-Partition 알고리즘
Hoare-Partition(arr[], left, right) {
pivot <- arr[left] // 제일 왼쪽 값 pivot
L <- left+1, R <- right
while(L <= R) {
while(L <= R and arr[L] <= pivot) L++
while(arr[R] > pivot) R--
if(L<R)
swap(arr[L], arr[R])
}
swap(arr[left], arr[R])
return R
}-
아이디어
-
P(피봇) 값들 보다 큰 값은 오른쪽, 작은 값들은 왼쪽 집합에 위치하도록 한다.
-
피봇을 두 집합의 가운데에 위치시킨다.
-
피봇 선택
- 왼쪽 끝 / 오른쪽 끝 / 임의의 세개 값 중 중간값
-
✅ Lomuto Partition 알고리즘
Lomuto-Partition(arr[], left, right) {
pivot <- arr[right]
i <- left - 1
FOR j in left -> right - 1
IF arr[j] <= pivot
i++
swap(arr[i], arr[j])
swap(arr[i+1], arr[right])
RETURN i + 1
}
✅ 퀵 정렬 자바 코드
import java.util.Arrays;
public class quicksort1 {
private static int[] arr;
public static void main(String[] args) {
arr = new int[]{7, 2, 2, 3, 9, 8, 0, 6, 1, 5};
QuickSort(0, arr.length-1);
System.out.println(Arrays.toString(arr));
}
public static void QuickSort(int left, int right) {
if(left < right) {
// int pivot = HoarePartition(left, right);
int pivot = LomutoPartition(left, right);
QuickSort(left, pivot-1);
QuickSort(pivot+1, right);
}
}
public static int HoarePartition(int left, int right) {
int leftPointer = left+1;
int rightPointer = right;
int pivot = arr[left];
while(leftPointer <= rightPointer) {
while(leftPointer <= rightPointer && arr[leftPointer] <= pivot)
leftPointer++;
while(arr[rightPointer] > pivot)
rightPointer--;
if(leftPointer < rightPointer) {
int tmp = arr[leftPointer];
arr[leftPointer] = arr[rightPointer];
arr[rightPointer] = tmp;
}
}
arr[left] = arr[rightPointer];
arr[rightPointer] = pivot;
return rightPointer;
}
public static int LomutoPartition(int left, int right) {
int idx = left - 1;
int pivot = arr[right];
for(int i=left; i<=right - 1; i++) {
if(arr[i] <= pivot) {
idx++;
int tmp = arr[idx];
arr[idx] = arr[i];
arr[i] = tmp;
}
}
arr[right] = arr[idx+1];
arr[idx+1] = pivot;
return idx+1;
}
}
✅ 정렬 알고리즘 비교
개발 공부!