검색문제 썸네일형 리스트형 배열 내에 k번째로 작은 수 구하기 어떤 배열이 주어졌을 때, 그 배열 속에서 k번째로 작은 수를 구하는 일은 심심치 않게 발생한다. 나 같은 경우에는, 어떤 확률을 나타내고 있는 n차원 백터내에서 k번째로 큰 확률을 가진 클래스를 찾고 싶었다. 그럼 이를 어떻게 구현할 수 있을까? 가장 간단하게 떠오르는 방법은 (1) 주어진 벡터를 오름차순으로 정렬한 뒤 (인덱스를 알고싶다면 인덱스도 함께 저장), (2) k번째 값을 찾는 것이다. 해당 방법은 O(nlogn)의 시간복잡도를 가지며 적당한 시간 내에 끝나기 때문에 실용적이다. 하지만, 이것보다 더 빠르게 구현할 수 있는 방법이 있을까?검색 알고리즘 (selection algorithm)이번에 찾아보면서 알게 되었는데 배열 속에서 k번째로 작은 수를 구하는 문제는 알고리즘 분야에서는 꽤나 .. 더보기 이전 1 다음
