C++/C++ STL
[C++ STL] 코딩테스트를 위한 algorithm
메카인
2023. 10. 16. 23:57
◆algorithm 클래스의 정의
: 알고리즘을 수행하는 C++ 표준 라이브러리 컨테이너 템플릿 함수를 정의합니다.
◆algorithm 클래스의 구문
(see links below for specific algorithm syntax)
◆algorithm 클래스의 함수
copy()
: 소스 범위의 요소를 대상 범위에 할당하여 요소의 소스 시퀀스 전체에서 반복하고 정방향으로 새 위치를 할당합니다.
first는 복사할 첫 위치, last는 마지막 위치, destBeg는 붙여넣을 위치를 나타냅니다. (exec는 사용할 실행 정책입니다.)
※ 단, 붙여넣을 공간이 할당되어 있는지 확인해야 합니다.
template<class InputIterator, class OutputIterator>
OutputIterator copy(
InputIterator first,
InputIterator last,
OutputIterator destBeg);
template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2>
ForwardIterator2 copy(
ExecutionPolicy&& exec,
ForwardIterator1 first,
ForwardIterator1 last,
ForwardIterator2 result);예제 코드)
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main()
{
vector<int> vec1{1, 2, 3};
vector<int> vec2{0, 0, 0, 0};
copy(vec1.begin(), vec1.end(), vec2.begin() + 1);
for (int i : vec2)
{
// 0 1 2 3
cout << i << " ";
}
}실행 예제)
count()
: 해당 값이 지정된 값과 일치하는 요소의 개수를 반환합니다.
first ~ last 까지의 범위에서 value의 개수를 반환합니다.
template<class InputIterator, class Type>
typename iterator_traits<InputIterator>::difference_type count(
InputIterator first,
InputIterator last,
const Type& value);
template<class ExecutionPolicy, class ForwardIterator, class Type>
typename iterator_traits<ForwardIterator>::difference_type
count(
ExecutionPolicy&& exec,
ForwardIterator first,
ForwardIterator last,
const Type& value);예제 코드)
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main()
{
vector<int> vec1{1, 1, 2, 3};
// 1 : 2
cout << "1 : " << count(vec1.begin(), vec1.end(), 1) << endl;
}실행 결과
count_if()
: 범위 내에서 해당 값이 지정된 조건과 일치하는 요소의 개수를 반환합니다.
template<class InputIterator, class UnaryPredicate>
typename iterator_traits<InputIterator>::difference_type count_if(
InputIterator first,
InputIterator last,
UnaryPredicate pred);
template<class ExecutionPolicy, class ForwardIterator, class UnaryPredicate>
typename iterator_traits<ForwardIterator>::difference_type
count_if(
ExecutionPolicy&& exec,
ForwardIterator first,
ForwardIterator last,
UnaryPredicate pred);예제 코드)
#include <vector>
#include <algorithm>
#include <iostream>
bool greater10(int value)
{
return value > 10;
}
int main()
{
using namespace std;
vector<int> v1{10, 20, 10, 40, 10};
vector<int>::iterator Iter;
cout << "v1 = ( ";
for (Iter = v1.begin(); Iter != v1.end(); Iter++)
cout << *Iter << " ";
cout << ")" << endl;
vector<int>::iterator::difference_type result1;
result1 = count_if(v1.begin(), v1.end(), greater10);
cout << "The number of elements in v1 greater than 10 is: "
<< result1 << "." << endl;
}실행 결과)
fill()
: 지정한 범위의 모든 요소에 동일한 새 값을 할당합니다.
template<class ForwardIterator, class Type>
void fill(
ForwardIterator first,
ForwardIterator last,
const Type& value);
template<class ExecutionPolicy, class ForwardIterator, class Type>
void fill(
ExecutionPolicy&& exec,
ForwardIterator first,
ForwardIterator last,
const Type& value);예제 코드)
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main()
{
vector<int> vec1(5);
fill(vec1.begin(), vec1.begin() + 3, 1);
for (int i : vec1)
{
// 1 1 1 0 0
cout << i << " ";
}
}실행 결과)
find()
: 범위에서 지정된 값을 가진 요소가 첫 번째로 나타나는 위치를 찾습니다.
※ 반환 자료형이 iterator 이므로 주의해서 사용합니다.
template<class InputIterator, class Type>
InputIterator find(
InputIterator first,
InputIterator last,
const Type& value);
template<class ExecutionPolicy, class ForwardIterator, class Type>
ForwardIterator find(
ExecutionPolicy&& exec,
ForwardIterator first,
ForwardIterator last,
const Type& value);예제 코드)
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main()
{
vector<int> vec1{0, 10, 20, 30, 1};
vector<int>::iterator it = find(vec1.begin(), vec1.end(), 10);
// 1
cout << it - vec1.begin();
}실행 결과)
for_each() //추후 추가
: 범위 내에서 정방향으로 각 요소에 지정된 함수 개체를 적용하고 함수 개체를 반환합니다.
: func는 범위의 각 요소에 적용되는 사용자 정의 함수 개체입니다.
template<class InputIterator, class Function>
Function for_each(
InputIterator first,
InputIterator last,
Function func);
template<class ExecutionPolicy, class ForwardIterator, class Function>
void for_each(
ExecutionPolicy&& exec,
ForwardIterator first,
ForwardIterator last,
Function func);max()
: 두 개체를 비교하고 둘 중 큰 개체를 반환합니다. 정렬 기준은 이진 조건자로 지정할 수 있습니다.
template<class Type>
constexpr Type& max(
const Type& left,
const Type& right);
template<class Type, class Pr>
constexpr Type& max(
const Type& left,
const Type& right,
BinaryPredicate pred);
template<class Type>
constexpr Type& max (
initializer_list<Type> ilist);
template<class Type, class Pr>
constexpr Type& max(
initializer_list<Type> ilist,
BinaryPredicate pred);예제 코드)
#include <iostream>
#include <algorithm>
using namespace std;
int main()
{
int one = 1;
int ten = 10;
// 10
cout << max(one, ten);
}실행 결과)
max_element()
: 지정된 범위에서 가장 큰 첫 번째 요소를 찾습니다. 정렬 기준은 이진 조건자로 지정할 수 있습니다.
※ 반환 자료형이 iterator 이므로 주의해서 사용합니다.
template<class ForwardIterator>
constexpr ForwardIterator max_element(
ForwardIterator first,
ForwardIterator last );
template<class ForwardIterator, class Compare>
constexpr ForwardIterator max_element(
ForwardIterator first,
ForwardIterator last,
Compare pred );
template<class ExecutionPolicy, class ForwardIterator>
ForwardIterator max_element(
ExecutionPolicy&& exec,
ForwardIterator first,
ForwardIterator last);
template<class ExecutionPolicy, class ForwardIterator, class Compare>
ForwardIterator max_element(
ExecutionPolicy&& exec,
ForwardIterator first,
ForwardIterator last,
Compare pred);예제 코드)
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main()
{
vector<int> vec1{10, 20, 10, 40, 10};
// 3 , 위치를 반환합니다.
cout << max_element(vec1.begin(), vec1.end()) - vec1.begin();
}
merge()
: 정렬된 두 소스 범위의 모든 요소를 정렬된 단일 대상 범위로 결합합니다. 정렬 기준은 이진 조건자로 지정할 수 있습니다.
result는 두 개의 소스 범위가 정렬된 단일 범위로 결합되는 대상 범위에서 첫 번째 요소 위치의 주소를 지정하는 입력 반복기입니다. (붙여 놓는 주소 입니다.)
template<class InputIterator1, class InputIterator2, class OutputIterator>
OutputIterator merge(
InputIterator1 first1,
InputIterator1 last1,
InputIterator2 first2,
InputIterator2 last2,
OutputIterator result );
template<class InputIterator1, class InputIterator2, class OutputIterator, class Compare>
OutputIterator merge(
InputIterator1 first1,
InputIterator1 last1,
InputIterator2 first2,
InputIterator2 last2,
OutputIterator result,
Compare pred );
template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2, class ForwardIterator>
ForwardIterator merge(
ExecutionPolicy&& exec,
ForwardIterator1 first1,
ForwardIterator1 last1,
ForwardIterator2 first2,
ForwardIterator2 last2,
ForwardIterator result);
template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2, class ForwardIterator, class Compare>
ForwardIterator merge(
ExecutionPolicy&& exec,
ForwardIterator1 first1,
ForwardIterator1 last1,
ForwardIterator2 first2,
ForwardIterator2 last2,
ForwardIterator result,
Compare pred);예제 코드)
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main()
{
vector<int> vec1{10, 20, 10, 40, 10};
vector<int> vec2{1, 2, 1, 4, 1};
// 충분한 공간이 선언되어 있어야 합니다.
vector<int> vec3(11);
// 두개의 컨테이너를 오름차순으로 붙여넣습니다.
// 1 2 1 4 1 10 20 10 40 10 0
merge(vec1.begin(), vec1.end(), vec2.begin(), vec2.end(), vec3.begin());
for (int i : vec3)
{
cout << i << " ";
}
}실행 결과)
min()
: 두 개체를 비교하고 둘 중 작은 개체를 반환합니다. 정렬 기준은 이진 조건자로 지정할 수 있습니다.
template<class Type>
constexpr const Type& min(
const Type& left,
const Type& right);
template<class Type, class Pr>
constexpr const Type& min(
const Type& left,
const Type& right,
BinaryPredicate pred);
template<class Type>
constexpr Type min(
initializer_list<Type> ilist);
template<class Type, class Pr>
constexpr Type min(
initializer_list<Type> ilist,
BinaryPredicate pred);
next_permutation()
: 원래 순서가 있는 경우 사전적으로 다음으로 더 큰 순열로 대체되도록 범위의 요소를 다시 정렬합니다. 다음 사전적 의미는 이진 조건자를 사용하여 지정할 수 있습니다.
template<class BidirectionalIterator>
bool next_permutation(
BidirectionalIterator first,
BidirectionalIterator last);
template<class BidirectionalIterator, class BinaryPredicate>
bool next_permutation(
BidirectionalIterator first,
BidirectionalIterator last,
BinaryPredicate pred);예제 코드)
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
void printV(vector<int> v);
int main()
{
// 1. next_permutation을 이용한 순열
int a[3]{1, 2, 3};
vector<int> v;
for (int i = 0; i < 3; i++)
v.push_back(a[i]);
do
{
printV(v);
} while (next_permutation(v.begin(), v.end()));
return 0;
}
void printV(vector<int> v)
{
for (int i = 0; i < v.size(); i++)
{
cout << v[i] << " ";
}
cout << "\n";
}실행 결과)
reverse()
: 범위 내에서 요소의 순서를 반대로 바꿉니다.
template<class BidirectionalIterator>
void reverse(
BidirectionalIterator first,
BidirectionalIterator last);
template<class ExecutionPolicy, class BidirectionalIterator>
void reverse(
ExecutionPolicy&& exec,
BidirectionalIterator first,
BidirectionalIterator last);예제 코드)
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
int main()
{
string str = "Why so Serious?";
cout << "Before Reverse : " << str << endl;
reverse(str.begin(), str.end());
cout << "After Reverse : " << str << endl;
}실행 결과)
rotate()
: 인접한 두 범위에 있는 요소를 교환합니다.
(middle ~ last]과 (first ~ middle]의 순서를 바꿔 줍니다.
template<class ForwardIterator>
void rotate(
ForwardIterator first,
ForwardIterator middle,
ForwardIterator last);
template<class ExecutionPolicy, class ForwardIterator>
ForwardIterator rotate(
ExecutionPolicy&& exec,
ForwardIterator first,
ForwardIterator middle,
ForwardIterator last);예제 코드)
#include <vector>
#include <algorithm>
#include <iostream>
int main()
{
using namespace std;
vector<int> v1;
vector<int>::iterator v1Iter1;
int i;
for (i = -3; i <= 5; i++)
{
v1.push_back(i);
}
cout << "Vector v1 is ( ";
for (v1Iter1 = v1.begin(); v1Iter1 != v1.end(); v1Iter1++)
{
cout << *v1Iter1 << " ";
}
cout << ")." << endl;
rotate(v1.begin(), v1.begin() + 3, v1.end());
cout << "After rotating, vector v1 is ( ";
for (v1Iter1 = v1.begin(); v1Iter1 != v1.end(); v1Iter1++)
{
cout << *v1Iter1 << " ";
}
cout << ")." << endl;
}실행 결과)
sort()
: 지정된 범위에 있는 요소를 비내림차순 또는 이진 조건자로 지정한 정렬 기준에 따라 정렬합니다.
pred는 순서에 따라 연속적인 요소에 대해 충족될 비교 조건을 정의하는 사용자 정의 조건자 함수 개체입니다.
template<class RandomAccessIterator>
void sort(
RandomAccessIterator first,
RandomAccessIterator last);
template<class RandomAccessIterator, class Compare>
void sort(
RandomAccessIterator first,
RandomAccessIterator last,
Compare pred);
template<class ExecutionPolicy, class RandomAccessIterator>
void sort(
ExecutionPolicy&& exec,
RandomAccessIterator first,
RandomAccessIterator last);
template<class ExecutionPolicy, class RandomAccessIterator, class Compare>
void sort(
ExecutionPolicy&& exec,
RandomAccessIterator first,
RandomAccessIterator last,
Compare pred);예제 코드)
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;
void printV(vector<int> vec1, string str)
{
cout << str << " : ";
for (int i : vec1)
{
cout << i << " ";
}
cout << endl;
return;
}
int main()
{
vector<int> vec1{0, 2, 5, 4, 3, 1, 0};
printV(vec1, "Origin");
sort(vec1.begin(), vec1.end());
printV(vec1, "Ascending");
sort(vec1.begin(), vec1.end(), greater<>());
printV(vec1, "Descending");
}실행 결과)
swap()
: 첫 번째 재정의는 두 개체의 값을 교환합니다. 두 번째 재정의는 두 개체 배열 간에 값을 교환합니다.
※ 인자 left, right를 iterator가 아닌 변수로 주어야 합니다.
template<class Type>
void swap(
Type& left,
Type& right);
template<class Type, size_t N>
void swap(
Type (& left)[N],
Type (& right)[N]);코드 예제)
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;
void printV(vector<int> vec1, string str)
{
cout << str << " : ";
for (int i : vec1)
{
cout << i << " ";
}
cout << endl;
return;
}
int main()
{
vector<int> vec1{0, 1, 2, 3};
printV(vec1, "Origin vec1");
swap(vec1[0], vec1[vec1.end() - vec1.begin() - 1]);
printV(vec1, "Swap vec1");
}실행 결과)
swap_ranges()
: 한 범위의 요소를 크기가 동일한 다른 범위의 요소로 교환합니다.
template<class ForwardIterator1, class ForwardIterator2>
ForwardIterator2 swap_ranges(
ForwardIterator1 first1,
ForwardIterator1 last1,
ForwardIterator2 first2 );
template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2>
ForwardIterator2 swap_ranges(
ExecutionPolicy&& exec,
ForwardIterator1 first1,
ForwardIterator1 last1,
ForwardIterator2 first2);코드 예제)
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;
void printV(vector<int> vec1, string str)
{
cout << str << " : ";
for (int i : vec1)
{
cout << i << " ";
}
cout << endl;
return;
}
int main()
{
vector<int> vec1{0, 2, 5, 4, 3, 1, 0};
vector<int> vec2{0, 1, 10, 100, 1000, 10000, 100000};
printV(vec1, "Origin vec1");
printV(vec2, "Origin vec1");
swap_ranges(vec1.begin(), vec1.end(), vec2.begin());
printV(vec1, "Swap vec1");
printV(vec2, "Swap vec2");
}실행 결과)
