코딩 테스트를 위한 자료 구조와 알고리즘 with C++
binary_search()
- 시퀀스(정렬된 상태)에서 이진 검색을 수행한다.
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
void main()
{
vector<int> v{1, 2, 3, 4, 5, 4, 3, 2, 1};
sort(v.begin(), v.end());
if (binary_search(v.begin(), v.end(), 3))
cout << "3을 찾았습니다." << endl;
else
cout << "3을 찾지 못했습니다." << endl;
sort(v.begin(), v.end(), greater<int>());
if (binary_search(v.begin(), v.end(), 6, greater<int>()))
cout << "6을 찾았습니다." << endl;
else
cout << "6을 찾지 못했습니다." << endl;
}
출력
3을 찾았습니다.
6을 찾지 못했습니다.
search()
- 원소들의 나열을 검색한다.
- 정렬된 상태가 아니어도 된다.
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
void main()
{
vector<int> v1{10, 20, 30, 40, 50, 60, 70, 80, 90};
vector<int> sub_sequence1{40, 50, 60};
if (search(v1.begin(), v1.end(), sub_sequence1.begin(), sub_sequence1.end()) != v1.end())
cout << "[40, 50, 60]을 찾았습니다." << endl;
else
cout << "[40, 50, 60]을 찾지 못했습니다." << endl;
vector<int> v2{20, 90, 30, 70, 50, 60, 40, 80, 10};
vector<int> sub_sequence2{30, 70, 50};
if (search(v2.begin(), v2.end(), sub_sequence2.begin(), sub_sequence2.end()) != v2.end())
cout << "[30, 70, 50]을 찾았습니다." << endl;
else
cout << "[30, 70, 50]을 찾지 못했습니다." << endl;
}
출력
[40, 50, 60]을 찾았습니다.
[30, 70, 50]을 찾았습니다.
search_n()
- val이 count 개수만큼 연속된 위치를 찾는다.
- 정렬된 상태가 아니어도 된다.
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
void main()
{
vector<int> v1{10, 20, 20, 40, 50, 60, 70, 80, 90};
if (search_n(v1.begin(), v1.end(), 2, 20) != v1.end())
cout << "[20, 20]을 찾았습니다." << endl;
else
cout << "[20, 20]을 찾지 못했습니다." << endl;
vector<int> v2{50, 90, 30, 50, 50, 50, 40, 80, 10};
if (search_n(v2.begin(), v2.end(), 3, 50) != v2.end())
cout << "[50, 50, 50]을 찾았습니다." << endl;
else
cout << "[50, 50, 50]을 찾지 못했습니다." << endl;
}
출력
[20, 20]을 찾았습니다.
[50, 50, 50]을 찾았습니다.
lower_bound()
- val보다 크거나 같은 첫 위치를 찾는다.
upper_bound()
- val보다 큰 첫 위치를 찾는다.
둘 모두 정렬된 상태에서 사용해야 한다.
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
void main()
{
vector<int> v{10, 20, 30, 30, 20, 10, 10, 20};
// 10, 10, 10, 20, 20, 20, 30, 30
sort(v.begin(), v.end());
auto low_bound = lower_bound(v.begin(), v.end(), 20);
auto up_bound = upper_bound(v.begin(), v.end(), 20);
cout << "위치 " << low_bound - v.begin() << "에서 20보다 크거나 같은 수를 찾았습니다." << endl;
cout << "위치 " << up_bound - v.begin() << "에서 20보다 큰 수를 찾았습니다." << endl;
}
출력
위치 3에서 20보다 크거나 같은 수를 찾았습니다.
위치 6에서 20보다 큰 수를 찾았습니다.
partition()
- pred 조건에 따라 참인 원소는 왼쪽, 거짓인 원소는 오른쪽으로 몰아 배치한다.
- 원본 순서가 유지됨을 보장하지 않는다.
- 오른쪽 집합의 시작 위치를 반환한다.
- 정렬된 상태가 아니어도 된다.
stable_partition()
- partition()과 같은 동작을 하나 원본 순서가 유지된다.
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
void print(vector<int>::iterator fromInclusive, vector<int>::iterator toExclusive);
void main()
{
vector<int> v1{9, 2, 1, 6, 5, 4, 7, 8, 3};
vector<int> v2(v1);
auto bound = partition(v1.begin(), v1.end(), [](int e) { return e & 1; });
cout << "partition()" << endl;
cout << "홀수: "; print(v1.begin(), bound);
cout << "짝수: "; print(bound, v1.end());
cout << endl;
bound = stable_partition(v2.begin(), v2.end(), [](int e) { return e & 1; });
cout << "stable_partition()" << endl;
cout << "홀수: "; print(v2.begin(), bound);
cout << "짝수: "; print(bound, v2.end());
cout << endl;
}
출력
partition()
홀수: 9 3 1 7 5
짝수: 4 6 8 2
stable_partition()
홀수: 9 1 5 7 3
짝수: 2 6 4 8
partition_copy()
- pred 조건에 따라 참인 원소는 첫 번째 공간에, 거짓인 원소는 두 번째 공간에 몰아 복사한다.
- 정렬된 상태가 아니어도 된다.
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
void print(vector<int> v);
void main()
{
vector<int> v{9, 2, 1, 6, 5, 4, 7, 8, 3};
vector<int> odd(5);
vector<int> even(4);
partition_copy(v.begin(), v.end(), odd.begin(), even.begin(), [](int e) { return e & 1; });
cout << "홀수: "; print(odd);
cout << "짝수: "; print(even);
cout << endl;
int pivot = 3;
vector<int> left(3);
vector<int> right(6);
partition_copy(v.begin(), v.end(), left.begin(), right.begin(), [pivot](int e) { return e <= pivot; });
cout << "3보다 작거나 같은 원소들: "; print(left);
cout << "3보다 큰 원소들: "; print(right);
}
출력
홀수: 9 1 5 7 3
짝수: 2 6 4 8
3보다 작거나 같은 원소들: 2 1 3
3보다 큰 원소들: 9 6 5 4 7 8
partition_point()
- 이미 분할된 파티션에서 bound(오른쪽 집합의 시작 위치)를 찾는다.
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
void print(vector<int> v);
void main()
{
vector<int> v{9, 2, 1, 6, 5, 4, 7, 8, 3};
auto is_odd = [](int e) { return e & 1; };
partition(v.begin(), v.end(), is_odd);
print(v);
cout << "파티션에서 홀수가 아닌 첫 위치: " << distance(v.begin(), partition_point(v.begin(), v.end(), is_odd)) << endl;
}
출력
9 3 1 7 5 4 6 8 2
파티션에서 홀수가 아닌 첫 위치: 5
is_partitioned()
- pred의 참, 거짓을 기준으로 좌우로 분할되어 있는지 확인한다.
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
void print(vector<int> v);
void main()
{
vector<int> v{9, 2, 1, 6, 5, 4, 7, 8, 3};
auto is_odd = [](int e) { return e & 1; };
print(v);
if (is_partitioned(v.begin(), v.end(), is_odd))
cout << "[홀수][짝수]가 나뉘어져 있습니다." << endl << endl;
else
cout << "[홀수][짝수]가 나뉘어져 있지 않습니다." << endl << endl;
partition(v.begin(), v.end(), is_odd);
print(v);
if (is_partitioned(v.begin(), v.end(), is_odd))
cout << "[홀수][짝수]가 나뉘어져 있습니다.";
else
cout << "[홀수][짝수]가 나뉘어져 있지 않습니다.";
}
출력
9 2 1 6 5 4 7 8 3
[홀수][짝수]가 나뉘어져 있지 않습니다.
9 3 1 7 5 4 6 8 2
[홀수][짝수]가 나뉘어져 있습니다.
sort()
- 배열을 정렬한다.
- 내부적으로 여러 알고리즘이 조합된 인트로 정렬 기법을 사용한다.
stable_sort()
- sort()와 같은 동작을 하나 순위가 같은 원소의 원본 순서의 유지를 보장한다.
- 보장한다고 한 이유는 sort()도 일부를 제외하고는 대부분의 경우 원본 순서를 유지하기 때문이다.
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
template <typename T>
void print(vector<T> v);
void main()
{
vector<int> v{9, 2, 1, 6, 5, 4, 7, 8, 3};
sort(v.begin(), v.end());
cout << "sort(begin, end): "; print(v);
sort(v.begin(), v.end(), greater<int>());
cout << "sort(begin, end, greater): "; print(v);
sort(v.rbegin(), v.rend());
cout << "sort(rbegin, rend): "; print(v);
cout << endl;
vector<float> f1{9.0, 2.45, 6.3, 5.2, 4.85, 7.0, 5.5, 2.03, 4.11};
vector<float> f2(f1);
auto compare_as_int = [](int a, int b) { return a < b; };
sort(f1.begin(), f1.end(), compare_as_int);
cout << "sort(): "; print(f1);
stable_sort(f2.begin(), f2.end(), compare_as_int);
cout << "stable_sort(): "; print(f2);
}
출력
sort(begin, end): 1 2 3 4 5 6 7 8 9
sort(begin, end, greater): 9 8 7 6 5 4 3 2 1
sort(rbegin, rend): 9 8 7 6 5 4 3 2 1
sort(): 2.45 2.03 4.85 4.11 5.2 5.5 6.3 7 9
stable_sort(): 2.45 2.03 4.85 4.11 5.2 5.5 6.3 7 9
partial_sort()
- first ~ last 구간에서 first ~ middle 사이의 개수만큼 순위가 높은 원소들을 first ~ middle 구간에 정렬되도록 배치한다.
- 당연히 last와 middle은 Exclusive이다.
- 예를 들어, 100명 중 가장 점수가 낮은 5명만 성적순으로 뽑고 싶을 때 사용할 수 있다.
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
void print(vector<int> v);
void main()
{
vector<int> v{9, 2, 1, 6, 5, 4, 7, 8, 3};
partial_sort(v.begin() + 2, v.begin() + 5, v.end());
print(v);
}
출력
- [9 2][1 6 5 4 7 8 3]
- [9 2][(1 3 4) 6 7 8 5]
9 2 1 3 4 6 7 8 5
merge()
- 정렬된 시퀀스를 병합한다.
- 단순히 concat하는 것이 아니라 오름차순으로 배치하는 것이다.
- 정렬되지 않은 상태에서 실행하면 런타임 오류가 발생한다.
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
void print(vector<int> v);
void main()
{
vector<int> v1{5, 10, 15, 20, 25};
vector<int> v2{50, 40, 30, 20, 10};
vector<int> m(10);
// 런타임 오류 발생 ! !
// merge(v1.begin(), v1.end(), v2.begin(), v2.end(), m.begin());
sort(v1.begin(), v1.end());
sort(v2.begin(), v2.end());
merge(v1.begin(), v1.end(), v2.begin(), v2.end(), m.begin());
print(m);
}
출력
5 10 10 15 20 20 25 30 40 50
nth_element()
- first ~ last 구간에서 nth 위치의 원소가 확정될 때까지 정렬한다.
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
void print(vector<int> v);
void main()
{
vector<int> v{1, 2, 3, 4, 5, 6, 7, 8, 9};
random_shuffle(v.begin(), v.end());
// 2 ~ 9 구간에서 4(5-2+1)번째로 작은 수가 정해질 때까지 정렬
nth_element(v.begin() + 2, v.begin() + 5, v.end());
print(v);
random_shuffle(v.begin(), v.end());
// 2 ~ 9 구간에서 2(3-2+1)번째로 작은 수가 정해질 때까지 정렬
nth_element(v.begin() + 2, v.begin() + 3, v.end());
print(v);
}
출력
9 2 1 3 4 5 6 7 8
4 7 1 2 3 5 6 8 9
accumulate()
- init + 각 원소에 binary_op를 수행한 결과의 합을 계산한다.
- 누적합 방식으로 계산된다.
#include <iostream>
#include <numeric>
#include <vector>
#include <cmath>
using namespace std;
void main()
{
vector<int> v{1, 2, 3};
cout << accumulate(v.begin(), v.end(), 100) << endl;
// current_sum은 현재까지의 합, e는 현재 원소를 뜻한다.
cout << accumulate(v.begin(), v.end(), 0, [](int current_sum, int e) { return current_sum + pow(e, 2); }) << endl;
}
출력
106
14
reduce()
- accumulate()와 같은 동작을 하나 병렬 처리를 지원한다.
- C++17부터 지원한다.
#include <iostream>
#include <numeric>
#include <vector>
#include <cmath>
using namespace std;
void main()
{
vector<int> v{1, 2, 3};
#if (__cplusplus >= 201703L)
cout << reduce(v.begin(), v.end(), 100) << endl;
// current_sum은 현재까지의 합, e는 현재 원소를 뜻한다.
cout << reduce(v.begin(), v.end(), 0, [](int current_sum, int e) { return current_sum + pow(e, 2); }) << endl;
#endif
}
출력
106
14
for_each()
- 각 원소에 대해 Func를 수행한다.
- 순차적으로 수행됨을 보장한다.
- 참조를 전달하면 원소의 값을 수정할 수 있지만 for_each()의 바람직한 사용법은 아니다.
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
void print(vector<int> v);
void main()
{
vector<int> v{1, 2, 3, 4, 5, 6};
for_each(v.begin(), v.end(), [](int e) { cout << e << " "; });
cout << endl;
for_each(v.begin(), v.end(), [](int &e) { e *= 10; });
print(v);
}
출력
1 2 3 4 5 6
10 20 30 40 50 60
transform()
- 각 원소에 unary_op (하나의 인자) 혹은 binary_op (두 개의 인자)를 적용한 결과를 다른 컨테이너에 저장한다.
- 순차적으로 수행됨을 보장하지 않는다.
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
void print(vector<int> v);
void main()
{
string s = "hello world !!";
vector<int> v1{1, 2, 3, 4, 5, 6};
vector<int> v2(v1.size());
vector<int> v3;
transform(s.begin(), s.end(), s.begin(), ::toupper);
cout << s << endl;
transform(v1.begin(), v1.end(), v2.begin(), [](int e) { return e * 10; });
print(v2);
transform(v1.begin(), v1.end(), v2.begin(), back_inserter(v3), ::plus<int>());
print(v3);
}
출력
HELLO WORLD !!
10 20 30 40 50 60
11 22 33 44 55 66
'자료구조 & 알고리즘 > 코딩 테스트를 위한 자료 구조와 알고리즘 with C++' 카테고리의 다른 글
탐욕법(Greedy Algorithm) (0) | 2023.02.22 |
---|---|
맵리듀스(MapReduce) (0) | 2023.02.21 |
병합 정렬(Merge Sort) (0) | 2023.02.17 |
이진 검색(Binary Search) (0) | 2023.02.16 |
분할 정복(Divide and Conquer) (0) | 2023.02.15 |