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

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

🧐 분할 정복 알고리즘


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

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

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


  • 부분 문제와 부분 해

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

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

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


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



❓ 문제

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

답을 계산하기 위해 분할한 총 횟수를 kk라고 하면 n/2k=1n/2^k = 1



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

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

      abAlg
      22합병정렬, 최근접 점의 쌍 찾기, 공제선 문제
      32큰 정수의 곱셈
      42큰 정수의 곱셈
      72스트라센의 행렬 곱셈 알고리즘
    • 문제가 22개로 분할되고, 부분 문제의 크기가 일정하지 않은 크기로 감소하는 알고리즘
      퀵 정렬

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

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

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



🧐 3.1 합병 정렬(Merge Sort)


  • 합병 정렬

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

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

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

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

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

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) / 2MergeSort(A, p, k)
    MergeSort(A, k+1, q)
    Merge array A from p to q
}

  • 시간 복잡도

    • 분할하는 부분

      • 배열의 중간 인덱스 계산과 22번의 순환 호출. O(1)O(1)
    • 합병하는 부분

      • 각 계층에서 모든 숫자가 합병에 참여하고 있으므로, 합병의 수행 시간은 합병되는 입력 크기에 비례한다.
        ⇒ 각 층에서 O(n)O(n). 층수는 log2nlog_2n
    • 합병 정렬의 시간 복잡도
      ⇒ (층수) ×O(n)=log2n×O(n)=O(nlogn)× O(n) = log2n × O(n) = O(nlogn)

    위의 계산대로라면 시간 복잡도는 O(nlog2n)O(nlog_2n)

  • 합병 정렬의 단점

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

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

      • 2개의 정렬된 부분을 하나로 합병하기 위해, 합병된 결과를 저장할 곳이 필요하기 때문임.
    • 합병 정렬의 공간 복잡도
      O(n)O(n)


  • ApplicationsApplications

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

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

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



🧐 3.2 퀵 정렬(Quick Sort)


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

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

  • 퀵 정렬의 아이디어

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

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


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



  • 최악 경우 시간 복잡도

    • 항상 최소 숫자가 선택되는 경우
      (n1)+(n2)++2+1=n(n1)/2(n-1)+(n-2)+…+2+1 = n(n-1)/2
  • 최선의 경우 시간 복잡도

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

  • 평균 경우 시간 복잡도

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

  • pivotpivot 선정 방법

    • 세 숫자의 중앙값으로 pivotpivot을 선정하는 방법
      MedianofThreeMedian-of-Three
    • 삼등분한 후 각 부분에서 가장 왼쪽 숫자, 중 간 숫자, 가장 오른쪽 숫자 중에서 중앙값을 찾은 후, 세 중앙값들 중에서 중앙값을 pivotpivot 으로 선정하는 방법
      MedianofMediansMedian-of-Medians
  • 성능 향상 방법

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

  • ApplicationsApplications

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

좋은 웹페이지 즐겨찾기