원리
주어진 입력을 더 이상 나눌 수 없을 때까지 두 개 이상의 작은 문제들로 순환적으로 분할하고,
이렇게 분할된 작은 문제들을 각각 해결한 후 이들의 해를 결합하여 원래 문제의 해를 구하는 방식입니다.
특성
- 분할된 작은 문제는 원래의 문제에 비해 입력 크기만 작아졌을 뿐 문제 자체는 원래 문제와 동일해야 합니다.
- 분할된 작은 문제들은 서로 독립적이어야 합니다.
- 하샹식 접근 방법을 사용합니다.
- 분할 -> 정복 -> 결합의 처리과정을 거칩니다.
종류
- 이진탐색 - 크기가 n인 문제를 n/2인 두 개의 작은 문제로 분할(그 중 하나의 작은 문제는 처리 대상에서 제외)
- 합병정렬 - 크기가 n인 문제를 n/2인 두 개의 작은 문제로 분할
- 퀵 정렬 - 크기가 n인 문제를 크기는 감소하지만 일정하지 않은 크기의 두 작은 문제로 분할
- 선택 문제 - 크기가 n인 문제를 크기는 감소하지만일정하지 않은 크기의 두 작은 문제로 분할(그 중 하나의 작은 문제는 처리 대상에서 제외)
이진탐색
개념과 원리
탐색은 배열 형태로 주어진 데이터에서 원하는 값을 가진 데이터를 찾는 문제이다.
이진 탐색 알고리즘은 배열을 가운데 원소를 기준으로 왼쪽 부분배열과 오른쪽 부분배열로 분할한다.(분할)
탐색키 x가 가운데 원소와 같으면 해당 인덱스를 반환하고 종료한다.
x가 가운데 원소보다 작으면 왼쪽 부분배열, 크면 오른쪽 부분배열을 대상으로 이진 탐색을 순환호출한다.
탐색을 다시 수행할 때마다 탐색 범위가 절반으로 줄어든다.(정복)
알고리즘
BinarySearch(A[], Left, Right, x) // 순환 형태로 표현된 이진 탐색
입력 - A[Left...Right] : 탐색 대상 배열, 오름차순으로 정렬되어 있다고 가정
Left, Right : A에서 x를 찾는 구간
x : 탐색키
출력 - 배열 A에서 x의 위치(탐색 실패한 경우 -1)
{
if(Left > Right) return -1; // 탐색키가 존재하지 않는 경우
Mid = (Left+Right)/2;
if(x == A[Mid]) return Mid;
else if(x < A[Mid]) BinarySearch(A, Left, Mid -1, x); // 왼쪽 부분배열 탐색
else BinarySearch(A, Mid+1, Right, x); // 오른쪽 부분배열 탐색
}BinarySearch(A[], n, x) // 반복 형태로 표현된 이진 탐색
입력 - A[0...n-1] : 탐색 대상 배열, 오름차순으로 정렬되어 있다고 가정
n : 탐색 대상 원소의 개수(배열의 크기)
x : 탐색키
출력 - 배열 A에서 x의 위치(탐색 실패한 경우 -1)
{
Left = 0;
Right = n-1;
while(Left <= Right) {
Mid = (Left + Right)/2;
if(x == A[Mid]) return Mid;
else if (x < A[Mid]) Right = Mid -1; // 왼쪽 부분배열 탐색
else Left = Mid + 1; // 오른쪽 부분배열 탐색
}
return -1; // 탐색키가 존재하지 않는 경우
}
성능 : O(log n)
특징
- 정렬된 리스트에 대해서만 적용 가능하다.
- 데이터의 삽입/삭제 연산을 수행하면 데이터의 이동이 발생한다.
- 데이터 삽입/삭제 후에는 정렬 상태로 유지하기 위해 평균적으로 n/2개의 데이터를 이동해야 하기 때문에 삽입과 삭제가 빈번한 응용에서의 탐색으로는 적합하지 않다.
합병 정렬
개념과 원리
합병 정렬은 주어진 배열을 동일한 크기의 두 개의 부분배열로 분할하고, 각각의 부분배열을 순환적으로 합병 정렬을 한 후, 정렬된 두개의 부분배열을 결합하여 하나의 정렬된 배열을 만드는 방법입니다.
입력된 크기가 n인 배열을 n/2개의 원소를 가진 두 부분배열로 분할한다.(분할)
각각의 부분배열에 대해서 합병 정렬을 순환적으로 적용하여 부분배열을 정렬한다.(정복)
정렬된 두 부분배열을 합병하여 하나의 정렬된 배열을 만든다.(결합)
알고리즘
MergeSort(A[], n)
입력 - A[0...n-1] : 정렬할 배열
n : 정렬할 원소의 개수
출력 - A[0...n-1] : 정렬된 배열
{
if(n > 1) {
Mid = n/2;
// 왼쪽 부분배열의 순환호출
B[0...Mid-1] = MergeSort(A[0...Mid-1], Mid);
// 오른쪽 부분배열의 순환호출
C[0...n-Mid-1] = MergeSort(A[Mid...n-1], n-Mid);
// 정렬된 두 부분배열의 합병
A[0...n-1] = Merge(B[0...Mid-1], C[0...n-Mid-1), Mid, n-Mid);
}
return A;
}
Merge(B[], C[], n, m)
입력 - B[0...n-1], C[0...m-1] : 합병할 두 정렬된 부분배열
출력 - A[0...n + m-1] : 합병된 하나의 정렬된 배열
{
i = j = k = 0;
while(i < n && j < m) {
if(B[i] <= C[j]) // 부분배열 B[i]와 C[j]를 비교해서 작은 값을 선택
A[k++] = B[i++]; // B[i]를 선택 후 다음에 비교할 원소를 지정하기 위해 인덱스 1증가
else A[k++] = C[j++]; // C[j]를 선택 후 다음에 비교할 원소를 지정하기 위해 인덱스 1증가
}
// 한 쪽 부분배열에 모든 원소가 A배열에 저장되면 다른 쪽 부분배열에는 원소가 남게 된다.
// 따라서 남은 모든 원소를 차례대로 선택해 A배열에 저장한다.
for( ; i<n; i++)
A[k++] = B[i];
for( ; j<m; j++)
A[k++] = C[j];
return A[0...n+m-1];
}성능 : O(nlogn)
특징
알고리즘을 보면 배열 A이외에 배열 B와 C가 추가적으로 사용된다. 배열 B와 C는 입력 배열을 분할한 두 부분배열의 정렬된 결과를 저장하기 위한 것으로, 두 배열의 크기의 합은 배열 A와 동일하다.
즉, 합병정렬을 수행하기 위해서는 입력 데이터 개수만큼의 추가 저장 장소가 필요하다.