[C++] STL(표준 템플릿 라이브러리) 알고리즘이란?

STL(표준 템플릿 라이브러리)은 C++에서 제공하는 강력한 라이브러리로, 다양한 자료구조와 알고리즘을 제공합니다. STL 알고리즘은 컨테이너와 함께 사용되며, 일반적으로 다음과 같은 주요 범주로 나눌 수 있습니다.

 

1. 검색 알고리즘

• std::find: 주어진 범위에서 특정 값을 찾습니다.
• std::binary_search: 이진 탐색 알고리즘을 사용하여 요소가 있는지 확인합니다. 정렬된 컨테이너에서만 사용 가능합니다.
• std::lower_bound: 특정 값보다 작지 않은 첫 번째 위치를 찾습니다. 정렬된 컨테이너에서 사용됩니다.
• std::upper_bound: 특정 값보다 큰 첫 번째 위치를 찾습니다. 마찬가지로 정렬된 컨테이너에서 사용됩니다.

예시 코드

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

int main() {
    std::vector<int> v = {1, 2, 3, 4, 5, 6};

    // std::find
    auto it = std::find(v.begin(), v.end(), 3);
    if (it != v.end())
        std::cout << "3을 찾았습니다.\n";

    // std::binary_search (정렬된 컨테이너)
    if (std::binary_search(v.begin(), v.end(), 4))
        std::cout << "4가 있습니다.\n";

    return 0;
}

 

2. 정렬 알고리즘

• std::sort: 범위 내의 요소들을 정렬합니다.
• std::stable_sort: 안정적인 정렬을 수행합니다. 즉, 동일한 값의 상대적 순서는 유지됩니다.
• std::partial_sort: 부분적으로 정렬을 수행하여 상위 n개 요소만 정렬합니다.

예시 코드

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

int main() {
    std::vector<int> v = {3, 1, 4, 1, 5, 9};

    // std::sort
    std::sort(v.begin(), v.end());
    for (int n : v)
        std::cout << n << ' '; // 출력: 1 1 3 4 5 9

    return 0;
}

 

3. 변환 알고리즘

• std::transform: 두 범위의 요소에 대해 변환 작업을 수행합니다.
• std::copy: 범위 내의 요소를 다른 위치로 복사합니다.
• std::remove: 주어진 값과 일치하는 모든 요소를 제거하지만, 컨테이너의 크기는 줄지 않습니다. 실제로는 요소를 논리적으로 제거하며, 새 크기를 구하려면 erase와 함께 사용해야 합니다.

예시 코드

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

int main() {
    std::vector<int> v = {1, 2, 3, 4, 2};

    // std::remove
    v.erase(std::remove(v.begin(), v.end(), 2), v.end());
    for (int n : v)
        std::cout << n << ' '; // 출력: 1 3 4

    return 0;
}

 

4. 수치 알고리즘

• std::accumulate: 범위 내 요소들의 합을 계산합니다.
• std::adjacent_difference: 인접한 요소 간의 차이를 계산하여 새로운 범위로 저장합니다.
• std::inner_product: 두 범위의 요소에 대한 내적을 계산합니다.

예시 코드

#include <iostream>
#include <vector>
#include <numeric> // accumulate, inner_product, adjacent_difference

int main() {
    std::vector<int> v = {1, 2, 3, 4, 5};

    // std::accumulate: 합계 계산
    int sum = std::accumulate(v.begin(), v.end(), 0);
    std::cout << "합계: " << sum << '\n';  // 출력: 합계: 15

    // std::adjacent_difference: 인접한 요소 간의 차이 계산
    std::vector<int> diff(v.size());
    std::adjacent_difference(v.begin(), v.end(), diff.begin());
    std::cout << "인접한 차이: ";
    for (int n : diff)
        std::cout << n << ' ';  // 출력: 인접한 차이: 1 1 1 1 1
    std::cout << '\n';

    // std::inner_product: 두 벡터의 내적 계산
    std::vector<int> v2 = {5, 4, 3, 2, 1};
    int product = std::inner_product(v.begin(), v.end(), v2.begin(), 0);
    std::cout << "내적: " << product << '\n';  // 출력: 내적: 35

    return 0;
}

 

5. 집합 알고리즘

• std::set_union: 두 집합의 합집합을 만듭니다.
• std::set_intersection: 두 집합의 교집합을 만듭니다.
• std::set_difference: 두 집합의 차집합을 만듭니다.

예시 코드

#include <iostream>
#include <vector>
#include <algorithm> // set_union, set_intersection, set_difference

int main() {
    std::vector<int> v1 = {1, 2, 3, 4, 5};
    std::vector<int> v2 = {3, 4, 5, 6, 7};

    std::vector<int> union_result, intersection_result, difference_result;

    // std::set_union: 합집합
    std::set_union(v1.begin(), v1.end(), v2.begin(), v2.end(),
                   std::back_inserter(union_result));
    std::cout << "합집합: ";
    for (int n : union_result)
        std::cout << n << ' ';  // 출력: 합집합: 1 2 3 4 5 6 7
    std::cout << '\n';

    // std::set_intersection: 교집합
    std::set_intersection(v1.begin(), v1.end(), v2.begin(), v2.end(),
                          std::back_inserter(intersection_result));
    std::cout << "교집합: ";
    for (int n : intersection_result)
        std::cout << n << ' ';  // 출력: 교집합: 3 4 5
    std::cout << '\n';

    // std::set_difference: 차집합 (v1 - v2)
    std::set_difference(v1.begin(), v1.end(), v2.begin(), v2.end(),
                        std::back_inserter(difference_result));
    std::cout << "차집합 (v1 - v2): ";
    for (int n : difference_result)
        std::cout << n << ' ';  // 출력: 차집합: 1 2
    std::cout << '\n';

    return 0;
}

 

6. 유틸리티 알고리즘

• std::for_each: 범위 내의 각 요소에 대해 작업을 수행합니다.
• std::count: 범위 내에서 특정 값이 나타나는 횟수를 셉니다.
• std::max_element: 범위 내에서 최대 요소를 찾습니다.

예시 코드

#include <iostream>
#include <vector>
#include <algorithm> // for_each, count, max_element

int main() {
    std::vector<int> v = {1, 2, 3, 4, 5, 5};

    // std::for_each: 각 요소에 대해 작업 수행
    std::cout << "벡터의 요소: ";
    std::for_each(v.begin(), v.end(), [](int n) {
        std::cout << n << ' ';
    });  // 출력: 벡터의 요소: 1 2 3 4 5 5
    std::cout << '\n';

    // std::count: 특정 값의 개수 세기
    int count_5 = std::count(v.begin(), v.end(), 5);
    std::cout << "5의 개수: " << count_5 << '\n';  // 출력: 5의 개수: 2

    // std::max_element: 최대 요소 찾기
    auto max_it = std::max_element(v.begin(), v.end());
    std::cout << "최대 요소: " << *max_it << '\n';  // 출력: 최대 요소: 5

    return 0;
}

C++의 STL(표준 템플릿 라이브러리)에 포함된 알고리즘은 다양한 작업을 강력하고 효율적으로 처리할 수 있도록 도와줍니다. 컨테이너와 반복자를 활용해 범용적이고 재사용 가능한 코드를 쉽게 작성할 수 있으며, 그 결과 코드의 가독성도 좋아지고 유지보수도 수월해집니다.

또한 STL 알고리즘은 함수 템플릿으로 제공되기 때문에, 다양한 자료형에 적용할 수 있어 복잡한 작업도 단순하게 해결할 수 있습니다. 이 글에서 소개한 알고리즘들을 활용해 기본적인 사용법을 익힌 뒤, 더 복잡한 문제에 응용해보면 좋을 것입니다.

STL 알고리즘을 잘 활용하면 반복되는 작업을 줄이고, 성능을 높이면서도 간결하고 효율적인 코드를 작성할 수 있는 큰 장점을 누릴 수 있습니다.