lower_bound 및 upper_bound는 내장된 이진 검색 기능입니다.
lower_bound - 대수 시간에서 주어진 값 k보다 크거나 같은 정렬된 배열에서 가장 작은 요소를 찾는 함수입니다.
배열의 범위와 k 값을 인수로 사용합니다.
발견된 요소 또는 그러한 요소가 존재하지 않는 경우 배열의 끝(포함되지 않음)에 대한 반복자를 반환합니다.
문서에서 자세한 내용을 확인할 수 있습니다.
upper_bound - 정렬된 배열의 대수 시간에서 주어진 값 k보다 엄격하게 큰 가장 작은 요소를 찾는 함수입니다.
배열의 범위와 k 값을 인수로 사용합니다.
발견된 요소 또는 그러한 요소가 존재하지 않는 경우 배열의 끝(포함되지 않음)에 대한 반복자를 반환합니다.
문서에서 자세한 내용을 확인할 수 있습니다.
위의 랜덤 액세스 컬렉션에 반복자가 없기 때문에 집합 또는 다중 집합에서 이러한 함수를 사용하는 것이 대수 시간에 작동하지 않는다는 점을 명확히 할 가치가 있습니다.
그러나 이러한 컬렉션에는 해당 내장 메서드가 있습니다(즉, "점을 통해" 사용해야 함).
예:
벡터 a = { 0, 1, 3, 5, 7 };
vector::iterator it;
it = lower_bound(a.begin(), a.end(), 4);
// *it == 5
it = lower_bound(a.begin(), a.end(), 5);
// *it == 5
it = lower_bound(a.begin(), a.end(), 8);
// 그것 == a.end()
it = upper_bound(a.begin(), a.end(), 4);
// *it == 5
it = upper_bound(a.begin(), a.end(), 5);
// *it == 7
it = upper_bound(a.begin(), a.end(), -1);
// *it == 0
// 반복자를 빼면 찾은 요소의 인덱스를 얻을 수 있습니다.
int ind = lower_bound(a.begin(), a.end(), 4) - a.begin();
// 인더 == 3
// set 및 유사한 컬렉션에 대해 함수 대신 메서드를 사용해야 합니다.
set s{ 1, 3, 5 };
set::iterator 앉아;
앉아 = s.lower_bound(3);
// *앉아 == 3
앉아 = s.upper_bound(3);
// *앉아 == 5
|
고유 - 동일한 연속 요소의 모든 시퀀스를 선형 시간으로 압축하는 기능.
인수로 압축을 적용하는 데 필요한 배열의 경계가 전달됩니다.
반복자는 배열의 새로운 끝(포괄하지 않음)으로 반환됩니다. 정의되지 않은 값을 가지므로 새 끝 뒤와 이전 끝 앞의 요소에 주의해야 합니다.
자세한 내용은 문서에서 확인할 수 있습니다.
벡터에서 이 기능을 사용하는 경우 반환된 결과를 사용하여 크기를 조정하는 것이 편리합니다(자세한 내용은 아래 참조).
예:
벡터 a = { 3, 3, 3, 2, 3, 3, 1, 1, 4, 5, 5 };
unique(a.begin(), a.end());
// a = [3, 2, 3, 1, 4, 5, ?, ?, ?, ?, ?]
// 유니크함수를 사용하면 편하다.
// 좌표 압축을 위한 보조 배열
a = {235, 10, 41, 10, 41, 41, 235, 500, 500};
정렬(a.begin(), a.end());
// a = [10, 10, 41, 41, 41, 235, 235, 500, 500]
a.resize(unique(a.begin(), a.end()) - a.begin());
// a = [10, 41, 235, 500]
|
병합 - 두 개의 정렬된 배열을 병합하는 기능, 즉 선형 시간에 첫 번째 및 두 번째 배열의 요소로 구성된 정렬된 배열을 얻습니다.
5개의 인수를 취합니다: 각 배열에 대한 두 개의 경계와 대상의 왼쪽 경계(결과 배열의 요소가 배치될 위치).
자세한 내용은 문서에서 확인할 수 있습니다.
예:
// 소스 배열을 정렬해야 합니다.
벡터 a = { 1, 3, 5, 7 };
벡터 b = { 2, 4, 6 };
// 대상이 충분히 커야 함
vectorc(7);
merge(a.begin(), a.end(), b.begin(), b.end(), c.begin());
// c = [1, 2, 3, 4, 5, 6, 7]
// 요소는 반복 가능
a = {1, 2, 4, 4};
b = {2, 3, 3, 3, 4, 4};
c.resize(10);
merge(a.begin(), a.end(), b.begin(), b.end(), c.begin());
// c = [1, 2, 2, 3, 3, 3, 4, 4, 4, 4]
이 기능은 병합 정렬의 맥락에서 매우 유용합니다.
|
nth_element는 선형 시간으로 정렬된 순서로 배열에서 n번째 요소를 찾을 수 있게 해주는 함수입니다.
이 함수는 배열의 왼쪽 끝, 정렬된 순서로 값을 찾을 위치의 반복자, 배열의 오른쪽 끝을 가져옵니다.
함수 적용 후 필요한 값은 iterator가 가리키는 곳에 위치하게 되고, 나머지 값들은 혼돈의 순서를 가지게 되지만 n번째 왼쪽에는 그 이하의 값들이 있게 되며, 오른쪽으로. 즉, 이 함수는 요소의 원래 순서를 파괴하는 것으로 이해해야 합니다.
자세한 내용은 설명서(https://www.cplusplus.com/reference/algorithm/nth_element/)에서 확인할 수 있습니다.
예:
벡터 a = { 4, 0, 3, 9, 2, 1, 8, 5, 6, 7 };
// 인덱스 4에서 요소를 찾습니다.
// 인수의 순서에 주의
nth_element(a.begin(), a.begin() + 4, a.end());
// a = [#, #, #, #, 4, $, $, $, $, $]
// 여기서 # <= 4 및 4 <= $
|
길이 n의 순열은 숫자 1, 2, ..., n이 반복되지 않는 정렬된 모음입니다. 예를 들어 [3, 1, 2]와 [5, 4, 3, 2, 1]은 순열이지만 [1, 2, 1, 3]과 [1, 2, 4]는 순열이 아닙니다.
작업이 길이 n의 모든 순열을 반복해야 한다는 사실로 축소되면 "next_permutation"이라고 하는 C++의 편리한 메커니즘을 사용할 수 있습니다.
문서에서 자세히 알아볼 수 있지만 요점은 이 함수가 전달된 배열을 변경한다는 것입니다. 사전식 순서(일반적으로 명확하고 이름이 명확함)의 후속 순열로.
next_permutation을 사용하려면 알고리즘 라이브러리를 포함해야 합니다(예: 프로그램 시작 부분에 #include <algorithm> 작성)
예:
vector 어러;
도착 = {1, 2, 3}; // 배열은 [1, 2, 3]입니다.
next_permutation(arr.begin(), arr.end()); // 전체 배열을 함수에 전달
// 배열은 이제 [1, 3, 2]입니다.
도착 = { 2, 3, 1 }; // 배열은 [2, 3, 1]입니다.
next_permutation(arr.begin(), arr.end()); // 전체 배열을 함수에 전달
// 배열은 이제 [3, 1, 2]입니다.
next_permutation(arr.begin() + 1, arr.begin() + 3); // 배열의 일부에 함수를 적용할 수 있지만 실제로는 거의 필요하지 않습니다.
// 배열은 이제 [3, 2, 1]입니다.
이 경우 함수는 다음 순열이 생성되면 true이고 다음 순열이 없으면 false인 부울 반환 값을 갖습니다(사전식 순서의 최대 순열이 함수에 전달되는 경우).
이렇게 하면 루프에서 함수를 사용할 수 있으므로 모든 순열을 한 번에 반복할 수 있습니다. 0-인덱싱으로 인해 순열에는 공식적으로 1에서 n까지의 숫자가 포함되지만 실제로는 0에서 n - 1까지의 숫자 순열로 작업하는 것이 더 편리한 경우가 많습니다. 그러나 다행스럽게도 이것은 코드에서 추가 오버레이로 이어지지 않습니다. next_permutation 함수는 인덱스가 0인 순열에 맞게 조정됩니다(및 배열의 중복 요소도 있지만 더 많은 정보를 직접 찾을 수 있음).
일반적으로 모든 순열을 반복하는 코드는 다음과 같습니다.
정수; // 순열 크기
vectorperm(n); // perm은 "순열"의 줄임말입니다. "순열"
for (int i = 0; i < n; i++)
perm[i] = i; // 초기 순열 0, 1, ..., n - 1 초기화
하다 {
// 루프 내부에서 현재 순열을 처리합니다.
} 동안 (next_permutation(perm.begin(), perm.end())); // 다음 순열이 없으면 루프를 종료합니다.
이 코드는 O(n! * f(n))에서 실행됩니다. 여기서 f(n)은 하나의 특정 순열을 처리하는 데 걸리는 시간입니다.
|