C++ STL 알고리즘 핵심 정리 및 활용 가이드

1. 시퀀스 비변경 알고리즘 (Non-modifying Sequence Algorithms)

이 알고리즘들은 컨테이너의 원소를 읽기만 할 뿐, 메모리 상의 원소 값을 직접 수정하지 않습니다.

1.1 원소 탐색 (find, find_if, find_end)

  • find: 특정 값과 일치하는 첫 번째 원소의 반복자를 반환합니다. 없으면 end를 반환합니다.
  • find_if: 주어진 조건자(predicate)를 만족하는 첫 번째 원소를 탐색합니다.
  • find_end: 부분 시퀀스가 마지막으로 등장하는 위치를 찾습니다.
#include <iostream>
#include <vector>
#include <algorithm>

int main() {
    std::vector<int> dataset = {12, 24, 36, 48, 60};

    // 특정 값(36) 탐색
    auto pos = std::find(dataset.begin(), dataset.end(), 36);
    if (pos != dataset.end()) {
        std::cout << "Target located: " << *pos << "\n";
    }

    // 40보다 큰 첫 번째 원소 탐색
    auto cond_pos = std::find_if(dataset.begin(), dataset.end(), [](int val) {
        return val > 40;
    });
    if (cond_pos != dataset.end()) {
        std::cout << "First element > 40: " << *cond_pos << "\n";
    }

    // 부분 시퀀스 탐색
    std::vector<int> subseq = {24, 36};
    auto sub_pos = std::find_end(dataset.begin(), dataset.end(), subseq.begin(), subseq.end());
    if (sub_pos != dataset.end()) {
        std::cout << "Subsequence found at index: " << (sub_pos - dataset.begin()) << "\n";
    }
    return 0;
}

1.2 개수 집계 (count, count_if)

  • count: 특정 값과 동일한 원소의 개수를 셉니다.
  • count_if: 조건자를 만족하는 원소의 개수를 반환합니다.
std::vector<int> scores = {85, 90, 85, 95, 85, 100};

// 85점인 원소의 개수
int target_count = std::count(scores.begin(), scores.end(), 85); 

// 90점 이상인 원소의 개수
int high_scores = std::count_if(scores.begin(), scores.end(), [](int s) { 
    return s >= 90; 
});

1.3 순회 및 적용 (for_each)

지정된 범위 내의 모든 원소에 대해 특정 함수나 람다식을 적용합니다.

std::vector<int> prices = {100, 200, 300};
std::for_each(prices.begin(), prices.end(), [](int& p) { 
    p = static_cast<int>(p * 1.1); // 10% 세금 부과
});

1.4 시퀀스 비교 (equal, mismatch)

  • equal: 두 범위의 원소들이 서로 동일한지 여부를 bool로 반환합니다.
  • mismatch: 두 범위에서 처음으로 일치하지 않는 원소의 반복자 쌍(pair)을 반환합니다.
std::vector<int> seq1 = {10, 20, 30};
std::vector<int> seq2 = {10, 20, 40};
std::vector<int> seq3 = {10, 20, 30, 50};

bool is_same = std::equal(seq1.begin(), seq1.end(), seq2.begin());

auto diff = std::mismatch(seq1.begin(), seq1.end(), seq3.begin());
if (diff.first != seq1.end()) {
    std::cout << "Mismatch found.\n";
}

1.5 조건부 전체 검사 (all_of, any_of, none_of)

범위 내의 원소들이 조건을 모두 만족하는지, 하나라도 만족하는지, 혹은 전혀 만족하지 않는지를 확인합니다.

std::vector<int> temperatures = {22, 24, 26, 28};

bool all_warm = std::all_of(temperatures.begin(), temperatures.end(), [](int t) { return t > 20; });
bool has_freezing = std::any_of(temperatures.begin(), temperatures.end(), [](int t) { return t < 0; });
bool no_extreme = std::none_of(temperatures.begin(), temperatures.end(), [](int t) { return t > 40; });

2. 시퀀스 변경 알고리즘 (Modifying Sequence Algorithms)

컨테이너의 원소 값을 직접 수정하거나, 원소의 위치를 변경하는 알고리즘들입니다.

2.1 복사 (copy, copy_if)

  • copy: 원본 범위의 원소들을 대상 위치로 복사합니다.
  • copy_if: 조건을 만족하는 원소들만 선택적으로 복사합니다.
std::vector<int> source = {11, 22, 33, 44, 55};
std::vector<int> destination(5);

std::copy(source.begin(), source.end(), destination.begin());

std::vector<int> odd_numbers;
std::copy_if(source.begin(), source.end(), std::back_inserter(odd_numbers), [](int n) {
    return n % 2 != 0;
});

참고: std::back_inserter를 사용하면 대상 컨테이너의 크기를 미리 할당하지 않아도 push_back이 자동으로 호출됩니다.

2.2 변환 (transform)

각 원소에 연산을 적용한 결과로 새로운 시퀀스를 생성합니다.

std::vector<int> base = {2, 4, 6};
std::vector<int> squared(base.size());

// 단일 인자 변환 (제곱)
std::transform(base.begin(), base.end(), squared.begin(), [](int n) {
    return n * n;
});

// 이중 인자 변환 (두 벡터의 합)
std::vector<int> weights = {10, 20, 30};
std::vector<int> combined(base.size());
std::transform(base.begin(), base.end(), weights.begin(), combined.begin(), [](int a, int b) {
    return a + b;
});

2.3 원소 교체 (replace, replace_if, replace_copy)

  • replace: 특정 값을 다른 값으로 일괄 변경합니다.
  • replace_if: 조건을 만족하는 원소의 값을 변경합니다.
  • replace_copy: 원본은 유지한 채, 복사본에서 특정 값을 교체합니다.
std::vector<int> data = {1, 2, 3, 2, 5};

std::replace(data.begin(), data.end(), 2, 20); 

std::replace_if(data.begin(), data.end(), [](int x) { return x > 10; }, 0);

std::vector<int> copied_data;
std::replace_copy(data.begin(), data.end(), std::back_inserter(copied_data), 3, 300);

2.4 제거 (remove, remove_if)

특정 원소를 컨테이너의 끝으로 이동시켜 논리적으로 제거합니다. 실제 메모리 해제를 위해서는 erase와 함께 사용해야 합니다(Erase-Remove Idiom).

std::vector<int> items = {10, 20, 30, 20, 40};

// 논리적 제거
auto logical_end = std::remove(items.begin(), items.end(), 20);

// 물리적 제거 (컨테이너 크기 축소)
items.erase(logical_end, items.end());

// 람다식을 활용한 짝수 제거
items = {1, 2, 3, 4, 5};
items.erase(
    std::remove_if(items.begin(), items.end(), [](int x) { return x % 2 == 0; }), 
    items.end()
);

2.5 중복 제거 (unique)

연속된 중복 원소를 하나로 축약합니다. 일반적으로 정렬 후 erase와 결합하여 사용합니다.

std::vector<int> raw = {1, 1, 2, 2, 3, 4, 4, 5};
auto last_unique = std::unique(raw.begin(), raw.end());
raw.erase(last_unique, raw.end());

2.6 순서 변경 (reverse, rotate, shuffle)

  • reverse: 원소들의 순서를 거꾸로 뒤집습니다.
  • rotate: 지정한 중간 원소를 시작으로 시퀀스를 회전시킵니다.
  • shuffle: 난수 생성기를 사용하여 원소들을 무작위로 섞습니다.
#include <random>

std::vector<int> seq = {1, 2, 3, 4, 5};
std::reverse(seq.begin(), seq.end()); 

std::rotate(seq.begin(), seq.begin() + 2, seq.end()); 

std::random_device rd;
std::mt19937 gen(rd());
std::shuffle(seq.begin(), seq.end(), gen);

3. 정렬 및 관련 알고리즘 (Sorting and Related Algorithms)

3.1 정렬 (sort, stable_sort, partial_sort)

  • sort: 평균 O(n log n) 시간 복잡도를 가지는 빠른 정렬(Introsort)을 수행합니다. 불안정 정렬입니다.
  • stable_sort: 값이 동일한 원소들의 기존 상대적 순서를 보존하는 안정 정렬을 수행합니다.
  • partial_sort: 상위 N개의 원소만 정렬하여 앞부분에 배치합니다.
std::vector<int> nums = {5, 3, 1, 4, 2};
std::sort(nums.begin(), nums.end()); 
std::sort(nums.begin(), nums.end(), std::greater<int>()); 

std::vector<std::pair<int, int>> pairs = {{1, 2}, {2, 1}, {1, 1}};
std::stable_sort(pairs.begin(), pairs.end(), [](const auto& a, const auto& b) {
    return a.first < b.first; 
});

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

3.2 N번째 원소 찾기 (nth_element)

지정한 인덱스에 정렬되었을 때 와야 할 원소를 위치시키고, 그 왼쪽은 더 작은 값, 오른쪽은 더 큰 값들로 분할합니다.

std::vector<int> values = {8, 4, 2, 9, 1, 7};
// 정렬 시 인덱스 2에 위치해야 할 값(3번째로 작은 값)을 찾음
std::nth_element(values.begin(), values.begin() + 2, values.end());

3.3 이진 탐색 (binary_search, lower_bound, upper_bound)

반드시 사전 정렬된 컨테이너에서만 사용할 수 있습니다.

  • binary_search: 원소의 존재 여부를 bool로 반환합니다.
  • lower_bound: 특정 값 이상인 첫 번째 원소의 반복자를 반환합니다.
  • upper_bound: 특정 값 초과인 첫 번째 원소의 반복자를 반환합니다.
std::vector<int> sorted_data = {10, 20, 20, 30, 50};

bool exists = std::binary_search(sorted_data.begin(), sorted_data.end(), 20);

auto lb = std::lower_bound(sorted_data.begin(), sorted_data.end(), 20);
auto ub = std::upper_bound(sorted_data.begin(), sorted_data.end(), 20);

3.4 병합 (merge)

이미 정렬된 두 시퀀스를 하나의 정렬된 시퀀스로 합칩니다.

std::vector<int> group_a = {1, 3, 5};
std::vector<int> group_b = {2, 4, 6};
std::vector<int> merged_group(group_a.size() + group_b.size());

std::merge(group_a.begin(), group_a.end(), group_b.begin(), group_b.end(), merged_group.begin());

4. 힙 알고리즘 (Heap Algorithms)

STL은 범위를 힙(Heap) 자료구조처럼 다룰 수 있는 알고리즘을 제공합니다.

std::vector<int> heap_data = {4, 1, 3, 2, 5};
std::make_heap(heap_data.begin(), heap_data.end()); 

heap_data.push_back(6);
std::push_heap(heap_data.begin(), heap_data.end()); 

std::pop_heap(heap_data.begin(), heap_data.end()); 
int max_val = heap_data.back(); 
heap_data.pop_back(); 

std::sort_heap(heap_data.begin(), heap_data.end());

5. 최솟값/최댓값 알고리즘 (Min/Max Algorithms)

5.1 기본 비교 (min, max)

int a = 15, b = 25;
int minimum = std::min(a, b); 
int maximum = std::max(a, b); 

auto min_list = std::min({40, 20, 80, 50, 10});

5.2 범위 내 극값 탐색 (min_element, max_element, minmax_element)

std::vector<int> metrics = {33, 11, 44, 22, 55};

auto min_it = std::min_element(metrics.begin(), metrics.end()); 
auto max_it = std::max_element(metrics.begin(), metrics.end()); 

auto minmax_pair = std::minmax_element(metrics.begin(), metrics.end());
// minmax_pair.first는 최솟값, second는 최댓값을 가리킴

6. 수치 알고리즘 (Numeric Algorithms)

<numeric> 헤더에 포함수치 연산과 관련된 알고리즘들입니다.

6.1 누적 및 내적 (accumulate, inner_product)

#include <numeric>

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

std::vector<int> vec_x = {1, 2, 3};
std::vector<int> vec_y = {4, 5, 6};
int dot_product = std::inner_product(vec_x.begin(), vec_x.end(), vec_y.begin(), 0);

6.2 시퀀스 생성 및 누적 (iota, partial_sum, adjacent_difference)

std::vector<int> sequence(5);
std::iota(sequence.begin(), sequence.end(), 10); // 10, 11, 12, 13, 14

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

std::partial_sum(src.begin(), src.end(), dst.begin()); // {1, 3, 6, 10, 15}
std::adjacent_difference(src.begin(), src.end(), dst.begin()); // {1, 1, 1, 1, 1}

7. 기타 유틸리티 알고리즘

7.1 값 생성 (generate, generate_n)

std::vector<int> gen_vec(5);
int counter = 0;
std::generate(gen_vec.begin(), gen_vec.end(), [&counter]() { return counter++; });

std::generate_n(gen_vec.begin(), 3, [&counter]() { return counter * 10; });

7.2 집합 연산 (includes, set_union, set_intersection 등)

집합 연산을 수행하기 위해서는 입력 시퀀스가 반드시 정렬되어 있어야 합니다.

std::vector<int> set_a = {1, 2, 3, 4, 5};
std::vector<int> set_b = {3, 4, 5, 6, 7};
std::vector<int> result;

bool is_subset = std::includes(set_a.begin(), set_a.end(), set_b.begin(), set_b.begin() + 2);

std::set_union(set_a.begin(), set_a.end(), set_b.begin(), set_b.end(), std::back_inserter(result));

result.clear();
std::set_intersection(set_a.begin(), set_a.end(), set_b.begin(), set_b.end(), std::back_inserter(result));

result.clear();
std::set_difference(set_a.begin(), set_a.end(), set_b.begin(), set_b.end(), std::back_inserter(result));

result.clear();
std::set_symmetric_difference(set_a.begin(), set_a.end(), set_b.begin(), set_b.end(), std::back_inserter(result));

8. 자주 묻는 질문 (FAQ)

  1. sort와 stable_sort의 근본적인 차이는 무엇인가?
    • sort는 Introsort(퀵정렬, 힙정렬, 삽입정렬의 하이브리드)를 기반으로 하며 평균 O(n log n)의 성능을 내지만, 값이 같은 원소들의 상대적 순서가 바뀔 수 있는 불안정 정렬입니다.
    • stable_sort는 병합 정렬을 기반으로 하여 동일 값에 대한 기존 순서를 보장(안정 정렬)하지만, 추가적인 메모리 할당이 필요할 수 있습니다.
  2. 왜 remove 알고리즘은 erase와 함께 사용해야 하는가?
    • std::remove는 삭제 대상 원소들을 컨테이너의 뒤쪽으로 이동시키고, 유지해야 할 원소들의 새로운 논리적 끝 반복자만 반환할 뿐 실제 컨테이너의 메모리 크기를 줄이지 않습니다. 따라서 container.erase(new_end, container.end())를 호출하여 물리적으로 메모리를 해제해야 합니다.
  3. 사전 정렬이 필수적인 알고리즘들은 어떤 것들이 있는가?
    • 이진 탐색 계열(binary_search, lower_bound, upper_bound), 집합 연산(set_union, set_intersection 등), 그리고 merge, includes 등은 O(log n) 또는 O(n)의 효율적인 연산을 위해 입력 데이터가 정렬되어 있음을 전제로 합니다.

태그: C++ STL algorithm StandardTemplateLibrary C++11

7월 24일 07:36에 게시됨

인기 태그

©2026 괴물 클럽