공부중 .../알고리즘

[알고리즘] 분할정복 알고리즘(합병 정렬, 선택 문제)

Chelsey 2022. 5. 11. 16:51
728x90

합병 정렬

1. 데이터를 나눌 수 없을 때 까지 나눠준다.

2. 두 가지의 원소를 비교하여 정렬한 후 합병해준다.

 

각 분할된 배열을 어떻게 합병하는가?

각 분할된 배열의 가장 첫번째 원소를 각자 비교하고 새로운 배열에 하나씩 넣어준다.

합병 함수 Merge()

Merge(B[], C[], n, m). //A[n+m-1] <- B[n]+C[m]
{
i=j=k=0;
while(i<n && j<m)
	if(B[i]<=C[j]
    	A[k++]=B[j++];
    else
    	A[k++]=C[j++];
}
for(;j<n;i++) A[k++]=B[i]; //남은 B[]의 데이터를 A[]에
for(;j<m; j++) A[k++]=C[j]; //남은 C[]의 데이터를 A[]에
return A[0..n+m-1]
}

입력 데이터 개수만큼 추가 저장 장소가 필요하다. - 제자리 정렬 알고리즘이 아니므로

수행 시간 -> 정렬하는데 걸리는 시간 :T(n) = 2T(n/2)+O(n)=O(nlogn)

 

비순환적 합병 정렬 -> 합병만 반복

 

 

선택 문제

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

 

직관적인 방법

오름차순으로 정렬한 후 i번째 원소를 찾는 방법 -> O(nlongn) 의 수행시간.

최솟값을 찾는 과정을 i번 반복(i-1번째까지는 최솟값을 찾은 후 삭제) -> O(in) :O(n)을 i번 반복, 만약 n번이면 O(n^2)

알고리즘 1. -> 최악 O(n^2) , 평균 O(n) 알고리즘

알고리즘 2. -> 최악 O(n), 평균 O(n) 알고리즘

 

최솟값을 어떻게 찾는가?

각 데이터를 하나씩 모두 비교하는 방법

    n개의 데이터에 대해서 적어도 (n-1)번의 비교가 필요 -> O(n)

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

최솟값과 최댓값 모두 찾기

방법 1 : 최솟값 찾은 후 최댓값 찾기 -> (n-1)개 비교 후 (n-2)개 비교

(n-1)+(n-2)=> 2n-3번의 비교 O(n)

방법 2 : 모든 원소를 짝을 지어 비교

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];
        }
        if(small<min) min=small;
        if(large>max) max=large;
    }
}

 

알고리즘1. 퀵정렬의 Partition() 이용

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

분할 : 피벗을 기준으로 주어진 배열을 두 부분배열로 분할하고 i가 피벗의 인덱스 p와 같으면 피벗의 값을 반환하고 종료

정복 : 인덱스 i가 포함된 부분배열에 대해서 알고리즘을 순환적으로 호출하여 적용

결합 : 필요 없음

int Selection(A[], n, i) { // 1<=i<=n 
	Left=0;
    Right=n-1;
    p=Partition(A,n); //0<=p<=n-1
    if(i==p+1) return A[p]
    else if(i<p+1)Selection(A[Left..p-1]-Left+1, i);
    	else Selection(A[p+1..Right], Right-(p+1)+1, i-p-1);  //Right는 i번째 인덱스값이 바뀌게 된다.

과정

35 45 15 40 80 90 20 60 10 75 의 6번째로 제일 큰 값을 찾는다 함은

피벗: 35, 을 이용한 분할 

20 10 15 35(pivot이었던 것) 80 90 40 60 45 75

pivot의 인덱스는 3이므로 4번째 원소이다. 6번째와 같지 않고 보다 작은 위치이므로 오른쪽 배열을 이용한다.

Selection(A[],6,2) 오른쪽 배열은 6개로 데이터 갯수가 줄어든다. 4번째 이후 6번째를 찾아야하므로 i값으로 2를 넣게 된다.

오른쪽 배열의 80 90 40 60 45 75에서 80이 pivot이 된다.

45 75 40 60 80(pivot) 90 에서 80은 5번째이고 아까 전체 배열까지 본다면 9번째 배열이다. 근데 우리는 i번째, 2번째 원소를 찾고 싶으므로 다시 pivot을 기준으로 왼쪽부분 배열에서 다시 Selection(A[], 4, 2)를 진행한다.

40 45(pivot) 75 60 에서 pivot이 2번째 이므로 찾고있는 i값과 일치하므로 값을 return하게 된다.

 

성능 분석

최악의 경우 = 퀵 정렬의 최악의 경우와 같다.

  • 분할 함수 Partition()이 항상 하나의 부분배열만 생성하는 경우(pivot이 늘 최솟값이거나 최댓값인 경우)
  • 오름차순을 정렬된 상태에서 최댓값(i=n)을 찾는 경우 => 성능이 O(n^2)이 된다.

해결방법 : 항상 일정한 비율의 두 부분배열로 분할

 

알고리즘 2. 중앙값의 중앙값 이용

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

항상 일정한 비율의 두 부분배열로 분할되도록! 특정 성질을 만족하는 값을 Pivot을 선택

Pivot 선택 방법

  1. 크기 n인 배열의 원소를 5개씩 묶어서 n/5개(바닥함수)의 그룹을 만듦 (5의 배수가 되지 않아 그룹을 형성하지 못한 채 남는 원소는 그대로 남겨-버림-둠)
  2. 각 그룹에 대해서 중간값을 찾음
  3. 2에서 알아낸 중간값(n/5개(바닥함수)의 중간값)을 대상으로 다시 중간값을 찾음(중간값들의 중간값) -> 피벗 선정!

A[]={9 6 35 39 15 24 70 95 50 1 97 84 77 28 10 22 27 11 31 62 54 81 5 34 4 89 60 29 2 75 18 36 80 7 53 25 66 43}

9
6
35
39
15		 24
70
95
50
1		 97
84
77
28
10		 22
27
11
31
62		 54
81
5
34
4		 89
60
29
2
75		 18
36
80
7
53

25 66 43 (남은 원소는 버림)

=> 그룹별 정렬

6
9
15
35
39		 1
24
50
70
95		 10
28
77
84
97		 11
22
27
31
62		 4
5
34
54
81		 2
29
60
75
89		 7
18
36
53
80

중간값 뽑기

15 27 34 36 50 60 77
그룹1 그룹2 그룹3 그룹4 그룹5 그룹6 그룹7

36이 중앙 값 => pivot = 36

이처럼 중앙값의 중앙값을 이요하게 되면 부분배열을 훨씬 잘 나눌 수 있다.

좋은 pivot기준으로 부분배열을 나눈 후 필요한 부분배열을 계속해서 호출해나가며 원하는 값을 찾을 수 있다.

 

728x90
저작자표시 비영리 변경금지