[알고리즘] The Selection Problem - 일반적인 경우

일반적으로 Selection Problem은 정렬되지 않은 배열에서 K번째로 큰 값 혹은 작은 값을 구하는 문제이다. K = 1이라면, 그 배열에서 가장 큰 값 혹은 가장 작은 값을 구하고 K = 2라면 2번째로 큰 값 혹은 2번째로 작은 값을 찾으면 된다.

• 입력 : n개의 값과 K(1<=K<=n)
• 출력 : K번째로 크거나 작은 값
• 목표 : 비교 횟수를 최적화하는 것

 

최댓값 찾기(K = n)

K = n일 때, S 배열에서 가장 큰 값을 찾아야 한다. S 배열의 수가 n일 때, n-1번 비교해야 한다. n-1 번이면 항상 최댓값을 찾을 수 있기 때문에 상한(Upper Bound)이라고 한다. n-1 번이면 최솟값을 찾기 위한 하한(Lower Bound)이다.

 

 

최솟값과 최댓값을 동시에 찾기(K = 1, K = n)

최댓값과 최솟값을 동시에 찾으려면, K = 1, K = n일 때, S 배열에서 최댓값을 찾은 다음, 최댓값을 제외한 나머지에서 최솟값을 찾아야 한다. 만약에 S 배열에 n개가 존재한다고 하면, 최댓값 1개를 찾을려면 총 n-1번 비교한다. 그리고 배열에서 최댓값을 제외하고 남은 n-1개에서 최솟값 1개를 찾아야 하므로, 총 n-2번 비교해야 한다. 따라서 총 비교 횟수의 상한은 (2n-3)번이다. 

void find_both(int n, vector<int> S, int& small, int& large) {
	int i;
    
    	small = S[1];
    	large = S[1];
   	for (i = 2; i <= n; i++) {
    		if (S[i] < small)
        		small = S[i]
       	 	else if (S[i] > large)
        		large = S[i];
    	}
}

 

우리가 이 문제를 푸는 목표가 상한을 최대한 줄이는 것이기 때문에, 최적화하는 방법을 떠올려야 한다.

 

값을 짝지어서 최솟값과 최댓값을 구하는 방법도 있다. 모든 값에 짝을 만들어서 그 짝 중에서 작은 키를 찾는 것이다.

먼저, n이 짝수라고 가정할 때, 모든 짝을 비교하는 횟수가 (n/2)번이다. 그리고 나온 작은 값들 중에서도 가장 작은 값을 찾는 데 (n/2)번, 큰 값들 중에서도 가장 큰 값을 찾는데 (n/2)번 비교해면 되기 때문에 총 3n/2번 비교만으로 최댓값과 최솟값을 동시에 찾을 수 있다.

void find_both2(int n, vector<int> S, int& small, int& large) {
	int i;
    
    if (S[1] < S[2]) {
    	small = S[1];
    	large = S[2];
    } 
    else {
    	small = S[2];
    	large = S[1];
    }
    
    for (i = 3; i <= n-1; i += 2) {
    	if (S[i] < S[i+1]) {
        	if (S[i] < small) small = S[i];
            	if (S[i+1] > large) large = S[i+1];
        }
        else {
        	if (S[i+1] < small) small = S[i+1];
            	if (S[i] > large) large = S[i];
    	}      	
  	}
}

 

정리하면, n이 짝수일 때 3n/2 - 2번, n이 홀수이면 3n/2 - 3/2번 비교하면 된다.

 

 

 

두 번째로 큰 값 찾기(K = 2)

가장 큰 값을 찾으려면, n개의 배열에서 (n-1)번 비교할 수 있었다. 그러면 두 번째로 큰 값은 남은 n-1 개 중에서 n-2번 비교하면 된다. 총 2n-3번 비교를 통해서 두 번째로 큰 값을 찾을 수 있다고 결론이 난다.

 

조금 더 최적화하기 위해서 Tournament 방법을 적용해서 찾아볼 것이다. 아래 그림과 같이 S = [12 ,10, 5, 15, 18, 11, 4, 16]이 주어졌을 때, 각각 짝을 지어서 최댓값을 찾을 수 있다. 우리가 잘 생각해보면, 최댓값을 결정하기 위해서 마지막으로 비교한 그 수가 두 번째로 클 수도 있다. 그러나, 처음부터 최댓값과 비교해서 Loser 배열로 들어간 수도 있을 것이다.

따라서, 최댓값과 비교한 수를 모두 linked list로 연결해서 비교하면 두 번째로 큰 값을 구할 수 있다. 따라서 최댓값을 찾기 위해서 (n-1)번 비교하고, 최댓값과 비교한 값들의 비교 횟수는 tree의 depth와 같다. 예를 들어서, n = 8일 때 depth는 log8 = 3이다. 그래서 11의 depth는 2, 16의 depth는 1, 15의 depth는 0이 되어 비교 횟수는 총 (n-1) + ceil(log2(n)) - 1 = n - ceil(log2(n)) - 2 번이다. 상한과 하한이 모두 동일하기 때문에 더 이상 비교 횟수를 줄일 수 는 없다.

---

참고

https://ssocoit.tistory.com/99