Make Unreal REAL.
article thumbnail
Published 2023. 2. 20. 20:10
분할 정복 관련 STL 함수들 자료구조 & 알고리즘/코딩 테스트를 위한 자료 구조와 알고리즘 with C++
코딩 테스트를 위한 자료 구조와 알고리즘 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
profile

Make Unreal REAL.

@diesuki4

포스팅이 좋았다면 "좋아요❤️" 또는 "구독👍🏻" 해주세요!

검색 태그

티스토리툴바