DEV/PS
[BOJ/11004] K번째 수 (QuickSelect로 풀기), c++
www.acmicpc.net/problem/11004 11004번: K번째 수 수 N개 A1, A2, ..., AN이 주어진다. A를 오름차순 정렬했을 때, 앞에서부터 K번째 있는 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 한줄 후기 : ㅂㅇㅎ 교수님 수업 같다 신촌 알고리즙 중급 연습 문제 였는데 확률적 알고리즘 파트에서 Quick Select를 알려주셔서 그거로 풀었다. 사실 풀고 찾아보니 대부분은 그냥 c++ sort 라이브러리로도 잘 풀린다고 한다. 아 그리고 c++에 아예 Quick Select를 구현해 놓은 라이브러리도 있다는데 그걸 쓰지는 않았다. Quick Select는 Quick Sort를 구현하면서 빠르게 n번째 원소를 찾는 기법이라고 한다. 실제 Sort는 대부분..
