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. 자주 묻는 질문
-
sort와stable_sort의 차이점은 무엇인가요?sort: 일반적으로 퀵 정렬 기반(Introsort)으로 구현되어 빠르지만, 동일한 값들을 가진 요소들의 원래 순서를 보장하지 않습니다 (불안정 정렬). 평균 시간 복잡도는 O(n log n)입니다.stable_sort: 합병 정렬(Merge Sort) 등을 사용하여 구현되며, 동일한 값들을 가진 요소들의 상대적 순서를 유지합니다 (안정 정렬). 시간 복잡도는 O(n log n)이지만, 추가 메모리 공간이 더 필요할 수 있습니다.
-
remove알고리즘은 왜erase와 함께 사용해야 하나요?remove는 삭제할 요소를 찾아 다른 요소로 덮어쓰거나 뒤로 이동시키는 방식으로 작동합니다. 이 과정에서 컨테이너의 실제 크기는 변경되지 않으며,remove는 유효한 새 논리적 끝을 가리키는 반복자만 반환합니다. 실제 메모리에서 불필요한 요소를 제거하고 컨테이너 크기를 줄이려면, 반환된 반복자를 사용하여erase멤버 함수를 호출해야 합니다. 패턴:container.erase(std::remove(container.begin(), container.end(), value), container.end()); -
어떤 알고리즘들이 정렬된 컨테이너를 필요로 하나요?
이진 탐색 관련 알고리즘들 (
std::binary_search,std::lower_bound,std::upper_bound), 집합 연산 알고리즘들 (std::set_intersection,std::set_union등),std::merge와 같이 O(log n) 또는 O(n) 시간에 효율적으로 작동하기 위해 데이터의 순서에 의존하는 알고리즘들이 정렬된 입력을 요구합니다.