[지연/week2] 분할 정복과 병합정렬, 퀵정렬

분할 정복(Divide and Conquer)이란?

분할 정복법(Divide and Conquer)은 여러 알고리즘의 기본이 되는 해결 방법으로, 기본적으로는 엄청나게 크고 방대한 문제를 조금씩 조금씩 나눠가면서 용이하게 풀 수 있는 문제 단위로 나눈 다음 그것들을 다시 합쳐서 해결하자는 개념에서 출발하였다. 대표적으로는 퀵소트나 합병 정렬이 있다.

적용 방식

분할 정복법은 재귀적으로 자신을 호출하면서 그 연산의 단위를 조금씩 줄어가는 방식이다. 예는 아래와 같다.

function F(x):
  if F(x)가 간단 then:
    return F(x)를 계산한 값
  else:
    x 를 x1, x2로 분할
    F(x1)과 F(x2)를 호출
    return F(x1), F(x2)로 F(x)를 구한 값

분할 정복의 장점

문제를 나눔으로써 어려운 문제를 해결할 수 있다는 엄청난 장점이 있다.

분할 정복의 단점

함수를 재귀적으로 호출한다는 점에서 함수 호출로 인한 오버헤드가 발생하며, 스택에 다양한 데이터를 보관하고 있어야 하므로 스택 오버플로우가 발생하거나 과도한 메모리 사용을 되는 단점이 있다. 가장 중요한 것은 이 알고리즘의 핵심인 “F(x)가 간단”이 어떤 것이냐에 따라 알고리즘의 퍼포먼스가 생각보다 꽤 차이나게 된다는 것이다. 이 “F(x)가 간단하다”라는 것을 정의하는 것의 난해함 역시 단점 중에서 중요하게다루어지고 있다.

알고리즘을 설계하는 요령

1. Divide (분할) : 문제 분할이 가능한 경우, 2개 이상의 문제로 나눈다.
2. Conquer (정복) : 나누어진 문제가 여전히 분할이 가능하면, 또 다시 Divide를 수행한다. 그렇지 않으면 문제를 푼다.
3. Combine (결합) : Conquer 한 문제들을 통합하여 원래 문제의 답을 얻는다.

• 문제를 제대로 나누면 Conquer 하는 것은 쉽기 때문에 Divide를 제대로 하는 것이 가장 중요하다.
• 분할 정복 알고리즘은 재귀 알고리즘이 많이 사용되는데, 이 부분에서 분할 정복 알고리즘의 효율성을 깎아내릴 수 있다.

분할 정복을 사용하는 알고리즘의 구성 요소

• 문제를 더 작은 문제로 분할하는 과정 (divide)
• 각 문제에 대해 구한 답을 원래 문제에 대한 답으로 병합하는 과정 (merge)
• 더이상 답을 분할하지 않고 곧장 풀 수 있는 매우 작은 문제 (base case)

예시 - 1부터 n까지의 합을 구하는 분할 정복 알고리즘

//필수조건 : n은 자연수
int fatsum(int n){
  if (n==1) return 1;
  if (n % 2 == 1) reutrn fatSum(n-1) + n;
  return 2 * fatSum(n/2) + (n/2)*(n/2);
}

병합 정렬(Merge sort)

주어진 수열을 크기 순서대로 정렬 알고리즘에서 병합정렬과 퀵정렬은 모두 분할 정복 패러다임을 기반으로 해서 만들어진 것이다.

병합 정렬 (Merge sort) 알고리즘

주어진 수열을 가운데에서 쪼개 비슷한 크기의 수열 두개로 만든 뒤 이들을 재귀 호출을 이용해 각각 정렬한 후 정렬된 배열을 하나로 합치는 방식.

특징

• 단점
  • 만약 레코드를 배열(Array)로 구성하면, 임시 배열이 필요하다.
    • 제자리 정렬(in-place sorting)이 아니다.
  • 레코드들의 크기가 큰 경우에는 이동 횟수가 많으므로 매우 큰 시간적 낭비를 초래한다.
• 장점
  • 안정적인 정렬 방법
    • 데이터의 분포에 영향을 덜 받는다. 즉, 입력 데이터가 무엇이든 간에 정렬되는 시간은 동일하다.
  • 만약 레코드를 연결 리스트(linked list)로 구성하면, 링크 인덱스만 변경되므로 데이터의 이동은 무시할 수 있을 정도로 작아진다.
    • 제자리 정렬 (in-place sorting)로 구현할 수 있다.
• 따라서 크기가 큰 레코드를 정렬할 경우에 연결 리스트를 사용한다면, 합병 정렬은 퀵정렬을 포함한 다른 어떤 정렬 방법보다 효율적이다.

과정 설명

1. 리스트의 길이가 0 또는 1이면 이미 정렬된 것으로 본다. 그렇지 않은 경우에는
2. 정렬되지 않은 리스트를 절반으로 잘라 비슷한 크기의 두 부분 리스트로 나눈다.
3. 각 부분 리스트를 재귀적으로 합병 정렬을 이용해 정렬한다.
4. 두 부분 리스트를 다시 하나의 정렬된 리스트로 합병한다.

코드예시

int sorted[100];

void mergesort(int list[], int left, int right){
  int mid;
  
  if (left < right){
    mid = (left + right) / 2; //중간 위치를 계산하여 리스트를 균등 분할 - Divide(분할)
    mergesort(list, left, mid);  //앞쪽 부분 리스트 정렬 - Conquer (정복)
    mergesort(list, mid+1, right); //뒤쪽 부분 리스트 정렬 - Conquer (정복)
    merge(list, left, mid, right); //정렬된 2개의 부분 배열을 합병하는 과정 - Combine (결합)
  }
}

void merge(int list[], int left, int mid, int right){
  int i, j, k, l;
  i = left; j = mid+1; k = left;

  //분할 정렬된 list 합병
  while(i <= mid && j <= right){
    if(list[i] <= list[j]){
      sorted[k] = list[i];
      k++; i++;
    {
    else{
      sorted[k] = list[j];
      k++; j++;
    }
  }

  //남아있는 값들을 일괄 복사
  if(i>mid){
    for(l=j; l<=right; l++){
      sorted[k] = list[l];
      k++;
    }
  }

  //남아있는 값들을 일괄 복사
  else{
    for(l=i; l<=mid; l++){
      sorted[k] = list[l];
      k++;
    }
  }

  //배열 sorted[]의 리스트를 배열 list[]로 재복사
  for(l=left; l<=right; l++){
    list[l] = sorted[l];
  }
}

병합 정렬의 시간 복잡도

• 분할 단계
  • 비교 연산과 이동 연산이 수행되지 않는다.
• 합병 단계
  • 비교 횟수
    • 순환 호출의 깊이 (합병 단계의 수)
      • 레코드의 개수 n이 2의 거듭제곱이라고 가정(n=2^k)했을 때, n=2^3인 경우, 2^3 -> 2^2 -> 2^1 -> 2^0 순으로 줄어들어 순환 호출의 깊이가 3임을 알 수 있다. 이것을 일반화하면 n=2^k의 경우, k임을 알 수 있다.
    • 각 합병 단계의 비교 연산
      • 최대 n번
    • 순환 호출의 깊이만큼의 합병 단계 x 각 합병 단계의 비교 연산 = n log2 n
  • 이동 횟수
    • 순환 호출의 깊이 (합병 단계의 수)
      • k = log2 n
    • 각 합병 단계의 이동 연산
      • 임시 배열에 복사했다가 다시 가져와야 되므로, 이동 연산은 총 부분 배열에 들어있는 요소의 개수가 n인 경우, 레코드의 이동이 2n번 발생한다.
    • 순환 호출의 깊이만큼 합병 단계 x 각 합병 단계의 이동 연산 = 2n * log2 n
• T(n) = n log2 n (비교) + 2n log2 n (이동) = 3n log2 n = O(n log2 n)

퀵 정렬 (Quick Sort)

배열을 단순하게 쪼개는 대신, 병합 과정이 필요 없도록 한쪽의 배열에 포함된 수가 다른 쪽에 배열의 수보다 항상 작도록 배열을 분할한다. 이를 위해 퀵정렬은 파티션(partition)이라고 부르는 단계를 도입하는데, 이는 배열에 있는 수 중 임의의 ‘기준 수(pivot)’를 지정한 후 기준보다 작거나 같은 숫자를 왼쪽, 더 큰 숫자를 오른쪽으로 보내는 과정.

• 퀵 정렬은 불안정 정렬에 속하며, 다른 원소와의 비교만으로 정렬을 수행하는 비교 정렬에 속한다.
• 분할 정복 알고리즘의 하나로, 평균적으로 매우 빠른 수행 속도를 자랑하는 정렬 방법이다. 병합 정렬과 달리 퀵정렬은 리스트를 비균등하게 분할한다.

과정 설명

1. 리스트 안에 있는 한 요소를 선택한다. 이렇게 고른 요소를 피벗(pivot) 이라고 한다.
2. 피벗을 기준으로 피벗보다 작은 요소들은 모두 피벗의 왼쪽으로 옮겨지고 피벗보다 큰 요소들은 모두 피벗의 오른쪽으로 옮겨진다. (피벗을 기준으로 왼쪽 : 피벗보다 작은 요소들, 오른쪽 : 피벗보다 큰 요소들)
3. 피벗을 제외한 왼쪽 리스트와 오른쪽 리스트를 다시 정렬한다.
   • 분할된 부분 리스트에 대하여 순환 호출을 이용하여 정렬을 반복한다.
   • 부분 리스트에서도 다시 피벗을 정하고 피벗을 기준으로 2개의 부분 리스트로 나누는 과정을 반복한다.
4. 부분 리스트들이 더이상 분할이 불가능할 때까지 반복한다.
   • 리스트의 크기가 더이상 0이나 1이 될 때 까지 반복한다.

특징

• 장점
  • 속도가 빠르다 (가장 빠르다)
  • 추가 메모리 공간을 필요로 하지 않는다.
    • 퀵 정렬은 O(log n)만큼의 메모리를 필요로 한다.
• 단점
  • 정렬된 리스트에 대해서는 퀵정렬의 불균형 분할에 의해 오히려 수행시간이 더 많이 걸린다.
• 퀵정렬의 불균형 분할을 방지하기 위하여 피벗을 선택할 때 더욱 리스트를 균등하게 분할할 수 있는 데이터를 선택한다.

퀵정렬의 시간 복잡도

• 평균 T(n) = O(n log2 n)
• 시간 복잡도가 O(n log2 n)를 가지는 다른 정렬 알고리즘과 비교했을 때도 가장 빠르다.
• 퀵정렬이 불필요한 데이터의 이동을 줄이고 먼 거리의 데이터를 교환할 뿐만 아니라, 한 번 결정된 피벗들이 추후 연산에서 제외되는 특성 때문에 가장 빠르다.

귀류법

“그래 네 말이 맞다고 치자. 근데도 문제가 생겼네. 따라서 니 말이 틀렸어” 식의 말이 귀류법이다.

수학과 논리학의 증명법 중 하나. 수학에서는 흔히 간접적 증명이라고도 부른다.

수학적 귀납법

1) P(0)가 성립한다.
2)  P(0),P(1),P(2),⋯,P(n)이 모두 성립하면, P(n + 1)

수학적 귀납법의 단계

1. 단계 나누기
   • 증명하고 싶은 사실을 여러 단계로 나눈다.
2. 첫 단계 증명
   • 첫 번째 단계에서 증명하고 싶은 내용이 성립함을 보인다.
3. 귀납 증명
   • 한 단계에서 증명하고 싶은 내용이 성립하면, 다음 단계에서도 성립함을 보인다.

반복문 불변식

반복문 불변식이란 반복문의 내용이 한 번 실행될 때 마다 중간 결과가 우리가 원하는 답으로 가는 길 위에 잘 있는지 명시하는 조건. 알고리즘의 정당성을 증명할 때 사용한다.

불변식을 이용한 반복문의 정당성 증명

1. 반복문 진입시에 불변식이 성립함을 보인다.
2. 반복문 내용이 불변식을 깨뜨리지 않음을 보인다. 다르게 말하면 반복문 내용이 시작할 때 불변식이 성립했다면 내용이 끝날 때도 불변식이 항상 성립함을 보인다.
3. 반복문 종료시에 불변식이 성립하면 항상 우리가 정답을 구했음을 보인다.

// (*) 불변식은 여기에서 성립해야 한다.
while (어떤 조건) {
  //반복문 내용의 시작
  ...
  //반복문 내용의 끝
  // (*) 불변식은 여기에서도 성립해야 한다.
}

• 2019 14