알고리즘/써먹기 좋은 알고리즘 알고리즘/써먹기 좋은 알고리즘 2020. 3. 29. Quick Selection을 이용한 k번째 숫자 탐색: O(n)의 시간 복잡도 N개의 원소 중 k번째로 작은 수를 찾아라 라는 문제를 만났을 때 가장 많이 사용하는 방법 중 하나는 컨테이너를 sorting 후에 k번째 인덱스를 참조하는 방식을 사용한다. 하지만 이렇게 정렬을 했을 경우엔 전체 시간 복잡도가 worst case O(N^2) 혹은 O(N longN)가 되어버리므로 원소의 개수가 많을 경우엔 적합하지 않다. 따라서 Quick Selection 알고리즘을 이용해서 O(N)의 시간 복잡도를 가지는 탐색을 구현할 수 있다. 이름에서도 유추할 수 있듯이 기본 idea는 Quick Sort에서 따왔다. int quick_selection(int n, int* ArrList, int k) { if (ArrList == NULL || n = mid) { std::swap(ArrLis.. 알고리즘/써먹기 좋은 알고리즘 2020. 3. 6. next_permutation을 이용한 조합의 개수 구하기 #include #include #include using namespace std; int main() { vector v; int n, k; cin >> n >> k; for (int i = 0; i < n; i++) v.push_back(i + 1); vector ind; //0과 1을 저장할 배열 벡터 생성 for (int i = 0; i < k; i++) ind.push_back(1); // k개의 1을 추가 for (int i = 0; i < v.size() - k; i++) ind.push_back(0); // n-k개의 0을 추가 sort(ind.begin(), ind.end()); do { for (int i = 0; i < ind.size(); i++) { if (ind[i] == 1).. 이전 1 다음
