9. 최대, 최소 찾기 (순차, 토너먼트, 선택 알고리즘)

 

순차 탐색

주어진 값들에서 최대, 최소를 찾는 방법은 다양하다. 아마 우리가 자주 사용하는 방법은 데이터를 첫 번째 부터 읽어서, 현재까지 저장해놓은 최대값과 계속 비교해 나아가는 방법일 것이다.

//c++
int findMax(int data[], int length){
    int max = INT_MIN; //<limit.h> 사용
    //int min = INT_MAX;
    int i;
	for(i = 0; i< length) ; i++){
        if(max < data[i]) max = data[i];
        //if(min > data[i]) min = data[i];
    }
    return max // or min
}

이러한 방법을 사용하였을 때, 우리는 필연적으로 $n-1$ 번의 비교를 해야한다.
더 효율적인 방법은 없을까? 우리가 실생활에서 자주 사용하는 방법을 생각해보자.
많은 토너먼트 대회에서 사용하는 방법을 보자, 각각의 데이터들을 두명씩 대전을 붙여, 최후의 1인이 남을 때 까지 반복하는 것이다.

 

토너먼트 트리

//c++
int findMax(int data[], int length) {

    queue<int> q;

    for (int i = 0; i < length; i++) {
        cout << data[i]+ "\n";
        q.push(data[i]);
    }
    int round;

    while (!q.empty()) {
        int round = q.size();
        int winner;
        int loser;

        if (round == 1) break;
		//queue에서 한 쌍씩 대전시키는 방법
        for (int i = 0; i < round/2; i++) {
            winner = q.front();
            q.pop();
            loser = q.front();
            q.pop();

            if (winner < loser) winner = loser;
            q.push(winner);
        }
    }
    return q.front();
}

이런 방법을 사용하면, $\frac{n}{2} + \frac{n}{4} + \frac{n}{8}..... = n-1$ 결국 하나씩 비교하는 방법과 동일하다. 하지만, 최대- 최소를 동시에 찾는다고 생각해보자. 위 코드에선 큐를 두 개로 나누어, 첫 번째 비교 이후 Winner들만 따로 토너먼트, Loser들만 따로 토너먼트를 진행한다면,

첫 번째 $(\frac{n}{2})$ + Winner $(\frac{n}{2}-1)$ + Loser $(\frac{n}{2}-1)$ = $(\frac{3n}{2}-2)$로, 순차탐색 시 최대, 최소를 찾는 $2n-2$보다 더 효율적임을 알 수 있다.
또한, 토너먼트 방법으로는 두번째로 큰 값을 찾기도 용이하다.

최종적으로 이긴 사람과 대결한 애들 중 최대값을 구하면 되므로 $lg(n) -1$번의 비교만 추가적으로 하면 된다.
순차탐색시 $n-2$번의 비교보다 효율적임을 알 수 있다.

 

선택 알고리즘

여기서 나아가서, 크기순으로 k번째를 찾는 문제를 보자. Selection Problem이라고도 하는 선택 문제를 해결하기 위해선 우선 간단하게 두 가지 방법을 생각해볼 수 있다.
단순하게 전부다 정렬한 다음 K번째를 찾는 경우는 효율적인 정렬 알고리즘을 사용했을 때 $O(nlgn)$번의 시간복잡도가 걸림을 알 수 있다.
위처럼 순차 탐색으로 1번째, 2번째씩 소거해가면서 한다면 $n-1 + n-2 + ... n- k = nk-\frac{k(k+1)}{2}$번이 걸린다.
이러한 방법보다 효율적인 알고리즘을 호어가 만들어 내었다. 퀵 소트를 만들어 낸 호어는, 퀵 소트와 비슷하게 피봇 값을 가지고 그룹을 분류함으로써 더 빠르게 k번째 크기의 데이터를 얻어내는 방법을 고안하였다. 그 방법을 이제부터 설명하겠다.

1. 데이터의 집합을 S라 할때 5묶음씩 그룹을 만들고, 가운데 값을 피봇으로 할때, 위에는 피봇보다 크게, 아래는 피봇보다 작게 나눈다. (a+n, a+m a a-k, a-j)

2. 이 피봇들 중에서의 가운데 값을 구한다. (Median of Median = $m^*$)

3. 이렇게 정렬된 그룹에서 영역을 아래와 같이 나눌 때, S1 = C $ \cup$ (A $\cup$ D 에서 $m^*$ 보다 작은 값) S2 = B $ \cup$ (A $\cup$ D 에서 $m^*$ 보다 큰 값) 의 두 집합을 구한다.

4. 이제 분할 정복을 사용해서, S1+1 = K면 $m^*$, S1 $\geq$ K 면 S1에서K찾기, 아니면 S2에서 K-S1-1 찾기를 진행하면 된다.

위와 같은 방법을 사용할 때의 시간 복잡도를 생각해본다면

1. 5개의 키 중 가운데 값을 찾아내는 방법은 6($\frac{n}{5}$)번
2. 가운데 값들중에서 가운데 값을 찾아내는 방법은 W$(\frac{n}{5})$번
3. S1과 S2로 나누는 방법 (A U D중 큰 값 작은 값 순차적으로 비교하는 법) $4r$
4. 재귀적으로 S1 or S2를 다시 하는법 W($7r+2$)

-> 단순화 시킨다면(n = 5(2r+1)), 1.2n + W(0.2n) + 0.4n + W(0.7n) = 1.6n + W(0.9n) .... -> 16n 정도임을 알 수 있다.

만약 n과 k가 엄청 큰 수 일 경우에, Linear-Time만에 할 수 있는 것이다.
위에서 1번 5개의 키 중 가운데 값을 6번만에 찾아내는 방법은 아래사진과 같다