2018/05/22 - [방송통신대학교/컴퓨터과학과 [3학년 1학기]] - [알고리즘] 3강 분할정복 알고리즘 - 1

2018/05/22 - [방송통신대학교/컴퓨터과학과 [3학년 1학기]] - [알고리즘] 2강 알고리즘 소개

2018/03/19 - [방송통신대학교/컴퓨터과학과 [3학년 1학기]] - [알고리즘] 1강 알고리즘 소개

1. [복습] 분할정복 방법의 원리

순환적으로 문제를 푸는 하향식 접근 방법
주어진 문제의 입력을 더 이상 나눌 수 없을 때까지 두 개 이상의 작은 문제로 순환적으로 분할하고, 이렇게 분할된 작은 문제들을 각각 해결한 후 그 해를 결합하여 원래 문제의 해를 구하는 방식

'분할' - '정복' - 결합

특징
- 분할된 문제는 원래 문제와 동일(입력 크기만 감소) 하고 서로 독립적

적용 알고리즘
- 이진 탐색, 퀵 정렬, 합병 정렬, 선택 문제

 

2. 합병 정렬

분할 정복 방법을 가장 잘 표현하고 있는 알고리즘이다.

배열을 동일한 크기의 두 개의 부분배열로 분할하고,
각각의 부분배열을 순환적으로 정렬한 후, (정복)
정렬된 두 부분배열을 합병하여 하나의 정렬된 배열을 만듦.

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

합병 정렬에서 분할은 신경쓸 필요없다. 합병이 중요한 부분이다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
MergeSort(A[], n){
    if(n > 1){
        Mid = n/2;
        B[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<&& 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];
    return A[0..n+m-1];
}
cs

 

성능 분석

두 부분배열 간의 비교 횟수 n/2 ~ ( n/2 + n/2 -1 = n - 1 )
최악의경우: Θ(n)
입력 데이터 개수만큼의 저장 장소가 추가로 필요하다.

합병 정렬 MergeSort() 수행시간
- 크기 n/2 인 두 번의 MergeSort() 순환 호출 + 한 번의 합병 Merge()
T(n) = T(n/2) + T(n/2) + Θ(n) (n>1)
T(1) = 1
                  ▼▼▼
         T(n) = 2T(n/2) + Θ(n)
                  ▼▼▼
             T(n) = O(nlogn)

퀵 정렬과 동일한 수행시간을 갖는다.

 

3. 선택 문제

선택문제란?
n개의 원소가 임의의 순서로 저장된 배열 A[0..n-1]에서 번째로 작은 원소를 찾는 문제

i = 1 > 최솟값
i = n/2 > 중간값
i = n > 최댓값

직관적인 방법
- 오름차순으로 정렬한 후 i번째 원소를 찾는 방법 > O(nlogn)
- 최솟값 찾는 과정을 i번 반복((i-1)번째까지는 최솟값을 찾은 후 삭제) > O(in)

최악 O(n2제곱), 평균 O(n) 알고리즘
최악 O(n), 평균 O(n) 알고리즘

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

3-2) 최솟값과 최댓값 모두 찾기

최솟값 찾은 후 최댓값 찾는 방법(또는 최댓값 찾은 후 최소값 찾기)
n개의 데이터에서 최솟값을 찾는데 (n-1)번의 비교
 + (n-1)개의 데이터에서 최댓값을 찾는데 (n-2)번의 비교
==> 2n - 3 번의 비교

2n-3번의 비교가 아닌 (3/2)n -2번의 비교로 수행 가능
모든 원소를 두 개씩 짝을 이루어 동시에 최솟값/최댓값과 비교

1
2
3
4
5
6
7
8
9
10
11
12
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++){
        if(A[i] < A[i+1] { small = A[i]; large = A[i+1]; }
        else { small = A[i+1]; large = A[i]; }
        
        if ( small < min ) min = small;
        if ( large > max ) max = large;
    }
}
cs

3-3) i번째로 작은 원소 찾기_ 최악 O(n2제곱), 평균 O(n)

개념과 원리
퀵 정렬의 분할 함수 Partition()을 순환적으로 적용한다.

분할: 피벗을 기준으로 주어진 배열을 두 부분배열로 분할, i가 피벗의 인덱스와 같으면 피벗의 값을 반환하고 종료
정복: 인덱스 i가 포함된 부분배열에 대해서 선택 알고리즘을 순환적으로 적용
결합: 필요없음

1
2
3
4
5
6
7
8
9
10
11
12
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)-1, i-p-1);
}
cs

성능 분석

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

평균적인 경우 O(n)

 

3-4) i번째로 작은 원소 찾기_최악 O(n), 평균 O(n)

개념과 원리
특정한 성질을 만족하도록 피벗을 선택
> 항상 일정한 비율의 두 부분배열로 분할

피벗선택방법
① 크기 n인 배열의 원소를 5개씩 묶어 n/5개의 그룹 형성
- 5의 배수가 되지 않아 그룹을 생성하지 못한 채 남는 원소는 그대로 남겨 둔다.
② 각 그룹에 대해서 중간값을 찾음
③ n/5 개의 중간값들을 대상으로 다시 중간값을 찾음 > "중간값들의 중간값" => "피벗"