[c++] 알고리즘 개념공부 :: 최대 최소 찾기 (토너먼트 트리, selection 알고리즘)

최대 최소 찾기

선택 문제

주어진 리스트의 최대, 최소 값을 찾거나 n번째 큰 값, n번째 작은 값을 찾는 과정도 프로그램에서 많이 등장한다. 이렇게 n개의 숫자들 중 k번째로 작은(또는 큰) 값을 찾는 문제를 'Selection problem' 즉, 선택 문제 라고 한다.

 

최대 최소 찾기

선택 문제에서 가장 쉬운 문제가 최대 / 최소를 찾는 문제이다. 주어진 리스트의 최대값을 찾기 위해서는 어떤 방법을 사용하면 될까?

 

정렬

먼저, 이전에 배웠던 정렬을 이용할 수 있다. 정렬 후 리스트의 마지막 요소를 가져오면 최대값을 알 수 있기 때문이다. 하지만 중간 요소들의 정렬은 최대값을 찾는데에 불필요한 과정이다. 따라서 정렬을 이용하면 정렬의 최소 시간복잡도인 O(nlgn)로 문제를 해결할 수 있다.

 

min/max

두번째는 선택 정렬에서 반복문 한 번에 사용했던 방식처럼, 요소들을 2개씩 묶어 비교함으로써 최대값을 찾을 수 있다. 이 방법은 시간복잡도가 O(n)이지만 최대 / 최소 값을 동시에 찾을 수 없다는 단점이 있다.

int max = 0;
for(int i=0; i<length; i++){
    if(arr[i]>max)
        max = arr[i];
}

가장 기본적으로 최대 / 최소를 찾는 방법

 

선택 알고리즘

선택 문제를 푸는 것에 최적화된 선택 알고리즘(Selection algorithm)으로 문제를 해결하면 O(n)의 시간복잡도로 최대 / 최소 값을 한번에 확인할 수 있다. 자세히 살펴보자.

 

먼저 주어진 리스트의 요소를 2개씩 묶어서 묶음 별 최대 / 최소를 구한다. 이 과정은 n/2의 시간복잡도를 가진다.

 

묶음 별 최대 값들 중 최대를 구하면 리스트의 최대값을 구할 수 있고, 묶음 별 최소 값들 중 최소를 구하면 리스트의 최소값을 구할 수 있다. 이 과정은 n/2-1 의 시간복잡도를 가진다. 따라서 전체 시간복잡도는 O(n)이며 최대/최소값을 동시에 구할 수 있다.

 

n번째 큰 값 찾기

이제 가장 쉬운 선택 문제인 '최대 최소 문제'를 벗어나 n번째 큰 값을 찾아보자. n이 몇이냐에 따라서 최적의 방법은 달라질 수 있다. 여기서는 2번째 큰 값을 찾는 것으로 문제를 해결해보겠다.

최대/최소 문제에서와 같이 정렬을 이용하여 index로 접근하여도 되지만 역시나 시간복잡도가 문제이다.

최대/최소값을 찾아 하나씩 제거해나가는 방법도 시간복잡도가 크다. 처음 최대값을 찾을 때 n-1, 최대값을 제외한 후 최대값을 다시 찾을 때 n-2 이므로 총 2n-3의 시간복잡도가 든다.

 

토너먼트 트리

이번에는 토너먼트 트리를 이용해서 문제를 해결해보자.

토너먼트 트리는 위의 그림처럼, 리프노드부터 두개씩 비교해서 더 큰 요소가 위로 올라가는 구조이다.

 

 이는 위의 최대/최소 찾기에서 살펴보았던 두개씩 묶는 구조와 비슷하지만 조금 다르다. 위의 그림을 비교해보면 차이점을 알 수 있다.

 토너먼트 트리는 각 묶음의 최대값들을 다시금 묶는 과정을 반복한다. 한번의 비교마다 한 명의 winner와 한 명의 loser가 나오게 되는데, 이를 이용하면 n번째 큰 값을 찾을 수 있다.

 2번째로 큰 값을 찾기로 했으니, 그 후보를 살펴보자. 일단 3은 가장 큰 값이므로 아니고 3과 대결 시 졌던 값들 중에 하나가 2번째로 큰 값일 것이다.

 

 

 따라서 위의 트리에서 1,4,7이 후보가 된다. 2번째로 큰 값은 이 중에 가장 큰 값이므로 min/max 방법으로 가장 큰 값을 찾아내면 된다. 이 방법은 최대값을 찾는데에 n-1, 후보들 중 최대 값을 찾는데 lgn-1 이 드므로 총 n+lgn-2 의 시간복잡도가 든다. 따라서 위의 2n-3 보다 낮은 시간 복잡도를 가진다.

후보들이 lgn개인 것은 3이 lgn번의 대결에서 이겼음을 의미한다.

 이번에는 2번째로 큰 값으로 예를 들었지만, 각각의 n에 대해서 최적의 알고리즘이 존재할 수 있다. 따라서 쉽게 더 큰 알고리즘으로 해결하려들지 말고, key의 갯수가 정해져있을 때는 본인이 알고리즘을 구현해보는 것이 좋다.

 

O(n) 선택 알고리즘

매번 n번째 값을 찾는 알고리즘을 우리가 짜면 되겠지만(^ㅠ^..) 효율적인 알고리즘이 이미 나와있다. 과정을 살펴보자.

1. 리스트의 요소 갯수가 5이하라면 기본 비교로 대체한다.

기본 비교

 

2. 리스트를 5개씩 묶음으로 나눈 후, 각 묶음의 중간 값(median)을 찾는다.

기본 비교로 중간 값을 찾으며, 이를 median(M)이라고 부르고 가운데에 배치한다. 위에는 M보다 큰 값, 아래에는 M보다 작은 값을 2개씩 배치한다. 모든 set에 대해 위의 과정을 마치면 다음과 같은 모양이 된다.

 

3. 중간 값의 중간 값 (median들의 median)을 찾는다.

이는 전체 set의 median은 아니므로 바로 답이 될 수는 없다. median을 찾을 때는 재귀 방식으로 현재 진행 중인 과정을 재호출하면 된다. median의 median(m*)을 찾은 후에 왼쪽에는 이보다 작은 median의 set들이 오른쪽에는 이보다 큰 median의 set들이 위치하게 하면 다음과 같은 모양이 된다.

A, B, C, D 4그룹으로 각 요소를 나눌 수 있고, 각각의 그룹은 다음과 같은 특성을 가지고 있다.

• A, D : m*과 비교해서 대소관계를 알 수 없다.
• B : m*과 비교해서 큰 값들의 모임이다.
• C : m*과 비교해서 작은 값들의 모임이다.

S1, S2이라는 새로운 그룹을 정의해보자.

• S1 : C와 (A+D)에서 m*보다 작은 수들
• S2 : B와 (A+D)에서 m*보다 큰 수들

S1, S2는 A, D의 요소들을 모두 m*과 비교함으로써 생성할 수 있다.

 

4. k번째 요소의 위치를 확인한다.

k가 S1의 크기보다 작으면 재귀적으로 S1에 대한 선택 알고리즘 수행하면 되고, S1의 크기보다 크면 재귀적으로 S2에 대한 선택 알고리즘을 수행하면 된다. 딱 k라면 m*가 k번째 key이다.

if(S1.size()+1==k)
    answer = mStar;
else if(S1.size()>k)
    Selection(S1);
else if(S1.size()<k)
    Selection(S2);

 

시간 복잡도

2. 리스트를 5개씩 묶음으로 나눈 후, 각 묶음의 중간 값(median)을 찾는다.

기본 비교는 6번의 비교를 필요로 하므로, set의 갯수(n/5)에 6을 곱한 6(n/5)이 2번 과정의 시간복잡도이다.

3. 중간 값의 중간 값 (median들의 median)을 찾는다.

   Selection 알고리즘의 최악의 시간복잡도를 W(n)이라 하면, 재귀적으로 median의 집합만을 넣는 것이므로 m*을 찾는 과정의 시간 복잡도는 W(n/5)이다.

   S1, S2를 생성하기 위해 A+D의 집합과 m*를 비교하는 과정이 필요하다.

A+D 집합의 크기는 위의 그림에서 4r이므로 시간복잡도는 4r이다. n은 5(2r+1)이다.

4. k번째 요소의 위치를 확인한다.

최악의 경우는 A+D가 S1, S2 중 한 쪽에 속하는 경우이다. 이 때 집합의 크기는 7r+2가 되므로 시간복잡도는 W(7r+2)이다.

모든 시간 복잡도를 합치면
$$
W(n) = \frac{6n}{5}+W(\frac{n}{5})+4r+W(7r+2)
$$
이다. r을 n에 맞춰 표현하면
$$
W(n) = 1.2n + W(0.2n) + 0.4n + W(0.7n) = 1.6n + W(0.2n)+W(0.7n)
$$
이고 재귀적으로 나타낸 후 상수항만 보면

1.6n => 1.6(.9)n => 1.6(.81)n ...

0.9씩 늘어가므로 다 더하면 16n보다 작다.

따라서 O(n) Selection Algorithm의 시간복잡도는 O(n)이다.

현재까지 나온 가장 좋은 알고리즘은 2.95n까지 줄였다고 한다.

 

기본 비교

기본 비교란 x1, x2, x3, x4, x5가 있을 때, (x1, x2) => (x3, x4) => (x1, x3) => (x2, x5) => (x2, x3) => (x3, x5) 와 같은 6번의 비교로 중간 값을 찾아낼 수 있는 비교 알고리즘이다.