분할정복 알고리즘 (2)

분할정복 방법의 원리

순환적으로 문제를 푸는 하향식 접근 방법
- 주어진 문제의 입력을 더 이상 나눌 수 없을 때까지 두 개 이상의 작은 문제로 순환적으로 분할하고, 이렇게 분할된 작은 문제들을 각각 해결한 후 그 해를 결합하여 원래 문제의 해를 구하는 방식
- 분할 - 정복 - 결합
특징
- 분할된 문제는 원래 문제와 동일(입력 크기만 감소)하고 서로 독립적
적용 알고리즘
- 이진 탐색, 퀵 정렬, 합병 정렬, 선택 문제

합병 정렬

개념과 원리

배열을 동일한 크기의 두 개로 부분배열로 분할하고, 각각의 부분배열을 순환적으로 정렬한 후, 정렬된 두 부분배열을 합병하여 하나의 정렬된 배열을 만듦
분할: 입력 크기 n인 배열을 크기 n/2인 두 부분배열로 분할
정복: 각 부분배열에 대해서 합병 정렬을 순환적을 적용하여 두 부분배열을 정렬
결합: 정렬된 두 부분배열을 합병하여 하나의 정렬된 배열을 만듦

알고리즘 합병 정렬

MergeSort(A[], n) {
    if(n > 1) {
        Mid = n / 2;
        M[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) {
    i = j = k = 0;
    while(i < n && j < m) {
        if(B[i] <= C[j]) {
            A[k++] = B[i++];
        } else {
            A[k++] = C[j++];
        }
    }
    for(; i < n; i++) A[k++] = B[i];
    for(; j < m; j++) A[k++] = C[j]l
    return A[0, ..., n + m - 1];
}

성능 분석

합병 함수 Merge 수행 시간
- 두 부분배열 간의 비교 횟수 n/2 ~ n - 1 => 최악의 경우 Θ(n)
- 입력 데이터 개수만큼의 저장 장소가 추가로 필요
합병 정렬 MergeSort 수행 시간
- 크기 n/2인 두 번의 MergeSort 순환 호출 + 한 번의 합병 Merge
- T(n) = T(n/2) + T(n/2) + Θ(n), T(1) = 1
- T(n) = 2T(n/2) + Θ(n)
- T(n) = O(nlogn)

선택 문제

개념과 원리

선택 문제
- n개의 원소가 임의의 순서로 저장된 배열 A[0, ..., n - 1]에서 i번쨰로 작은 원소를 찾는 문제
  - i = 1 -> 최솟값
  - i = n/2 -> 중간값
  - i = n -> 최댓값
- 직관적인 방법
  - 오름차순으로 정렬한 후 i 번째 원소를 찾는 방법 -> O(nlogn)
  - 최솟값 찾는 과정을 i번 반복(i - 1 번째까지는 최솟값을 찾은 후 삭제) -> O(i * n)
- 최악 O(n^2), 평균 O(n) 알고리즘
- 최악 O(n), 평균 O(n) 알고리즘

최솟값 찾기

각 데이터를 하나씩 모두 비교하는 방법
- n개의 데이터를 대해서 최소한 (n-1)번의 비교가 필요 => O(n)

FindMinimum (A[], n) {
    mid = A[0];
    for(i = 1; i < n; i++) {
        if(A[i] < min) min = A[i];
    }
    return min;
}

최솟값과 최댓값 모두 찾기

최솟값 찾은 후 최댓값 찾는 방법(또는 최댓값 찾은 후 최솟값 찾기)
- n개의 데이터에서 최솟값을 찾는데 (n -1)번의 비교 + (n-1)개의 데이터에서 최댓값을 찾는데 (n-2)번의 비교 -> 2n -3 번의 비교
2n -3 번의 비교가 아닌 3/2n -2 번의 비교로 수행 가능
- 모든 원소를 두 개씩 짝을 이루어 동시에 최솟값/최댓값과 비교

FindMinMax(A[], n, min, max) {
    if(A[0] < A[1]) {
        min = A[0];
        max = A[1];
    } else {
        min = A[1];
        max = A[0];
    }
    for(i = 2; i < n; i += 2) {
        if(A[i] < A[i + 1]) {
            small = A[i];
            large = A[i + 1];
        } else {
            small = A[i + 1];
            large = A[i]l;
        }
        if(small < min) min = small;
        if(large > max) max = large;
    }
}

i번쨰로 작은 원소 찾기 최악 O(n^2), 평균 O(n)

개념의 원리
- 퀵 정렬의 분할 함수 Partition을 순환적으로 적용
  - i = j -> 피벗이 찾고자 하는 i번쨰 원소
  - i < j -> 왼쪽 부분배열에 대해 순환 적용
  - i > j -> 오른쪽 부분배열에 대해 순환 적용
분할: 피벗을 기준을 주어진 배열을 두 부분배열로 분할, i가 피벗의 인덱스와 같으면 피벗의 값을 반환하고 종료
정복: 인덱스 i가 포함된 부분배열에 대해서 선택 알고리즘을 순환적으로 적용
결합: 필요 없음

int Selection(A[], n, i) {
    Left = 0; Right = n - 1;
    p = Partition(A,n);
    if(i == p + 1) return A[p];
    else if (i < p + 1) Selection(A[Left, ... , p - 1], (p - 1) - Left + 1, i);
    else Selection(A[p+1, ..., Right], Right- (p+1) - i , i - p - 1);
}

성능 분석
- 최악의 경우 = 퀵 정렬의 최악의 경우
  - 분할 함수가 항상 하나의 부분배열만 생성하는 경우
  - 오름차순으로 정렬된 상태에서 i=n을 찾는 경우 -> 분할 함수 호출할 때마다 피벗의 인덱스는 1씩 증가 -> Partition을 O(n)번 호출 -> O(n^2)
  - 해결책 -> 항상 일정한 비율의 두 부분배열로 분할 -> 최악의 경우에도 O(n)
- 평균적인 경우
  - O(n)

i번쨰로 작은 원소 찾기 최악 O(n), 평균 O(n)

개념과 원리
- 특정한 성질을 만족하도록 피벗을 선택 -> 항상 일정한 비율의 두 부분배열로 분할
피벗 선택 방법
1. 크기 n인 배열의 원소를 5개씩 묶어 (n/5)개의 그룹을 형성
  - 5의 배수가 되지 않아 그룹을 형성하지 못한 채 남는 원소는 그대로 남겨 둠
2. 각 그룹에 대해서 중간값을 찾음
3. (n/5)개의 중간값들을 대상으로 다시 중간값을 찾음 -> 중간값들의 중간값 -> 피벗
부분배열로의 분할 비율
- S1과 S2에 각각 속하는 원소의 개수 = 3 x ((n/5)/2) -> 분할할 때 마다 탐색 과정에서 제외되는 데이터 개수

int Selection(A[],n,i) {
    단계1 if(n <= 5) 배열 A에서 i번쨰 원소를 찾아서 반환
          else 단계2 ~ 6을 진행
    단계2 A의 원소를 5개씩 묶어서 (n/5)개의 그룹을 생성
    단계3 각 그룹의 중간값을 구하고 이들을 모아 배열 M을 구성
    단계4 중간값들의 중간값을 계산하기 위해서 선택 함수를 순환 호출 p = Selection_n(M, (n/5), ((n/5)/2))
    단계5 p를 피벗으로 사용하여 A를 분할(피벗의 인덱스 = j라고 가정)
    단계6 if(i == j + 1) return A[j]
          else if(i < j + 1) Selection_n(A[0, ..., j - 1], j,i)를 순환 호출
          else Selection_n(A[j+1, ..., n - 1], n- j - 1, i - j - 1)를 순환 호출
}

분할정복 알고리즘 (1)

devground-junior-2019 정리