C++ STL 알고리즘 활용 가이드

C++ 표준 템플릿 라이브러리(STL)는 다양한 알고리즘을 제공하여 데이터 처리 및 조작을 효율적으로 수행할 수 있도록 돕습니다. 이 가이드에서는 STL 알고리즘을 기능별로 분류하고 사용법을 설명합니다.

1. 비수정 순서 알고리즘

이 알고리즘들은 연산 대상 컨테이너의 요소를 변경하지 않습니다.

1.1 find 및 find_if

  • find(begin, end, value): value와 동일한 첫 번째 요소를 찾습니다. 해당 요소의 반복자를 반환하며, 찾지 못하면 end 반복자를 반환합니다.
  • find_if(begin, end, predicate): 주어진 술어(predicate)를 만족하는 첫 번째 요소를 찾습니다.
  • find_end(begin, end, sub_begin, sub_end): 두 번째 범위([sub_begin, sub_end))가 첫 번째 범위([begin, end))에 마지막으로 나타나는 위치를 찾습니다.

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

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

    // 값 5 찾기
    auto it = std::find(numbers.begin(), numbers.end(), 5);
    if (it != numbers.end()) {
        std::cout << "Found: " << *it << std::endl; // 출력: Found: 5
    }

    // 6보다 큰 첫 번째 요소 찾기
    auto it2 = std::find_if(numbers.begin(), numbers.end(), [](int x) {
        return x > 6;
    });
    std::cout << "First element > 6: " << *it2 << std::endl; // 출력: First element > 6: 7

    // 부분 시퀀스 찾기
    std::vector<int> sub_sequence = {3, 5};
    auto it3 = std::find_end(numbers.begin(), numbers.end(), sub_sequence.begin(), sub_sequence.end());
    if (it3 != numbers.end()) {
        // std::distance를 사용하여 인덱스 계산
        std::cout << "Subsequence starts at index: " << std::distance(numbers.begin(), it3) << std::endl; // 출력: Subsequence starts at index: 1
    }

    return 0;
}
    

1.2 count 및 count_if

  • count(begin, end, value): 범위 내에서 value와 동일한 요소의 개수를 셉니다.
  • count_if(begin, end, predicate): 주어진 술어를 만족하는 요소의 개수를 셉니다.

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

int main() {
    std::vector<int> vec = {1, 2, 3, 2, 4, 2};
    int count_of_2 = std::count(vec.begin(), vec.end(), 2); // 2의 개수, 결과: 3
    
    int even_count = std::count_if(vec.begin(), vec.end(), [](int x) { 
        return x % 2 == 0; 
    }); // 짝수의 개수, 결과: 4
    std::cout << "Count of 2: " << count_of_2 << ", Even count: " << even_count << std::endl; // 출력: Count of 2: 3, Even count: 4

    return 0;
}
    

1.3 for_each

범위 내의 각 요소에 주어진 함수(람다 포함)를 적용합니다.


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

int main() {
    std::vector<int> vec = {1, 2, 3, 4, 5};
    std::for_each(vec.begin(), vec.end(), [](int& x) { 
        x *= 2; // 각 요소를 2배로 만듭니다.
    });
    // 이제 vec는 {2, 4, 6, 8, 10}이 됩니다.
    std::cout << "After for_each: ";
    for(int val : vec) {
        std::cout << val << " "; // 출력: 2 4 6 8 10
    }
    std::cout << std::endl;

    return 0;
}
    

1.4 equal 및 mismatch

  • equal(b1, e1, b2): 첫 번째 범위([b1, e1))와 두 번째 범위([b2, b2 + (e1 - b1)))가 같은지 비교합니다.
  • mismatch(b1, e1, b2): 두 범위에서 처음으로 일치하지 않는 요소 쌍을 반환합니다 (std::pair 형태).

#include <vector>
#include <algorithm>
#include <iostream>
#include <iterator> // std::distance 사용

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

    // a와 b의 첫 3개 요소 비교
    bool is_equal = std::equal(a.begin(), a.end(), b.begin());
    std::cout << "a == b (first 3 elements)? " << std::boolalpha << is_equal << std::endl; // 출력: a == b (first 3 elements)? false

    // a와 c의 첫 번째 불일치 요소 찾기
    auto mis = std::mismatch(a.begin(), a.end(), c.begin());
    if (mis.first != a.end()) {
        // a와 c의 처음 3개 요소가 동일하므로 이 블록은 실행되지 않습니다.
        std::cout << "Mismatch found: " << *mis.first << " vs " << *mis.second << std::endl; 
    } else {
         std::cout << "No mismatch found within the range of 'a'." << std::endl; // 출력: No mismatch found within the range of 'a'.
    }
    
    // a와 c의 첫 번째 불일치 요소 찾기 (전체 비교)
    auto mis_full = std::mismatch(a.begin(), a.end(), c.begin(), c.begin() + a.size());
     if (mis_full.first != a.end()) {
        std::cout << "Full mismatch found: " << *mis_full.first << " vs " << *mis_full.second << std::endl; 
    }

    return 0;
}
    

1.5 all_of, any_of, none_of

범위 내의 모든 요소, 어떤 요소 또는 어떤 요소도 특정 조건을 만족하는지 검사합니다.


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

int main() {
    std::vector<int> vec = {2, 4, 6, 8};
    bool all_even = std::all_of(vec.begin(), vec.end(), [](int x) { 
        return x % 2 == 0; 
    }); // 모두 짝수인가? true
    
    bool any_odd = std::any_of(vec.begin(), vec.end(), [](int x) { 
        return x % 2 != 0; 
    }); // 홀수가 하나라도 있는가? false
    
    bool none_negative = std::none_of(vec.begin(), vec.end(), [](int x) { 
        return x < 0; 
    }); // 음수가 하나도 없는가? true

    std::cout << std::boolalpha;
    std::cout << "All even: " << all_even << std::endl;      // 출력: All even: true
    std::cout << "Any odd: " << any_odd << std::endl;        // 출력: Any odd: false
    std::cout << "None negative: " << none_negative << std::endl; // 출력: None negative: true

    return 0;
}
    

2. 수정 순서 알고리즘

이 알고리즘들은 연산 대상 컨테이너의 요소를 변경합니다.

2.1 copy 및 copy_if

  • copy(begin, end, dest): [begin, end) 범위의 요소를 dest가 가리키는 위치부터 복사합니다.
  • copy_if(begin, end, dest, predicate): 술어를 만족하는 요소만 dest가 가리키는 위치부터 복사합니다.

#include <vector>
#include <algorithm>
#include <iterator> // std::back_inserter
#include <iostream>

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

    // 모든 요소 복사
    std::copy(source.begin(), source.end(), destination.begin()); 
    // destination: {1, 2, 3, 4, 5}

    // 짝수만 새 컨테이너로 복사
    std::vector<int> evens;
    std::copy_if(source.begin(), source.end(), std::back_inserter(evens), [](int x) {
        return x % 2 == 0;
    }); 
    // evens: {2, 4}

    std::cout << "Destination after copy: ";
    for(int val : destination) std::cout << val << " "; // 출력: 1 2 3 4 5
    std::cout << std::endl;

    std::cout << "Evens vector: ";
    for(int val : evens) std::cout << val << " "; // 출력: 2 4
    std::cout << std::endl;

    return 0;
}
    

참고: std::back_inserter(dest)는 dest.push_back()을 호출하므로, 미리 공간을 할당할 필요가 없습니다.

2.2 transform

범위 내 각 요소에 함수를 적용하고, 그 결과를 다른 범위에 저장합니다. 단일 범위 또는 두 개의 입력 범위를 사용할 수 있습니다.


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

int main() {
    std::vector<int> nums = {1, 2, 3};
    std::vector<int> squares(nums.size());

    // 제곱 계산 (단일 입력 범위)
    std::transform(nums.begin(), nums.end(), squares.begin(), [](int x) {
        return x * x;
    }); 
    // squares: {1, 4, 9}

    // 두 컨테이너의 요소 덧셈 (이중 입력 범위)
    std::vector<int> a = {1, 2, 3};
    std::vector<int> b = {4, 5, 6};
    std::vector<int> sum(a.size());
    std::transform(a.begin(), a.end(), b.begin(), sum.begin(), [](int x, int y) {
        return x + y;
    }); 
    // sum: {5, 7, 9}

    std::cout << "Squares: ";
    for(int val : squares) std::cout << val << " "; // 출력: 1 4 9
    std::cout << std::endl;

    std::cout << "Sum: ";
    for(int val : sum) std::cout << val << " "; // 출력: 5 7 9
    std::cout << std::endl;

    return 0;
}
    

2.3 replace, replace_if 및 replace_copy

  • replace(begin, end, old_val, new_val): 범위 내의 모든 old_val을 new_val로 변경합니다.
  • replace_if(begin, end, predicate, new_val): 술어를 만족하는 요소를 new_val로 변경합니다.
  • replace_copy(begin, end, dest, old_val, new_val): 복사하면서 old_val을 new_val로 변경합니다 (원본 컨테이너는 변경되지 않음).

#include <vector>
#include <algorithm>
#include <iterator> // std::back_inserter
#include <iostream>

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

    // 모든 2를 20으로 변경
    std::replace(nums.begin(), nums.end(), 2, 20); 
    // nums: {1, 20, 3, 20, 5}

    // 10보다 큰 요소를 0으로 변경
    std::replace_if(nums.begin(), nums.end(), [](int x) {
        return x > 10;
    }, 0); 
    // nums: {1, 0, 3, 0, 5}

    // 3을 300으로 변경하며 복사 (원본 nums는 변경되지 않음)
    std::vector<int> result_vec;
    std::replace_copy(nums.begin(), nums.end(), std::back_inserter(result_vec), 3, 300); 
    // result_vec: {1, 0, 300, 0, 5}

    std::cout << "Nums after replace/replace_if: ";
    for(int val : nums) std::cout << val << " "; // 출력: 1 0 3 0 5
    std::cout << std::endl;

    std::cout << "Result vector after replace_copy: ";
    for(int val : result_vec) std::cout << val << " "; // 출력: 1 0 300 0 5
    std::cout << std::endl;

    return 0;
}
    

2.4 remove, remove_if 및 erase

  • remove(begin, end, value): 범위 내의 value와 동일한 요소들을 컨테이너의 뒤쪽으로 "이동"시키고, 유효한 새 논리적 끝을 나타내는 반복자를 반환합니다. 실제로 요소를 삭제하지 않습니다. erase와 함께 사용해야 합니다.
  • remove_if(begin, end, predicate): 술어를 만족하는 요소들을 뒤쪽으로 이동시킵니다.

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

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

    // 모든 2를 논리적으로 제거 (뒤로 이동)
    auto new_end_it = std::remove(nums.begin(), nums.end(), 2); 
    // nums의 내용은 {1, 3, 4, ?, ?} 와 같이 변환됩니다. (물리적 크기는 그대로)

    // 실제로 요소를 제거
    nums.erase(new_end_it, nums.end()); 
    // nums: {1, 3, 4}

    // 람다를 사용하여 짝수 제거
    nums = {1, 2, 3, 4, 5}; // 초기화
    nums.erase(std::remove_if(nums.begin(), nums.end(), [](int x) {
        return x % 2 == 0; // 짝수이면 true 반환
    }), nums.end()); 
    // nums: {1, 3, 5}

    std::cout << "Nums after remove and erase: ";
    for(int val : nums) std::cout << val << " "; // 출력: 1 3 4 (첫 번째 remove/erase 후)
    std::cout << std::endl;

    nums = {1, 2, 3, 4, 5}; // 다시 초기화
    nums.erase(std::remove_if(nums.begin(), nums.end(), [](int x) { return x % 2 == 0; }), nums.end());
    std::cout << "Nums after remove_if and erase (evens removed): ";
    for(int val : nums) std::cout << val << " "; // 출력: 1 3 5
    std::cout << std::endl;

    return 0;
}
    

2.5 unique

연속된 중복 요소를 제거하고, 새로운 논리적 끝을 가리키는 반복자를 반환합니다. 일반적으로 erase와 함께 사용됩니다.


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

int main() {
    std::vector<int> vec = {1, 1, 2, 2, 3, 3, 3, 4, 5};
    // 연속된 중복 제거
    auto last_unique = std::unique(vec.begin(), vec.end());
    // vec의 내용은 {1, 2, 3, 4, 5, ?, ?, ?, ?} 와 같이 변환됩니다.
    
    // 실제 요소 제거
    vec.erase(last_unique, vec.end()); 
    // vec는 {1, 2, 3, 4, 5}가 됩니다.

    std::cout << "After unique and erase: ";
    for(int val : vec) std::cout << val << " "; // 출력: 1 2 3 4 5
    std::cout << std::endl;

    return 0;
}
    

2.6 reverse

범위 내 요소의 순서를 뒤집습니다.


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

int main() {
    std::vector<int> vec = {1, 2, 3, 4, 5};
    std::reverse(vec.begin(), vec.end()); 
    // vec는 {5, 4, 3, 2, 1}이 됩니다.

    std::cout << "After reverse: ";
    for(int val : vec) std::cout << val << " "; // 출력: 5 4 3 2 1
    std::cout << std::endl;

    return 0;
}
    

2.7 rotate

범위 내의 요소를 회전시켜, 주어진 중간 요소가 새로운 첫 번째 요소가 되도록 합니다.


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

int main() {
    std::vector<int> vec = {1, 2, 3, 4, 5};
    // 세 번째 요소(값 3)를 새로운 시작점으로 회전
    std::rotate(vec.begin(), vec.begin() + 2, vec.end()); 
    // vec는 {3, 4, 5, 1, 2}가 됩니다.

    std::cout << "After rotate: ";
    for(int val : vec) std::cout << val << " "; // 출력: 3 4 5 1 2
    std::cout << std::endl;

    return 0;
}
    

2.8 shuffle

범위 내 요소의 순서를 무작위로 섞습니다 (C++11 이상 필요).


#include <vector>
#include <algorithm>
#include <random> // 난수 생성기
#include <iostream>

int main() {
    std::vector<int> vec = {1, 2, 3, 4, 5};
    
    // 난수 생성 엔진 설정
    std::random_device rd;
    std::mt19937 g(rd()); // Mersenne Twister 엔진

    std::shuffle(vec.begin(), vec.end(), g); 
    // vec의 요소 순서가 무작위로 변경됩니다.

    std::cout << "After shuffle: ";
    for(int val : vec) std::cout << val << " "; // 예시 출력: 3 1 5 2 4 (실행할 때마다 달라짐)
    std::cout << std::endl;

    return 0;
}
    

3. 정렬 및 관련 알고리즘

3.1 sort, stable_sort 및 partial_sort

  • sort(begin, end): 요소를 정렬합니다 (일반적으로 퀵 정렬 기반). 불안정 정렬이며, 평균 시간 복잡도는 O(n log n)입니다.
  • stable_sort(begin, end): 안정 정렬을 수행합니다 (동일한 요소의 상대적 순서가 유지됨).
  • partial_sort(begin, mid, end): 범위 [begin, end)에서 가장 작은 mid - begin개의 요소를 찾아 [begin, mid) 범위에 정렬된 상태로 저장합니다.

#include <vector>
#include <algorithm>
#include <functional> // std::greater
#include <iostream>
#include <utility> // std::pair

int main() {
    // 기본 정렬 (오름차순)
    std::vector<int> vec1 = {5, 3, 1, 4, 2};
    std::sort(vec1.begin(), vec1.end()); 
    // vec1: {1, 2, 3, 4, 5}

    // 내림차순 정렬
    std::vector<int> vec2 = {5, 3, 1, 4, 2};
    std::sort(vec2.begin(), vec2.end(), std::greater<int>());
    // vec2: {5, 4, 3, 2, 1}

    // 사용자 정의 비교 함수 (람다)
    std::vector<int> vec3 = {5, 3, 1, 4, 2};
    std::sort(vec3.begin(), vec3.end(), [](int a, int b) { 
        return a < b; // 오름차순
    });

    // stable_sort 예제
    std::vector<std::pair<int, int>> pairs = {{1, 2}, {2, 1}, {1, 1}, {2, 2}};
    std::stable_sort(pairs.begin(), pairs.end(), [](const auto& a, const auto& b) {
        return a.first < b.first; // first 기준으로 안정 정렬
    });
    // pairs: {{1, 2}, {1, 1}, {2, 1}, {2, 2}} (1,2와 1,1의 순서 유지)

    // partial_sort 예제
    std::vector<int> vec_ps = {5, 3, 1, 4, 2, 6};
    // 가장 작은 3개의 요소를 찾아 앞 3개 위치에 정렬
    std::partial_sort(vec_ps.begin(), vec_ps.begin() + 3, vec_ps.end());
    // vec_ps: {1, 2, 3, ?, ?, ?} (나머지 요소는 정렬되지 않음)

    std::cout << "Sorted vec1: ";
    for(int val : vec1) std::cout << val << " "; // 출력: 1 2 3 4 5
    std::cout << std::endl;

    std::cout << "Sorted vec2 (desc): ";
    for(int val : vec2) std::cout << val << " "; // 출력: 5 4 3 2 1
    std::cout << std::endl;

    std::cout << "Partially sorted vec_ps: ";
    for(int val : vec_ps) std::cout << val << " "; // 출력: 1 2 3 4 2 6 (예시)
    std::cout << std::endl;

    return 0;
}
    

3.2 nth_element

범위 내에서 k번째 요소를 찾아 올바른 위치에 배치합니다. 이 요소의 왼쪽에는 이보다 작거나 같은 요소들이, 오른쪽에는 이보다 크거나 같은 요소들이 위치하게 됩니다. (완전 정렬은 아님)


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

int main() {
    std::vector<int> vec = {5, 3, 1, 4, 2, 6};
    // 세 번째로 작은 요소 (인덱스 2)를 찾습니다.
    std::nth_element(vec.begin(), vec.begin() + 2, vec.end());
    
    // 이제 vec[2]는 3이 됩니다. vec[0], vec[1]은 3보다 작거나 같고, 
    // vec[3], vec[4], vec[5]는 3보다 크거나 같습니다.
    std::cout << "Element at index 2 after nth_element: " << vec[2] << std::endl; // 출력: 3
    
    std::cout << "Vector after nth_element: ";
    for(int val : vec) std::cout << val << " "; // 예시 출력: 1 2 3 6 5 4 (순서는 보장되지 않음)
    std::cout << std::endl;

    return 0;
}
    

3.3 binary_search, lower_bound, upper_bound

정렬된 컨테이너에서 사용해야 합니다.

  • binary_search(begin, end, value): value가 범위 내에 존재하는지 여부를 불리언(boolean) 값으로 반환합니다.
  • lower_bound(begin, end, value): value보다 크거나 같은 첫 번째 요소의 반복자를 반환합니다.
  • upper_bound(begin, end, value): value보다 큰 첫 번째 요소의 반복자를 반환합니다.

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

int main() {
    std::vector<int> sorted_vec = {1, 3, 3, 5, 7}; // 반드시 정렬되어 있어야 함

    // 값 3이 존재하는지 확인
    bool exists = std::binary_search(sorted_vec.begin(), sorted_vec.end(), 3); 
    std::cout << "Does 3 exist? " << std::boolalpha << exists << std::endl; // 출력: Does 3 exist? true

    // 3보다 크거나 같은 첫 번째 요소 찾기
    auto lb_it = std::lower_bound(sorted_vec.begin(), sorted_vec.end(), 3);
    if (lb_it != sorted_vec.end()) {
        std::cout << "Lower bound for 3 is at index: " << std::distance(sorted_vec.begin(), lb_it) << std::endl; // 출력: Lower bound for 3 is at index: 1
    }

    // 3보다 큰 첫 번째 요소 찾기
    auto ub_it = std::upper_bound(sorted_vec.begin(), sorted_vec.end(), 3);
     if (ub_it != sorted_vec.end()) {
        std::cout << "Upper bound for 3 is at index: " << std::distance(sorted_vec.begin(), ub_it) << std::endl; // 출력: Upper bound for 3 is at index: 3
    }

    return 0;
}
    

3.4 merge

두 개의 정렬된 범위를 하나의 정렬된 범위로 병합합니다.


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

int main() {
    std::vector<int> vec_a = {1, 3, 5};
    std::vector<int> vec_b = {2, 4, 6};
    std::vector<int> merged_vec(vec_a.size() + vec_b.size());

    // 두 정렬된 벡터를 병합
    std::merge(vec_a.begin(), vec_a.end(), vec_b.begin(), vec_b.end(), merged_vec.begin()); 
    // merged_vec: {1, 2, 3, 4, 5, 6}

    std::cout << "Merged vector: ";
    for(int val : merged_vec) std::cout << val << " "; // 출력: 1 2 3 4 5 6
    std::cout << std::endl;

    return 0;
}
    

4. 힙 알고리즘

STL은 범위를 힙 구조로 다루는 알고리즘들 (make_heap, push_heap, pop_heap, sort_heap 등)을 제공합니다.


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

int main() {
    std::vector<int> vec = {4, 1, 3, 2, 5};
    
    // 최대 힙 생성
    std::make_heap(vec.begin(), vec.end()); 
    // vec는 {5, 4, 3, 2, 1} 형태의 최대 힙이 됩니다. (루트 노드가 가장 큼)

    // 새 요소 추가 후 힙 유지
    vec.push_back(6);
    std::push_heap(vec.begin(), vec.end()); 
    // vec는 {6, 4, 5, 2, 1, 3} 형태의 최대 힙이 됩니다.

    // 루트 요소 (최대값)를 뒤로 옮기고 힙 재구성
    std::pop_heap(vec.begin(), vec.end()); 
    // vec는 {5, 4, 3, 2, 1, 6}이 됩니다. (6은 이제 마지막 요소)
    int max_val = vec.back(); // 최대값 6을 얻음
    vec.pop_back(); // 최대값 제거

    // 힙을 일반 정렬된 시퀀스로 변환
    std::sort_heap(vec.begin(), vec.end()); 
    // vec는 {1, 2, 3, 4, 5}가 됩니다. (오름차순 정렬)

    std::cout << "Max value popped: " << max_val << std::endl; // 출력: 6
    std::cout << "Vector after sort_heap: ";
    for(int val : vec) std::cout << val << " "; // 출력: 1 2 3 4 5
    std::cout << std::endl;

    return 0;
}
    

5. 최소/최대값 알고리즘

5.1 min 및 max

두 값 또는 초기화 리스트에서 최소/최대값을 반환합니다.


#include <algorithm>
#include <iostream>
#include <vector> // initializer_list 사용을 위해

int main() {
    int a = 5, b = 3;
    int min_val = std::min(a, b); // 3
    int max_val = std::max(a, b); // 5

    // 초기화 리스트 사용 (C++11 이상)
    auto min_of_list = std::min({4, 2, 8, 5, 1}); // 1
    auto max_of_list = std::max({4, 2, 8, 5, 1}); // 8

    std::cout << "min(5, 3): " << min_val << std::endl; // 출력: 3
    std::cout << "max(5, 3): " << max_val << std::endl; // 출력: 5
    std::cout << "min({4, 2, 8, 5, 1}): " << min_of_list << std::endl; // 출력: 1
    std::cout << "max({4, 2, 8, 5, 1}): " << max_of_list << std::endl; // 출력: 8

    return 0;
}
    

5.2 min_element 및 max_element

범위 내에서 최소값 또는 최대값을 가지는 첫 번째 요소의 반복자를 반환합니다.


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

int main() {
    std::vector<int> vec = {3, 1, 4, 2, 5};
    
    auto min_it = std::min_element(vec.begin(), vec.end()); // 1을 가리키는 반복자
    auto max_it = std::max_element(vec.begin(), vec.end()); // 5를 가리키는 반복자

    std::cout << "Minimum element: " << *min_it << std::endl; // 출력: 1
    std::cout << "Maximum element: " << *max_it << std::endl; // 출력: 5

    return 0;
}
    

5.3 minmax_element (C++11 이상)

범위 내의 최소값과 최대값을 동시에 가지는 요소들의 반복자 쌍(std::pair)을 반환합니다.


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

int main() {
    std::vector<int> vec = {3, 1, 4, 2, 5};
    
    auto minmax_pair = std::minmax_element(vec.begin(), vec.end());
    // minmax_pair.first는 1을 가리키는 반복자
    // minmax_pair.second는 5를 가리키는 반복자

    std::cout << "Min element: " << *minmax_pair.first << std::endl;  // 출력: 1
    std::cout << "Max element: " << *minmax_pair.second << std::endl; // 출력: 5

    return 0;
}
    

6. 수치 알고리즘 (<numeric> 헤더)

6.1 accumulate

범위 내 요소들의 누적 합(또는 사용자 정의 연산)을 계산합니다.


#include <numeric> // accumulate, multiplies
#include <vector>
#include <iostream>

int main() {
    std::vector<int> vec = {1, 2, 3, 4, 5};
    
    // 누적 합 (초기값 0)
    int sum = std::accumulate(vec.begin(), vec.end(), 0); // 결과: 15
    
    // 누적 곱 (초기값 1, 곱셈 연산자 사용)
    int product = std::accumulate(vec.begin(), vec.end(), 1, std::multiplies<int>()); // 결과: 120

    std::cout << "Sum: " << sum << std::endl; // 출력: 15
    std::cout << "Product: " << product << std::endl; // 출력: 120

    return 0;
}
    

6.2 inner_product

두 범위의 내적(dot product)을 계산합니다. (또는 사용자 정의 연산)


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

int main() {
    std::vector<int> a = {1, 2, 3};
    std::vector<int> b = {4, 5, 6};
    
    // 내적 계산 (초기값 0)
    int dot_product = std::inner_product(a.begin(), a.end(), b.begin(), 0); 
    // 1*4 + 2*5 + 3*6 = 4 + 10 + 18 = 32

    std::cout << "Inner product: " << dot_product << std::endl; // 출력: 32

    return 0;
}
    

6.3 iota

범위를 연속적으로 증가하는 값으로 채웁니다.


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

int main() {
    std::vector<int> vec(5); // 크기가 5인 벡터
    
    // 10부터 시작하여 연속적으로 채움
    std::iota(vec.begin(), vec.end(), 10); 
    // vec: {10, 11, 12, 13, 14}

    std::cout << "Vector filled with iota: ";
    for(int val : vec) std::cout << val << " "; // 출력: 10 11 12 13 14
    std::cout << std::endl;

    return 0;
}
    

6.4 partial_sum

누적 합(부분 합)을 계산하고 결과를 지정된 대상 범위에 저장합니다.


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

int main() {
    std::vector<int> source = {1, 2, 3, 4, 5};
    std::vector<int> destination(source.size());
    
    std::partial_sum(source.begin(), source.end(), destination.begin()); 
    // destination: {1, 1+2, 1+2+3, 1+2+3+4, 1+2+3+4+5} = {1, 3, 6, 10, 15}

    std::cout << "Destination vector after partial_sum: ";
    for(int val : destination) std::cout << val << " "; // 출력: 1 3 6 10 15
    std::cout << std::endl;

    return 0;
}
    

6.5 adjacent_difference

인접한 요소 간의 차이를 계산하고 결과를 대상 범위에 저장합니다.


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

int main() {
    std::vector<int> source = {1, 2, 3, 4, 5};
    std::vector<int> destination(source.size());
    
    std::adjacent_difference(source.begin(), source.end(), destination.begin()); 
    // destination: {1, 2-1, 3-2, 4-3, 5-4} = {1, 1, 1, 1, 1}

    std::cout << "Destination vector after adjacent_difference: ";
    for(int val : destination) std::cout << val << " "; // 출력: 1 1 1 1 1
    std::cout << std::endl;

    return 0;
}
    

7. 기타 알고리즘

7.1 generate

주어진 생성 함수(예: 람다)를 사용하여 범위를 채웁니다.


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

int main() {
    std::vector<int> vec(5);
    int start_value = 0;
    
    // 람다 함수를 사용하여 0부터 시작하는 값으로 채움
    std::generate(vec.begin(), vec.end(), [&start_value]() { 
        return start_value++; 
    }); 
    // vec: {0, 1, 2, 3, 4}

    std::cout << "Vector filled with generate: ";
    for(int val : vec) std::cout << val << " "; // 출력: 0 1 2 3 4
    std::cout << std::endl;

    return 0;
}
    

7.2 generate_n

주어진 생성 함수를 사용하여 범위의 시작부터 N개의 요소를 채웁니다.


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

int main() {
    std::vector<int> vec(5); // 크기 5 벡터
    int current_val = 10;
    
    // vec.begin()부터 3개의 요소를 10부터 시작하는 값으로 채움
    std::generate_n(vec.begin(), 3, [¤t_val]() { 
        return current_val++; 
    }); 
    // vec: {10, 11, 12, ?, ?} (나머지 요소는 초기값 유지)

    std::cout << "Vector after generate_n: ";
    for(int val : vec) std::cout << val << " "; // 출력: 10 11 12 0 0 (초기값이 0이라면)
    std::cout << std::endl;

    return 0;
}
    

7.3 includes

정렬된 첫 번째 범위가 정렬된 두 번째 범위의 모든 요소를 포함하는지 검사합니다.


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

int main() {
    std::vector<int> vec1 = {1, 2, 3, 4, 5}; // 정렬된 범위
    std::vector<int> vec2 = {2, 4};         // 정렬된 범위
    
    bool result = std::includes(vec1.begin(), vec1.end(), vec2.begin(), vec2.end()); 
    std::cout << "vec1 includes vec2? " << std::boolalpha << result << std::endl; // 출력: true

    std::vector<int> vec3 = {1, 3};
    bool result2 = std::includes(vec1.begin(), vec1.end(), vec3.begin(), vec3.end());
    std::cout << "vec1 includes vec3? " << std::boolalpha << result2 << std::endl; // 출력: true

    std::vector<int> vec4 = {2, 6};
    bool result3 = std::includes(vec1.begin(), vec1.end(), vec4.begin(), vec4.end());
    std::cout << "vec1 includes vec4? " << std::boolalpha << result3 << std::endl; // 출력: false

    return 0;
}
    

7.4 set_union, set_intersection, set_difference, set_symmetric_difference

정렬된 범위에 대한 집합 연산(합집합, 교집합, 차집합, 대칭 차집합)을 수행합니다.


#include <vector>
#include <algorithm>
#include <iterator> // std::back_inserter
#include <iostream>

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

    // 합집합 (Union)
    result.clear();
    std::set_union(v1.begin(), v1.end(), v2.begin(), v2.end(), std::back_inserter(result));
    // result: {1, 2, 3, 4, 5, 6, 7}
    std::cout << "Union: ";
    for(int val : result) std::cout << val << " "; // 출력: 1 2 3 4 5 6 7
    std::cout << std::endl;

    // 교집합 (Intersection)
    result.clear();
    std::set_intersection(v1.begin(), v1.end(), v2.begin(), v2.end(), std::back_inserter(result));
    // result: {3, 4, 5}
    std::cout << "Intersection: ";
    for(int val : result) std::cout << val << " "; // 출력: 3 4 5
    std::cout << std::endl;

    // 차집합 (Difference, v1 - v2)
    result.clear();
    std::set_difference(v1.begin(), v1.end(), v2.begin(), v2.end(), std::back_inserter(result));
    // result: {1, 2}
    std::cout << "Difference (v1 - v2): ";
    for(int val : result) std::cout << val << " "; // 출력: 1 2
    std::cout << std::endl;

    // 대칭 차집합 (Symmetric Difference)
    result.clear();
    std::set_symmetric_difference(v1.begin(), v1.end(), v2.begin(), v2.end(), std::back_inserter(result));
    // result: {1, 2, 6, 7} (합집합에서 교집합을 제외한 부분)
    std::cout << "Symmetric Difference: ";
    for(int val : result) std::cout << val << " "; // 출력: 1 2 6 7
    std::cout << std::endl;

    return 0;
}
    

8. 자주 묻는 질문

  1. sort와 stable_sort의 차이점은 무엇인가요?

    • sort: 일반적으로 퀵 정렬 기반(Introsort)으로 구현되어 빠르지만, 동일한 값들을 가진 요소들의 원래 순서를 보장하지 않습니다 (불안정 정렬). 평균 시간 복잡도는 O(n log n)입니다.
    • stable_sort: 합병 정렬(Merge Sort) 등을 사용하여 구현되며, 동일한 값들을 가진 요소들의 상대적 순서를 유지합니다 (안정 정렬). 시간 복잡도는 O(n log n)이지만, 추가 메모리 공간이 더 필요할 수 있습니다.
  2. remove 알고리즘은 왜 erase와 함께 사용해야 하나요?

    remove는 삭제할 요소를 찾아 다른 요소로 덮어쓰거나 뒤로 이동시키는 방식으로 작동합니다. 이 과정에서 컨테이너의 실제 크기는 변경되지 않으며, remove는 유효한 새 논리적 끝을 가리키는 반복자만 반환합니다. 실제 메모리에서 불필요한 요소를 제거하고 컨테이너 크기를 줄이려면, 반환된 반복자를 사용하여 erase 멤버 함수를 호출해야 합니다. 패턴: container.erase(std::remove(container.begin(), container.end(), value), container.end());

  3. 어떤 알고리즘들이 정렬된 컨테이너를 필요로 하나요?

    이진 탐색 관련 알고리즘들 (std::binary_search, std::lower_bound, std::upper_bound), 집합 연산 알고리즘들 (std::set_intersection, std::set_union 등), std::merge와 같이 O(log n) 또는 O(n) 시간에 효율적으로 작동하기 위해 데이터의 순서에 의존하는 알고리즘들이 정렬된 입력을 요구합니다.

태그: C++ STL 알고리즘 정렬 탐색

10월 16일 08:13에 게시됨