선택 알고리즘

n개의 원소로 이루어진 집합에서 최소/최대 원소를 찾기 위해서는 선형시간 O(n)이 필요하다

적어도 모든원소를 한번씩은 봐야하는 것이다.

 

그렇다면 최소(혹은 최대) 원소가 아닌 2번째로 작은(혹은 큰) 원소를 찾기 위해서는

최소(최대)원소를 구하는 기본 과정에 2번째로 작은 원소를 저장하고 이를 갱신하는 과정을 추가 하면 된다.

 

위 과정은 최소/최대 원소를 구하는 과정보다 시간이 더 걸리긴 하지만 마찬가지로 선형시간내에 구할 수 있다.

 

하지만 n개의 원소로 이루어진 집합에서 중앙값을 구한다고 하면 위 과정에서 n/2번째 원소까지를 저장하며 갱신해야 하므로 이런 경우에는 O(n^2)의 시간이 걸리게 된다.

 

이런 경우에는 위와같은 방법을 사용하기보단 O(nlogn)시간이 소요되는 정렬 알고리즘을 통해 배열을 정렬하고

배열의 n/2 인덱스에 해당하는 원소를 선택하는 방법을 쉽게 떠올릴 것이다.

 

하지만 O(n)시간만에 n개의 원소로 이루어진 집합에서 i 번째 작은 원소를 선택하는 방법이 있다.

 

일단 아래 코드를 보자.

평균 선형 시간 선택 알고리즘

#include <stdio.h>

int partition(int* A, int p, int r){
	//퀵정렬의 그것과 같음
	int x = A[r];
    int i = p-1;
    
    int temp;
    for(int j = p; j < r; j++){
    	if( A[j] <= x ){
    		temp = A[j];
            A[j] = A[++i];
            A[i] = temp;
		} 
	}
    
    temp = A[r];
    A[r] = A[i + 1];
    A[i + 1] = temp;
    
    printf("i is : %d\n", i+1);
    return i+1;
}

int select(int* A, int p, int r, int i){
	if(p == r){
		return A[p];
		//찾으려는 그룹의 크기가 1 -> 더 볼것 없이 종료 
	}
	
	int q = partition(A, p, r);
	//기준 원소를 정해서 왼쪽,오른쪽 그룹으로 분할 
	int k = q - p + 1;
	//기준원소가 전체에서 몇번째로 작은 원소인지 k값을 통해 알게 되었다. 
	
	//기준원소 보다 작은 원소를 찾으려면 왼쪽그룹에서,
	//기준원소 보다 큰 원소를 찾으려면 오른쪽 그룹에서,
	//기준원소가 내가 찾으려던 i번째로 작은 원소라면 종료
	if(i<k){
		return select(A, p, q-1, i);
		//왼쪽 그룹에서 탐색 
	}else if(i == k){
		return A[q];
	}else{
		return select(A, q+1, r, i-k);
		//오른쪽 그룹에서 탐색 
	}
}

int main(void){
	int A[10] = {31, 8, 48, 73, 11, 3, 20, 29, 65, 15};
	int third = select(A, 0, 9, 3);
	printf("3번째: %d", third);
	return 0;
}

위 코드를 보면 퀵정렬을 하는 방법과 상당부분 공통점이 있는데

퀵정렬과 선택에는 목적의 차이점이 있다.

 

퀵정렬은 모든 원소를 정렬하는것이 목적이고,

i번째 작은 원소 선택은 선택만 하면 끝이다

 

O(nlogn) 시간의 정렬 알고리즘을 사용해 정렬 후 i번째 인덱스 원소를 가져오는 방법에서

우선 정렬을 하는것은 구현을 간단하게 하기 위함이고

궁극적으로 이 문제에선 원소를 가져오기만 하면 될 뿐이므로, 배열을 정렬시켜놓는게 목적이 아니다.

 

int A[10] = {31, 8, 48, 73, 11, 3, 20, 29, 65, 15};
int third = select(A, 0, 9, 3);

select(A, 0, 9, 3) 함수를 호출하면 A배열의 0~9 구간에서 3번째로 작은 원소찾기를 시작한다.

 

select(A, 0, 9, 3) 함수가 호출되면 퀵정렬과 마찬가지로 partition(A, 0, 9)를 호출해서

기준원소(맨 오른쪽 원소)를 통해 왼쪽 그룹과 오른쪽 그룹으로 나누게 된다.

 

그러면 기준원소 15는 전체에서 4번째로 작은 원소가 된다.

 

우리가 찾고자 하는 원소는 3번째로 작은 원소이므로 우리가 찾고자 하는 원소는 왼쪽 그룹에 있음이 확실하고

더이상 오른쪽 그룹은 볼 필요가 없다.

 

따라서 위 알고리즘은 기준원소를 통해 그룹을 분할을 하고, 두 그룹중 하나만을 선택해서 문제의 크기를 적절히 줄여나가 O(n)시간만에 i번째 원소를 선택할 수 있다.

 

최악의 경우에는?

만약에 분할 할 때마다 그룹이 항상 1 : n-1 개의 원소로 분할 되고,

심지어 선택하는 그룹이 항상 n-1개 원소를 가진 그룹이면 어떨까?

 

이런 상황에서는 그룹을 나누고 선택해서 문제의 크기를 획기적으로 줄여나갔다고 할 수 있을까?

 

이러한 최악의 경우에는 이 알고리즘도 Θ(n^2)의 시간이 걸리게 될 것이다.

이것이 위 알고리즘이 "평균"선형 시간 선택 알고리즘인 이유인듯 하다.

 

최악의 경우에도 선형 시간을 보장하는 선택 알고리즘

위에서 그룹이 항상 1 : n-1 개의 원소로 분할 되고

계속해서 찾고자 하는 원소가 큰 그룹에 속하는 일이 반복되면  Θ(n^2) 시간이 걸린다고 했다

 

그렇다면 계속에서 일정 비율 이상은 보장받도록 하면 어떨까?

아무리 나쁜 경우여도 "이 비율" 이상은 유지되도록 말이다.

 

계속해서 1:9 비율로 분할되는 경우를 예로 들어보자.

 

T(n) = T(9n/10) + Θ(n)

...

T(n) = Θ(n)

 

따라서 앞서 소개한 알고리즘의 기본 골격은 유지하되, 분할 할 때 일정 비율이상은 보장해서 성능 저하를 막아보자.

 

linearSelect (A, p, r, i)
▷ 배열 A[p ... r]에서  i번째 작은 원소를 찾는다 
{ 
	① 원소의 총 수가 5개 이하이면 원하는 원소를 찾고 알고리즘을 끝낸다. 
	② 전체 원소들을 5개씩의 원소를 가진           개의 그룹으로 나눈다. 
	    (원소의 총수가 5의 배수가 아니면 이중 한 그룹은 5개 미만이 된다.) 
	③ 각 그룹에서 중앙값을 (원소가 5개이면 3번째 원소) 찾는다. 
	     이렇게 찾은 중앙값들을  m1, m2, …, m     이라 하자. 
	④ m1, m2, …, m     들의 중앙값 M을 재귀적으로 구한다. 원소의 총수가          
	    홀수면 중앙값이 하나이므로 문제가 없고, 원소의 총수가 짝수일 
	    경우는 두 중앙값 중 아무거나 임의로 선택한다.	▷ call linearSelect( ) 
	⑤ M을 기준원소로 삼아 전체 원소를 분할한다(M보다 작거나 같은 것은 
	     M의 왼쪽에, M보다 큰 것은 M의 오른쪽에 오도록). 
	⑥ 분할된 두 그룹 중 적합한 쪽을 선택하여 단계 ①~⑥을 재귀적으로 
	     반복한다.					▷ call linearSelect( ) 
} 

 

위 알고리즘에서 원소들을 그룹으로 묶은것을 그림으로 나타낸 모습

그룹 K를 보자. Mk는 그룹 K에서 중앙값이니 Klarge의 원소들은 Mk보다 크다.

 

M < Mk < Klarge 이므로

 

그림에서 보듯 원소M 기준 ~ 오른쪽 하단 까지의 원소들은 M보다 항상 큰 원소들이다.

 

Ksmall의 경우를 보면 Ksmall 은 Mk보다 작은건 확실한데,

M보다 큰지 작은지는 알 수 없다. 왼쪽 아래에 있는 원소들도 마찬가지다.

 

이런 알 수 없는 원소들도 있지만

 

왼쪽 상단 ~ 오른쪽 하단의 색칠된

M보다 큼/ 작음이 확실한 원소들의 존재로 인해

분할 할 때 양쪽 그룹의 비율이 일정 수준 이상으로 보장된다.

 

 

오버헤드를 포함해도 Θ(n) 시간이 걸림을 증명할 수 있다.