[Algorithm/Divide&Conquer] 06. 분할 정복 기법과 C++ 표준 라이브러리 함수

분할 정복 기법과 C++ 표준 라이브러리 함수

앞선 게시글에서 알고리즘에 필요한 기능을 직접 구현해보았지만, C++ 표준 라이브러리는 미리 정의된 다수의 알고리즘 함수를 제공하고 있다.

std::binary_search()

std::binary_search() 함수는 정렬된 범위에서 특정 값을 찾기 위해 이진 검색 알고리즘을 사용합니다. 이 함수는 주어진 값이 정렬된 범위 내에 존재하는지를 확인하고, 존재 여부에 따라 true 또는 false를 반환합니다.

헤더 파일:

#include <algorithm>

사용법:

bool binary_search(InputIt first, InputIt last, const T& value);
bool binary_search(InputIt first, InputIt last, const T& value, Compare comp);

매개변수:

• first, last: 검색할 정렬된 범위의 시작과 끝을 나타내는 반복자.
• value: 검색할 값.
• comp: 값을 비교하는 데 사용할 이진 함수 객체(optional).

반환 값:

• 범위 내에 값이 존재하면 true, 그렇지 않으면 false.

예제:

#include <iostream>
#include <vector>
#include <algorithm>

int main() {
    std::vector<int> vec = {1, 3, 5, 7, 9, 11};

    if (std::binary_search(vec.begin(), vec.end(), 5)) {
        std::cout << "5 is found in the vector." << std::endl;
    } else {
        std::cout << "5 is not found in the vector." << std::endl;
    }

    return 0;
}

std::search()

std::search() 함수는 특정 서브 시퀀스가 범위 내에 존재하는지 찾습니다. 이 함수는 서브 시퀀스의 시작 반복자를 반환하며, 서브 시퀀스가 범위 내에 없으면 last 반복자를 반환합니다.

헤더 파일:

#include <algorithm>

사용법:

ForwardIt search(ForwardIt first, ForwardIt last, ForwardIt s_first, ForwardIt s_last);
ForwardIt search(ForwardIt first, ForwardIt last, ForwardIt s_first, ForwardIt s_last, BinaryPredicate p);

매개변수:

• first, last: 검색할 범위의 시작과 끝을 나타내는 반복자.
• s_first, s_last: 검색할 서브 시퀀스의 시작과 끝을 나타내는 반복자.
• p: 요소를 비교하는 데 사용할 이진 함수 객체(optional).

반환 값:

• 서브 시퀀스의 첫 번째 요소를 가리키는 반복자. 서브 시퀀스가 범위 내에 없으면 last 반복자.

예제:

#include <iostream>
#include <vector>
#include <algorithm>

int main() {
    std::vector<int> vec = {1, 2, 3, 4, 5, 6, 7, 8, 9};
    std::vector<int> sub_vec = {4, 5, 6};

    auto it = std::search(vec.begin(), vec.end(), sub_vec.begin(), sub_vec.end());

    if (it != vec.end()) {
        std::cout << "Subsequence found at position: " << std::distance(vec.begin(), it) << std::endl;
    } else {
        std::cout << "Subsequence not found." << std::endl;
    }

    return 0;
}

std::upper_bound()

std::upper_bound 함수는 정렬된 범위에서 특정 값보다 큰 첫 번째 요소의 위치를 찾습니다.

헤더 파일:

#include <algorithm>

사용법:

ForwardIt upper_bound(ForwardIt first, ForwardIt last, const T& value);
ForwardIt upper_bound(ForwardIt first, ForwardIt last, const T& value, Compare comp);

매개변수:

• first, last: 검색할 정렬된 범위의 시작과 끝을 나타내는 반복자.
• value: 검색할 값.
• comp: 값을 비교하는 데 사용할 이진 함수 객체(optional).

반환 값:

• 특정 값보다 큰 첫 번째 요소의 반복자.

예제:

#include <iostream>
#include <vector>
#include <algorithm>

int main() {
    std::vector<int> vec = {1, 2, 4, 4, 5, 6};
    auto it = std::upper_bound(vec.begin(), vec.end(), 4);

    std::cout << "The first element greater than 4 is: " << *it << std::endl;

    return 0;
}

std::lower_bound()

std::lower_bound 함수는 정렬된 범위에서 특정 값 이상인 첫 번째 요소의 위치를 찾습니다.

헤더 파일:

#include <algorithm>

사용법:

ForwardIt lower_bound(ForwardIt first, ForwardIt last, const T& value);
ForwardIt lower_bound(ForwardIt first, ForwardIt last, const T& value, Compare comp);

매개변수:

• first, last: 검색할 정렬된 범위의 시작과 끝을 나타내는 반복자.
• value: 검색할 값.
• comp: 값을 비교하는 데 사용할 이진 함수 객체(optional).

반환 값:

• 특정 값 이상인 첫 번째 요소의 반복자.

예제:

#include <iostream>
#include <vector>
#include <algorithm>

int main() {
    std::vector<int> vec = {1, 2, 4, 4, 5, 6};
    auto it = std::lower_bound(vec.begin(), vec.end(), 4);

    std::cout << "The first element not less than 4 is: " << *it << std::endl;

    return 0;
}

std::partition()

std::partition 함수는 주어진 범위를 조건에 따라 두 개의 그룹으로 재배치합니다. 조건을 만족하는 요소들은 앞쪽 그룹에, 만족하지 않는 요소들은 뒤쪽 그룹에 위치하게 됩니다.

헤더 파일:

#include <algorithm>

사용법:

ForwardIt partition(ForwardIt first, ForwardIt last, UnaryPredicate p);

매개변수:

• first, last: 범위의 시작과 끝을 나타내는 반복자.
• p: 조건을 나타내는 단항 함수 객체.

반환 값:

• 조건을 만족하지 않는 첫 번째 요소의 반복자.

예제:

#include <iostream>
#include <vector>
#include <algorithm>

int main() {
    std::vector<int> vec = {1, 2, 3, 4, 5, 6, 7, 8, 9};
    auto it = std::partition(vec.begin(), vec.end(), [](int n){ return n % 2 == 0; });

    std::cout << "Partitioned vector: ";
    for (int n : vec) {
        std::cout << n << " ";
    }
    std::cout << std::endl;

    return 0;
}

std::is_partitioned()

std::is_partitioned 함수는 주어진 범위가 특정 조건에 따라 분할되어 있는지 확인합니다.

헤더 파일:

#include <algorithm>

사용법:

bool is_partitioned(InputIt first, InputIt last, UnaryPredicate p);

매개변수:

• first, last: 범위의 시작과 끝을 나타내는 반복자.
• p: 조건을 나타내는 단항 함수 객체.

반환 값:

• 범위가 조건에 따라 분할되어 있으면 true, 그렇지 않으면 false.

예제:

#include <iostream>
#include <vector>
#include <algorithm>

int main() {
    std::vector<int> vec = {2, 4, 6, 1, 3, 5};
    bool result = std::is_partitioned(vec.begin(), vec.end(), [](int n){ return n % 2 == 0; });

    std::cout << "Vector is partitioned: " << std::boolalpha << result << std::endl;

    return 0;
}

std::stable_partition()

std::stable_partition 함수는 주어진 범위를 조건에 따라 두 개의 그룹으로 재배치합니다. 이때 요소들의 상대적인 순서는 유지됩니다.

헤더 파일:

#include <algorithm>

사용법:

ForwardIt stable_partition(ForwardIt first, ForwardIt last, UnaryPredicate p);

매개변수:

• first, last: 범위의 시작과 끝을 나타내는 반복자.
• p: 조건을 나타내는 단항 함수 객체.

반환 값:

• 조건을 만족하지 않는 첫 번째 요소의 반복자.

예제:

#include <iostream>
#include <vector>
#include <algorithm>

int main() {
    std::vector<int> vec = {1, 2, 3, 4, 5, 6, 7, 8, 9};
    auto it = std::stable_partition(vec.begin(), vec.end(), [](int n){ return n % 2 == 0; });

    std::cout << "Stably partitioned vector: ";
    for (int n : vec) {
        std::cout << n << " ";
    }
    std::cout << std::endl;

    return 0;
}

std::sort()

std::sort 함수는 범위를 오름차순으로 정렬합니다.

헤더 파일:

#include <algorithm>

사용법:

void sort(RandomIt first, RandomIt last);
void sort(RandomIt first, RandomIt last, Compare comp);

매개변수:

• first, last: 정렬할 범위의 시작과 끝을 나타내는 반복자.
• comp: 요소를 비교하는 데 사용할 이진 함수 객체(optional).

예제:

#include <iostream>
#include <vector>
#include <algorithm>

int main() {
    std::vector<int> vec = {9, 3, 1, 5, 4, 7, 6, 8, 2};
    std::sort(vec.begin(), vec.end());

    std::cout << "Sorted vector: ";
    for (int n : vec) {
        std::cout << n << " ";
    }
    std::cout << std::endl;

    return 0;
}

std::stable_sort()

std::stable_sort 함수는 범위를 오름차순으로 정렬합니다. 이때 요소들의 상대적인 순서는 유지됩니다.

헤더 파일:

#include <algorithm>

사용법:

void stable_sort(RandomIt first, RandomIt last);
void stable_sort(RandomIt first, RandomIt last, Compare comp);

매개변수:

• first, last: 정렬할 범위의 시작과 끝을 나타내는 반복자.
• comp: 요소를 비교하는 데 사용할 이진 함수 객체(optional).

예제:

#include <iostream>
#include <vector>
#include <algorithm>

int main() {
    std::vector<int> vec = {9, 3, 1, 5, 4, 7, 6, 8, 2};
    std::stable_sort(vec.begin(), vec.end());

    std::cout << "Stably sorted vector: ";
    for (int n : vec) {
        std::cout << n << " ";
    }
    std::cout << std::endl;

    return 0;
}

std::partial_sort()

std::partial_sort 함수는 범위의 일부를 정렬합니다. 지정된 범위의 시작부터 n번째 요소까지 오름차순으로 정렬합니다.

헤더 파일:

#include <algorithm>

사용법:

void partial_sort(RandomIt first, RandomIt middle, RandomIt last);
void partial_sort(RandomIt first, RandomIt middle, RandomIt last, Compare comp);

매개변수:

• first, middle, last: 정렬할 범위의 시작, 중간, 끝을 나타내는 반복자.
• comp: 요소를 비교하는 데 사용할 이진 함수 객체(optional).

예제:

#include <iostream>
#include <vector

>
#include <algorithm>

int main() {
    std::vector<int> vec = {9, 3, 1, 5, 4, 7, 6, 8, 2};
    std::partial_sort(vec.begin(), vec.begin() + 5, vec.end());

    std::cout << "Partially sorted vector: ";
    for (int n : vec) {
        std::cout << n << " ";
    }
    std::cout << std::endl;

    return 0;
}

std::merge()

std::merge 함수는 두 개의 정렬된 범위를 하나의 정렬된 범위로 병합합니다.

헤더 파일:

#include <algorithm>

사용법:

OutputIt merge(InputIt1 first1, InputIt1 last1, InputIt2 first2, InputIt2 last2, OutputIt d_first);
OutputIt merge(InputIt1 first1, InputIt1 last1, InputIt2 first2, InputIt2 last2, OutputIt d_first, Compare comp);

매개변수:

• first1, last1: 첫 번째 정렬된 범위의 시작과 끝을 나타내는 반복자.
• first2, last2: 두 번째 정렬된 범위의 시작과 끝을 나타내는 반복자.
• d_first: 병합된 범위의 시작을 나타내는 반복자.
• comp: 요소를 비교하는 데 사용할 이진 함수 객체(optional).

반환 값:

• 병합된 범위의 끝을 나타내는 반복자.

예제:

#include <iostream>
#include <vector>
#include <algorithm>

int main() {
    std::vector<int> vec1 = {1, 3, 5, 7};
    std::vector<int> vec2 = {2, 4, 6, 8};
    std::vector<int> result(vec1.size() + vec2.size());

    std::merge(vec1.begin(), vec1.end(), vec2.begin(), vec2.end(), result.begin());

    std::cout << "Merged vector: ";
    for (int n : result) {
        std::cout << n << " ";
    }
    std::cout << std::endl;

    return 0;
}

std::nth_element()

std::nth_element 함수는 범위의 n번째 요소를 정렬된 상태로 만듭니다. n번째 요소보다 작은 요소들은 앞쪽에, 큰 요소들은 뒤쪽에 위치하게 됩니다.

헤더 파일:

#include <algorithm>

사용법:

void nth_element(RandomIt first, RandomIt nth, RandomIt last);
void nth_element(RandomIt first, RandomIt nth, RandomIt last, Compare comp);

매개변수:

• first, nth, last: 정렬할 범위의 시작, n번째, 끝을 나타내는 반복자.
• comp: 요소를 비교하는 데 사용할 이진 함수 객체(optional).

예제:

#include <iostream>
#include <vector>
#include <algorithm>

int main() {
    std::vector<int> vec = {9, 3, 1, 5, 4, 7, 6, 8, 2};
    std::nth_element(vec.begin(), vec.begin() + 4, vec.end());

    std::cout << "Vector after nth_element: ";
    for (int n : vec) {
        std::cout << n << " ";
    }
    std::cout << std::endl;

    std::cout << "5th element: " << vec[4] << std::endl;

    return 0;
}

std::accumulate()

std::accumulate 함수는 범위의 모든 요소를 합산합니다.

헤더 파일:

#include <numeric>

사용법:

T accumulate(InputIt first, InputIt last, T init);
T accumulate(InputIt first, InputIt last, T init, BinaryOperation op);

매개변수:

• first, last: 합산할 범위의 시작과 끝을 나타내는 반복자.
• init: 초기 값.
• op: 합산을 수행할 이진 함수 객체(optional).

반환 값:

• 합산 결과.

예제:

#include <iostream>
#include <vector>
#include <numeric>

int main() {
    std::vector<int> vec = {1, 2, 3, 4, 5};
    int sum = std::accumulate(vec.begin(), vec.end(), 0);

    std::cout << "Sum of elements: " << sum << std::endl;

    return 0;
}

std::transform()

std::transform 함수는 범위의 각 요소에 함수 객체를 적용하여 결과를 저장합니다.

헤더 파일:

#include <algorithm>

사용법:

OutputIt transform(InputIt first, InputIt last, OutputIt d_first, UnaryOperation unary_op);
OutputIt transform(InputIt1 first1, InputIt1 last1, InputIt2 first2, OutputIt d_first, BinaryOperation binary_op);

매개변수:

• first, last: 변환할 범위의 시작과 끝을 나타내는 반복자.
• d_first: 결과를 저장할 범위의 시작을 나타내는 반복자.
• unary_op: 단항 함수 객체.
• first1, last1: 첫 번째 입력 범위의 시작과 끝을 나타내는 반복자.
• first2: 두 번째 입력 범위의 시작을 나타내는 반복자.
• binary_op: 이항 함수 객체.

반환 값:

• 결과 범위의 끝을 나타내는 반복자.

예제:

#include <iostream>
#include <vector>
#include <algorithm>

int main() {
    std::vector<int> vec = {1, 2, 3, 4, 5};
    std::vector<int> result(vec.size());

    std::transform(vec.begin(), vec.end(), result.begin(), [](int n) { return n * n; });

    std::cout << "Transformed vector: ";
    for (int n : result) {
        std::cout << n << " ";
    }
    std::cout << std::endl;

    return 0;
}

std::reduce()

std::reduce 함수는 범위의 모든 요소를 합산합니다. std::accumulate와 비슷하지만 병렬 처리를 지원합니다.

헤더 파일:

#include <numeric>

사용법:

T reduce(InputIt first, InputIt last);
T reduce(InputIt first, InputIt last, T init);
T reduce(InputIt first, InputIt last, T init, BinaryOperation binary_op);

매개변수:

• first, last: 합산할 범위의 시작과 끝을 나타내는 반복자.
• init: 초기 값.
• binary_op: 합산을 수행할 이진 함수 객체(optional).

반환 값:

• 합산 결과.

예제:

#include <iostream>
#include <vector>
#include <numeric>
#include <execution>

int main() {
    std::vector<int> vec = {1, 2, 3, 4, 5};
    int sum = std::reduce(std::execution::par, vec.begin(), vec.end(), 0);

    std::cout << "Sum of elements: " << sum << std::endl;

    return 0;
}

 

• std::reduce()는 std::accumulate() 함수와 유사한 역할을 하지만 병렬 처리를 지원하기 때문에 일반적으로 실행 속도가 더 빠르다