[컴퓨터알고리즘] Ch 3. 분할 정복 알고리즘(1)

사진을 클릭하면 PDF 정리본 다운로드 링크로 이어집니다.

🧐 분할 정복 알고리즘

• 주어진 문제의 입력을 분할하여 문제를 해결(정복)하는 방식의 알고리즘

  • 분할한 입력에 대해 동일한 알고리즘을 적용하여 해를 계산

  • 이들의 해를 취합하여 원래 문제의 해를 얻음

• 부분 문제와 부분 해

  • 분할된 입력에 대한 문제를 부분 문제라고 함

  • 부분 문제의 해를 부분 해라고 함

  • 부분 문제는 더 이상 분할할 수 없을 때까지 분할함.

• 대부분의 분할 정복 알고리즘은 문제의 입력을 단순히 분할만 해서는 해를 구할 수 없고, 분할된 부분 문제들을 정복해야 함.

❓ 문제

입력 크기가 $n$일 때 총 몇 번 분할하여야 더 이상 분할할 수 없는 크기인 $1$이 될까?

답을 계산하기 위해 분할한 총 횟수를 $k$라고 하면 $n/2^k = 1$일 때 더 이상 분할할 수 없으므로, $k = log_2n$임을 확인할 수 있다.

• 분할 정복 알고리즘의 분류

  • 문제가 $a$개로 분할되고, 부분 문제의 크기가 $1/b$로 감소하는 알고리즘

    a	b	Alg
    2	2	합병정렬, 최근접 점의 쌍 찾기, 공제선 문제
    3	2	큰 정수의 곱셈
    4	2	큰 정수의 곱셈
    7	2	스트라센의 행렬 곱셈 알고리즘

  • 문제가 $2$개로 분할되고, 부분 문제의 크기가 일정하지 않은 크기로 감소하는 알고리즘
    ⇒퀵 정렬

  • 문제가 $2$개로 분할되나, 그 중에 $1$개의 부분 문제는 고려할 필요가 없으며, 부분 문제의 크기가 $1/2$로 감소하는 알고리즘
    ⇒ 이진 탐색

  • 문제가 $2$개로 분할되나, 그 중에 $1$개의 부분 문제는 고려할 필요가 없으며, 부분 문제의 크기가 일정하지 않은 크기 로 감소하는 알고리즘
    ⇒ 선택 문제 알고리즘

  • 부분 문제의 크기가 $1$, $2$개씩 감소하는 알고리즘
    ⇒ 삽입 정렬, 피보나치 수의 계산

🧐 3.1 합병 정렬(Merge Sort)

• 합병 정렬

  • $n$개의 숫자들을 $n/2$개씩 $2$개의 부분 문제로 분할

  • 각각의 부분 문제를 순환으로 합병 정렬

  • $2$개의 정렬된 부분을 합병하여 정렬(정복)

    • 합병 과정이 문제를 정복하는 것임.
      
      

👩🏻‍💻 의사코드로 표현해본다면?

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
}

• 시간 복잡도

  • 분할하는 부분

    • 배열의 중간 인덱스 계산과 $2$번의 순환 호출. $O(1)$

  • 합병하는 부분

    • 각 계층에서 모든 숫자가 합병에 참여하고 있으므로, 합병의 수행 시간은 합병되는 입력 크기에 비례한다.
      ⇒ 각 층에서 $O(n)$. 층수는 $log_2n$.

  • 합병 정렬의 시간 복잡도
    ⇒ (층수) $× O(n) = log2n × O(n) = O(nlogn)$

  위의 계산대로라면 시간 복잡도는 $O(nlog_2n)$이 되어야 하는데, 왜 $O(nlogn)$일까? 이는 마스터 정리에 의한 계산법인데, 자세한 사항은 Ch 3(2)에서 설명하려한다.

• 합병 정렬의 단점

  • 대부분의 정렬 알고리즘들은 입력을 위한 메모리 공간과 $O(1)$ 크기의 메모리 공간만을 사용하면서 정렬을 수행함.

  • 합병 정렬은 입력을 위한 메모리 공간외에 추가로 입력과 같은 크기의 공간(임시 배열)이 별도로 필요함.

    • 2개의 정렬된 부분을 하나로 합병하기 위해, 합병된 결과를 저장할 곳이 필요하기 때문임.

  • 합병 정렬의 공간 복잡도
    ⇒ $O(n)$

• $Applications$

  • 합병 정렬은 외부 정렬의 기본이 되는 정렬 알고리즘

  • 연결 리스트에 있는 데이터를 정렬할 때 퀵 정렬이나 힙 정렬보다 훨씬 효율적임.

  • 멀티코어 CPU와 다수의 프로세서로 구성된 그래픽 처리 장치의 등장으로 정렬 알고리즘을 병렬화하는데에 합병 정렬 알고리즘이 활용됨.

🧐 3.2 퀵 정렬(Quick Sort)

• 퀵 정렬 알고리즘은 문제를 2개의 부분 문제로 분할함.

  • 사실 알고리즘이 수행되는 과정을 살펴보면 정복 후 분할하는 알고리즘
    
    

• 퀵 정렬의 아이디어

  • $pivot$ 원소를 기준으로 $pivot$보다 작은 숫자들은 왼편으로, $pivot$보다 큰 숫자들은 오른편으로 위치시키고 $pivot$을 그 사이에 놓는다.
  • 분할된 부분 문제들에 대해서도 위와 동일한 과정을 순환으로 수행하여 정렬한다.
  
  

👩🏻‍💻 의사코드로 표현해본다면?

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);
    }
}

• 최악 경우 시간 복잡도

  • 항상 최소 숫자가 선택되는 경우
    ⇒ $(n-1)+(n-2)+…+2+1 = n(n-1)/2$
    ⇒ 즉, $O(n^2)$
    • 단, $pivot$이 랜덤하게 선택될 때, 이런 결과가 나올 확률은 낮다는 것이 과학적으로 증명되었다.
      
      

• 최선의 경우 시간 복잡도

  • 항상 $1/2$로 분할되는 경우
    ⇒ (총 비교 횟수) = $O(n)$ × (층수) = $O(n) × logn$
    ⇒ 즉, $O(nlogn)$

• 평균 경우 시간 복잡도

  • $pivot$을 항상 랜덤하게 선택한다고 가정
    ⇒ $O(nlogn)$

• $pivot$ 선정 방법

  • 세 숫자의 중앙값으로 $pivot$을 선정하는 방법
    ⇒ $Median-of-Three$
  • 삼등분한 후 각 부분에서 가장 왼쪽 숫자, 중 간 숫자, 가장 오른쪽 숫자 중에서 중앙값을 찾은 후, 세 중앙값들 중에서 중앙값을 $pivot$ 으로 선정하는 방법
    ⇒ $Median-of-Medians$
    
    
    

• 성능 향상 방법

  • 입력의 크기가 매우 클 때, 퀵 정렬의 성능을 더 향상시키기 위해서 삽입 정렬을 동시에 사용
  • 입력의 크기가 작을 때에는 순환 호출로 수행되는 퀵 정렬이 삽입 정렬보다 느림.
    ⇒ 부분 문제의 크기가 작아지면 더 이상의 분할(순환 호출)을 중단하고 삽입 정렬을 사용

• $Applications$

  • 퀵 정렬은 커다란 크기의 입력에 대해서 가장 좋은 성능을 보이는 정렬 알고리즘
  • 퀵 정렬은 실질적으로 어느 정렬 알고리즘보다 좋은 성능을 보임.