선택문제 Quick Select

- 선택문제: n개의 값 중에서 k번째로 크거나 작은 수를 찾는 문제

- Quick Select: pivot과 작은 값, 같은 값, 큰 값으로 나누어서 찾고자 하는 수가 어디에 속해있는지 찾아나가는 방법
1. pivot 고르기
2. 3부분으로 나누기 ( n-1번 수행 )
    S = { P보다 작은 값 }
    L = { P보다 큰 값 }
    M = { P와 같은 값 }
3. k가 어디에 속해 있는지 찾기
    |S| : 배열 S의 개수,
    (S에 속함)  if |S| >= k  { return 재귀(S, k) }
    (L에 속함)  else if |S| + |M| < k  { return 재귀(L, k - |S| - |M| }
    (M에 속함) else { return P }

- 시간복잡도
최선의 경우 O(n), 최악의 경우 O(n^2) 최악의 경우는 극히 드물어서 평균적으로 O(n)으로 생각한다.

 

Quick Select

n개의 값에서 k번째로 작은 수를 찾는 문제를 선택문제 라고 하는데요,
선택 문제를 해결하는 방법 중 Quick Selection에 대해 알아보겠습니다.

아이디어는 
pivot을 기준으로 아래의 3가지 부분으로 나눠서 k가 어디에 속해 있는지 생각해보는 것입니다.

small: pivot보다 작은 값,
big: pivot보다 큰 값,
same: pivot과 같은 값

배열을 쭉 돌면서 나누면 n-1로 가능하겠죠?
다음으로 k가 어디에 속해있는지 보는 것입니다. 각각의 배열의 크기로 범위를 생각해볼 수 있겠네요.

small: small.count >= k
big: small.count + same.count < k
same: 나머지

재귀적으로 이 과정을 반복해주면 된답니다 :)

구현

pivot을 그냥 배열의 첫 번째 요소로 생각하면 다음과 같이 구현할 수 있습니다.

func quickSelect(_ n: [Int], _ k: Int) -> Int {
    var small = [Int]()
    var same = [Int]()
    var big = [Int]()
    
    let pivot = n[0]
    
    for num in n {
        if num == pivot {
            same.append(num)
        } else if num < pivot {
            small.append(num)
        } else {
            big.append(num)
        }
    }
    
    if small.count >= k {
        return quickSelect(small, k)
    } else if small.count + same.count < k {
        return quickSelect(big, k - small.count - same.count)
    } else {
        return pivot
    }
}

 

시간 복잡도

Best case O(n)

피벗을 기준으로 양쪽이 균등하게 나눠진다면
나누어진 절반 중에서만 찾으면 되니까 T(n/2), 분배하는 횟수를 n으로 생각하면

T(n) = T(n/2) + n

로 생각할 수 있고, 절반의 절반을 또 찾으면 되니까 T(n/2) = T(n/2^2) + n/2로 생각할 수 있고 아래와 같은 식을 도출할 수 있습니다.

T(n) = T(n/2) + n
       = T(n/2^2 + n/2) + n
       = T(n/2^k) + n/2^(k-1) + ... + n/2 + n

이때 n = 2^k로 가정하면, T(n/2^k) = T(1) = 1 로 생각하고 지워버릴 수 있습니다. 그러면

T(n) = T(n/2) + n
       = T(n/2^2 + n/2) + n
       = T(n/2^k) + n/2^(k-1) + ... + n/2 + n 
       = n(1 + 1/2 + 1/2^2 + ... + 1/2^k) 

가 되고 이때 (1 + 1/2 + 1/2^2 + ... + 1/2^k) 부분은 1을 넘을 수가 없습니다.

따라서 O(n) 의 시간복잡도로 생각할 수 있습니다.

Worst case O(n^2)

그러면 최악의 경우를 생각해볼까요?
피벗을 기준으로 한쪽으로 모두 치우쳐져 있다면 최악의 경우엔
T(n) = T(n-1) + n 이 되므로 최악의 경우 n^2 을 돌아야합니다.

Average O(n)

하지만 이 경우는 극히 드물기 때문에 Quick Select은 평균적으로 O(n)으로 생각할 수 있다고 합니다.

 

참고

신찬수 교수님 Youtube

감사합니다 :)