[컴퓨터알고리즘] Ch 3. 분할 정복 알고리즘(1)
사진을 클릭하면 PDF 정리본 다운로드 링크로 이어집니다.
🧐 분할 정복 알고리즘
-
주어진 문제의 입력을
분할
하여 문제를해결(정복)
하는 방식의 알고리즘-
분할한 입력에 대해 동일한 알고리즘을 적용하여 해를 계산
-
이들의 해를 취합하여 원래 문제의 해를 얻음
-
-
부분 문제와 부분 해
-
분할된 입력에 대한 문제를
부분 문제
라고 함 -
부분 문제의 해를 부분 해라고 함
-
부분 문제는 더 이상 분할할 수 없을 때까지 분할함.
-
- 대부분의 분할 정복 알고리즘은 문제의 입력을 단순히 분할만 해서는 해를 구할 수 없고, 분할된 부분 문제들을 정복해야 함.
❓ 문제
입력 크기가 일 때 총 몇 번 분할하여야 더 이상 분할할 수 없는 크기인 이 될까?
답을 계산하기 위해 분할한 총 횟수를 라고 하면 일 때 더 이상 분할할 수 없으므로, 임을 확인할 수 있다.
-
분할 정복 알고리즘의 분류
-
문제가 개로 분할되고, 부분 문제의 크기가 로 감소하는 알고리즘
a b Alg 2 2 합병정렬, 최근접 점의 쌍 찾기, 공제선 문제 3 2 큰 정수의 곱셈 4 2 큰 정수의 곱셈 7 2 스트라센의 행렬 곱셈 알고리즘 -
문제가 개로 분할되고, 부분 문제의 크기가 일정하지 않은 크기로 감소하는 알고리즘
⇒퀵 정렬
-
문제가 개로 분할되나, 그 중에 개의 부분 문제는 고려할 필요가 없으며, 부분 문제의 크기가 로 감소하는 알고리즘
⇒이진 탐색
-
문제가 개로 분할되나, 그 중에 개의 부분 문제는 고려할 필요가 없으며, 부분 문제의 크기가 일정하지 않은 크기 로 감소하는 알고리즘
⇒선택 문제 알고리즘
-
부분 문제의 크기가 , 개씩 감소하는 알고리즘
⇒삽입 정렬, 피보나치 수의 계산
-
🧐 3.1 합병 정렬(Merge Sort)
-
합병 정렬
-
개의 숫자들을 개씩 개의 부분 문제로 분할
-
각각의 부분 문제를 순환으로 합병 정렬
-
개의 정렬된 부분을 합병하여 정렬(정복)
- 합병 과정이 문제를 정복하는 것임.
- 합병 과정이 문제를 정복하는 것임.
-
👩🏻💻 의사코드로 표현해본다면?
Alg MergeSort(A, p, q)
input array A of size n, integer p, integer q
output sorted array A
if(p < q) {
k = ⌊(p + q) / 2⌋
MergeSort(A, p, k)
MergeSort(A, k+1, q)
Merge array A from p to q
}
-
시간 복잡도
-
분할하는 부분
- 배열의 중간 인덱스 계산과 번의 순환 호출.
-
합병하는 부분
- 각 계층에서 모든 숫자가 합병에 참여하고 있으므로, 합병의 수행 시간은 합병되는 입력 크기에 비례한다.
⇒ 각 층에서 . 층수는 .
- 각 계층에서 모든 숫자가 합병에 참여하고 있으므로, 합병의 수행 시간은 합병되는 입력 크기에 비례한다.
-
합병 정렬의 시간 복잡도
⇒ (층수)
위의 계산대로라면 시간 복잡도는 이 되어야 하는데, 왜 일까? 이는
마스터 정리
에 의한 계산법인데, 자세한 사항은 Ch 3(2)에서 설명하려한다. -
-
합병 정렬의 단점
-
대부분의 정렬 알고리즘들은 입력을 위한 메모리 공간과 크기의 메모리 공간만을 사용하면서 정렬을 수행함.
-
합병 정렬은 입력을 위한 메모리 공간외에 추가로 입력과 같은 크기의 공간(임시 배열)이 별도로 필요함.
- 2개의 정렬된 부분을 하나로 합병하기 위해, 합병된 결과를 저장할 곳이 필요하기 때문임.
-
합병 정렬의 공간 복잡도
⇒
-
-
-
합병 정렬은 외부 정렬의 기본이 되는 정렬 알고리즘
-
연결 리스트에 있는 데이터를 정렬할 때 퀵 정렬이나 힙 정렬보다 훨씬 효율적임.
-
멀티코어 CPU와 다수의 프로세서로 구성된 그래픽 처리 장치의 등장으로 정렬 알고리즘을 병렬화하는데에 합병 정렬 알고리즘이 활용됨.
-
🧐 3.2 퀵 정렬(Quick Sort)
-
퀵 정렬 알고리즘은 문제를 2개의 부분 문제로 분할함.
- 사실 알고리즘이 수행되는 과정을 살펴보면 정복 후 분할하는 알고리즘
- 사실 알고리즘이 수행되는 과정을 살펴보면 정복 후 분할하는 알고리즘
-
퀵 정렬의 아이디어
- 원소를 기준으로 보다 작은 숫자들은 왼편으로, 보다 큰 숫자들은 오른편으로 위치시키고 을 그 사이에 놓는다.
- 분할된 부분 문제들에 대해서도 위와 동일한 과정을 순환으로 수행하여 정렬한다.
👩🏻💻 의사코드로 표현해본다면?
Alg QuickSort(A, left, right)
input array A of size n, integer left, integer right
output sorted array A
1. if(left < right) {
2. pivot을 A[left]~A[right]에서 선택
pivot을 A[left]와 자리 변경
pivot과 배열의 원소를 비교
pivot보다 작은 숫자는 A[left]~A[p-1]
pivot보다 큰 숫자는 A[p]~A[right]
A[p] = pivot
3. QuickSort(A, left, p-1)
4. QuickSort(A, p+1, right)
}
c코드로 함수를 나타내면 아래와 같다.
int partition(int list[], int left, int right)
{
int pivot, temp, low, high;
pivot = list[left];
low = left; high = right + 1;
do
{
do
low++;
while(list[low] < pivot);
do
high--;
while(list[high] > pivot);
if(low < high)
SWAP(list[low], list[high], temp);
} while(low < high);
SWAP(list[left], list[high], temp);
return high;
}
void quickSort(int list[], int left, int right)
{
if(left < right)
{
int q = partition(list, left, right);
quickSort(list, left, q - 1);
quickSort(list, q + 1, right);
}
}
-
최악 경우 시간 복잡도
- 항상 최소 숫자가 선택되는 경우
⇒
⇒ 즉,- 단, 이 랜덤하게 선택될 때, 이런 결과가 나올 확률은 낮다는 것이 과학적으로 증명되었다.
- 단, 이 랜덤하게 선택될 때, 이런 결과가 나올 확률은 낮다는 것이 과학적으로 증명되었다.
- 항상 최소 숫자가 선택되는 경우
-
최선의 경우 시간 복잡도
- 항상 로 분할되는 경우
⇒ (총 비교 횟수) = × (층수) =
⇒ 즉,
- 항상 로 분할되는 경우
-
평균 경우 시간 복잡도
- 을 항상 랜덤하게 선택한다고 가정
⇒
- 을 항상 랜덤하게 선택한다고 가정
-
선정 방법
- 세 숫자의 중앙값으로 을 선정하는 방법
⇒ - 삼등분한 후 각 부분에서 가장 왼쪽 숫자, 중 간 숫자, 가장 오른쪽 숫자 중에서 중앙값을 찾은 후, 세 중앙값들 중에서 중앙값을 으로 선정하는 방법
⇒
- 세 숫자의 중앙값으로 을 선정하는 방법
-
성능 향상 방법
- 입력의 크기가 매우 클 때, 퀵 정렬의 성능을 더 향상시키기 위해서 삽입 정렬을 동시에 사용
- 입력의 크기가 작을 때에는 순환 호출로 수행되는 퀵 정렬이 삽입 정렬보다 느림.
⇒ 부분 문제의 크기가 작아지면 더 이상의 분할(순환 호출)을 중단하고 삽입 정렬을 사용
-
- 퀵 정렬은 커다란 크기의 입력에 대해서 가장 좋은 성능을 보이는 정렬 알고리즘
- 퀵 정렬은 실질적으로 어느 정렬 알고리즘보다 좋은 성능을 보임.
Author And Source
이 문제에 관하여([컴퓨터알고리즘] Ch 3. 분할 정복 알고리즘(1)), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@gangjjang5/컴퓨터알고리즘-Ch-3.-분할-정복-알고리즘1저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)