알고리즘 썸네일형 리스트형 배열 내에 k번째로 작은 수 구하기 어떤 배열이 주어졌을 때, 그 배열 속에서 k번째로 작은 수를 구하는 일은 심심치 않게 발생한다. 나 같은 경우에는, 어떤 확률을 나타내고 있는 n차원 백터내에서 k번째로 큰 확률을 가진 클래스를 찾고 싶었다. 그럼 이를 어떻게 구현할 수 있을까? 가장 간단하게 떠오르는 방법은 (1) 주어진 벡터를 오름차순으로 정렬한 뒤 (인덱스를 알고싶다면 인덱스도 함께 저장), (2) k번째 값을 찾는 것이다. 해당 방법은 O(nlogn)의 시간복잡도를 가지며 적당한 시간 내에 끝나기 때문에 실용적이다. 하지만, 이것보다 더 빠르게 구현할 수 있는 방법이 있을까?검색 알고리즘 (selection algorithm)이번에 찾아보면서 알게 되었는데 배열 속에서 k번째로 작은 수를 구하는 문제는 알고리즘 분야에서는 꽤나 .. 더보기 Number of components 오랜만에 한 문제 풀어봤다. Problem - E - Codeforces codeforces.com 어떤 왕국이 n개의 정점을 가지는 트리 구조라고 하자. 각각의 정점은 a_i라는 값을 가지고 있다. 모든 정점은 일자로 연결되어 있다. 정확하게, 1부터 n까지 모든 i에 대해서, i번째 정점과 i+1번째 정점은 간선으로 연결되어 있다. 여기서 함수 f(l, r)을 정의한다. (l in[i]; in[0] = 0; for(int i=1; i 더보기 이전 1 다음
