선택문제 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)으로 생각할 수 있다고 합니다.
참고
감사합니다 :)