[BOJ11004] K번째 수 (K-th smallest)

1. 문제

https://www.acmicpc.net/problem/11004

2. Note

알고리즘 수업에서 분할 정복을 다룰 때 배운 K-th smallest 문제와 정확히 같은 문제였다.
분할 정복 문제를 푸는 김에 복습해보려고 풀었는데 생각보다 구현에 애를 먹었다.
복습하면서 다음과 같은 주제들을 다시 살펴보았다.

2.1. 시간복잡도가 O(n)임을 증명하기 위해

• 수학적 귀납법(Mathmetical Induction)
• 정수론의 Well-Ordering Property
• 귀류법

2.2. 컨테이너의 일부만 정렬하는 함수 (std::sort와 다름에 주의)

• std::partial_sort

2.3. 피봇보다 작은, 같은, 큰 컨테이너로 나누는 기법

• 3-way partition

3. Reference

Wikipedia: Dutch national flag problem (3-way partition)