1. 비수정 시퀀스 알고리즘
이러한 알고리즘은 작업 대상 컨테이너의 요소를 변경하지 않습니다.
1.1 find와 find_if
find(begin, end, value):value와 동일한 첫 번째 요소를 찾아 반복자 반환 (못 찾으면end반환)find_if(begin, end, predicate): 조건자를 만족하는 첫 번째 요소 찾기find_end(begin, end, sub_begin, sub_end): 하위 시퀀스가 마지막으로 나타나는 위치 찾기
std::vector<int> data = {2, 4, 6, 8, 10};
// 값이 6인 요소 찾기
auto pos = std::find(data.begin(), data.end(), 6);
if (pos != data.end()) {
std::cout << "발견: " << *pos << std::endl; // 출력: 6
}
// 5보다 큰 첫 번째 요소 찾기
auto pos2 = std::find_if(data.begin(), data.end(), [](int n) {
return n > 5;
});
std::cout << "5보다 큰 첫 번째: " << *pos2 << std::endl; // 출력: 6
// 하위 시퀀스 찾기
std::vector<int> pattern = {4, 6};
auto pos3 = std::find_end(data.begin(), data.end(), pattern.begin(), pattern.end());
if (pos3 != data.end()) {
std::cout << "하위 시퀀스 시작 인덱스: " << pos3 - data.begin() << std::endl; // 출력: 1
}1.2 count와 count_if
count(begin, end, value):value와 동일한 요소 개수 계산count_if(begin, end, predicate): 조건자를 만족하는 요소 개수 계산
std::vector<int> collection = {5, 3, 1, 3, 7, 3};
int target = std::count(collection.begin(), collection.end(), 3); // 3의 개수, 결과: 3
int odd_cnt = std::count_if(collection.begin(), collection.end(), [](int n) {
return n % 2 != 0;
}); // 홀수 개수, 결과: 51.3 for_each
범위의 각 요소에 함수 적용
std::vector<int> items = {10, 20, 30, 40, 50};
std::for_each(items.begin(), items.end(), [](int& val) {
val += 5; // 각 요소에 5 더하기
});
// 이제 items는 {15, 25, 35, 45, 50}1.4 equal과 mismatch
equal(b1, e1, b2): 두 범위가 같은지 비교mismatch(b1, e1, b2): 첫 번째로 일치하지 않는 요소의 반복자 쌍 반환
std::vector<int> source = {1, 2, 3};
std::vector<int> target1 = {1, 2, 4};
std::vector<int> target2 = {1, 2, 3, 4};
// source와 target1 비교
bool same = std::equal(source.begin(), source.end(), target1.begin());
std::cout << "source == target1? " << std::boolalpha << same << std::endl; // 출력: false
// source와 target2의 첫 번째 불일치 찾기
auto diff = std::mismatch(source.begin(), source.end(), target2.begin());
if (diff.first != source.end()) {
std::cout << "불일치: " << *diff.first << " vs " << *diff.second << std::endl;
}1.5 all_of, any_of, none_of
범위 내 요소가 모두, 하나라도, 또는 하나도 조건을 만족하지 않는지 확인
std::vector<int> numbers = {2, 4, 6, 8};
bool all_positive = std::all_of(numbers.begin(), numbers.end(), [](int n) {
return n > 0;
}); // true
bool any_zero = std::any_of(numbers.begin(), numbers.end(), [](int n) {
return n == 0;
}); // false
bool none_negative = std::none_of(numbers.begin(), numbers.end(), [](int n) {
return n < 0;
}); // true2. 수정 시퀀스 알고리즘
이 알고리즘들은 작업 대상 컨테이너의 요소를 수정합니다.
2.1 copy와 copy_if
copy(begin, end, dest):[begin, end)의 요소를dest위치에 복사copy_if(begin, end, dest, predicate): 조건자를 만족하는 요소만 복사
std::vector<int> source = {1, 2, 3, 4, 5};
std::vector<int> destination(5); // 충분한 공간 사전 할당 필요
// 모든 요소 복사
std::copy(source.begin(), source.end(), destination.begin()); // destination: [1,2,3,4,5]
// 홀수 요소만 새 컨테이너에 복사
std::vector<int> odds;
std::copy_if(source.begin(), source.end(), std::back_inserter(odds), [](int n) {
return n % 2 != 0;
}); // odds: [1,3,5]참고: back_inserter(dest)는 자동으로 push_back을 호출하므로 공간을 미리 할당할 필요가 없습니다.
2.2 transform
범위의 각 요소에 함수를 적용하고 결과를 다른 범위에 저장
std::vector<int> values = {1, 2, 3};
std::vector<int> squares(3);
// 제곱 계산 (단일 인자 변환)
std::transform(values.begin(), values.end(), squares.begin(), [](int n) {
return n * n;
}); // squares: [1,4,9]
// 두 컨테이너 요소 더하기 (이중 인자 변환)
std::vector<int> left = {1, 2, 3};
std::vector<int> right = {4, 5, 6};
std::vector<int> result(3);
std::transform(left.begin(), left.end(), right.begin(), result.begin(), [](int x, int y) {
return x + y;
}); // result: [5,7,9]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): 조건자를 만족하는 요소 교체replace_copy(begin, end, dest, old_val, new_val): 복사 시 교체 (원본 불변)
std::vector<int> numbers = {1, 2, 3, 2, 5};
// 모든 2를 20으로 교체
std::replace(numbers.begin(), numbers.end(), 2, 20); // numbers: [1,20,3,20,5]
// 15보다 큰 요소를 0으로 교체
std::replace_if(numbers.begin(), numbers.end(), [](int n) {
return n > 15;
}, 0); // numbers: [1,0,3,0,5]
// 복사 시 3을 300으로 교체 (원본 불변)
std::vector<int> output;
std::replace_copy(numbers.begin(), numbers.end(), std::back_inserter(output), 3, 300); // output: [1,0,300,0,5]2.4 remove, remove_if와 erase
remove(begin, end, value):value와 같은 요소를 끝으로 "이동", 새 논리적 끝 반복자 반환 (실제 삭제X,erase와 함께 사용)remove_if(begin, end, predicate): 조건자를 만족하는 요소를 끝으로 이동
std::vector<int> values = {1, 2, 3, 2, 4};
// 논리적 삭제 (끝으로 이동)
auto new_end = std::remove(values.begin(), values.end(), 2); // values: [1,3,4,2,2]
// 물리적 삭제 (실제 요소 제거)
values.erase(new_end, values.end()); // values: [1,3,4]
// lambda와 결합하여 홀수 삭제
values = {1, 2, 3, 4, 5};
values.erase(std::remove_if(values.begin(), values.end(), [](int n) {
return n % 2 != 0;
}), values.end()); // values: [2,4]2.5 unique
범위 내 연속된 중복 요소를 제거하고 새 논리적 끝 반복자 반환. 보통 erase와 함께 사용.
std::vector<int> sequence = {1, 1, 2, 2, 3, 3, 3, 4, 5};
auto new_last = std::unique(sequence.begin(), sequence.end());
sequence.erase(new_last, sequence.end()); // sequence는 {1, 2, 3, 4, 5}2.6 reverse
범위 내 요소 순서 뒤집기
std::vector<int> list = {1, 2, 3, 4, 5};
std::reverse(list.begin(), list.end()); // list는 {5, 4, 3, 2, 1}2.7 rotate
범위 내 요소를 회전시켜 중간 요소가 새로운 첫 번째 요소가 되도록 함
std::vector<int> list = {1, 2, 3, 4, 5};
std::rotate(list.begin(), list.begin() + 2, list.end()); // 3을 시작점으로 회전, list는 {3, 4, 5, 1, 2}2.8 shuffle
범위 내 요소를 무작위로 재배열 (C++11 이상 필요)
#include <random>
#include <algorithm>
std::vector<int> list = {1, 2, 3, 4, 5};
std::random_device rd;
std::mt19937 gen(rd());
std::shuffle(list.begin(), list.end(), gen); // list의 요소를 무작위로 섞음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, mid)가 전체 중 가장 작은 정렬된 요소
std::vector<int> numbers = {5, 3, 1, 4, 2};
std::sort(numbers.begin(), numbers.end()); // 기본 오름차순, numbers: {1, 2, 3, 4, 5}
std::sort(numbers.begin(), numbers.end(), std::greater<int>()); // 내림차순, numbers: {5, 4, 3, 2, 1}
std::sort(numbers.begin(), numbers.end(), [](int a, int b) {
return a < b;
}); // 오름차순, 사용자 정의 비교
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로 정렬, 동일 요소의 상대 순서 유지
});
std::vector<int> numbers = {5, 3, 1, 4, 2, 6};
// 가장 작은 3개 요소를 앞에 배치하고 정렬
std::partial_sort(numbers.begin(), numbers.begin() + 3, numbers.end());
// 이제 numbers 앞 세 요소는 1, 2, 3, 뒤에는 미정렬된 4, 5, 63.2 nth_element
범위를 재배열하여 지정 위치의 요소가 정렬 후 해당 위치의 값이 되도록 하고, 왼쪽 요소는 모두 작거나 같고 오른쪽 요소는 모두 크거나 같도록 함
std::vector<int> numbers = {5, 3, 1, 4, 2, 6};
// 세 번째로 작은 요소 찾기 (인덱스 2)
std::nth_element(numbers.begin(), numbers.begin() + 2, numbers.end());
// 이제 numbers[2]는 3, 왼쪽 요소는 <= 3, 오른쪽 요소는 >= 33.3 binary_search, lower_bound, upper_bound
정렬된 컨테이너에서만 사용 가능
binary_search(begin, end, value):value是否存在 (bool 반환)lower_bound(begin, end, value):value이상이 첫 번째 요소 반복자 반환upper_bound(begin, end, value):value초과 첫 번째 요소 반복자 반환
std::vector<int> sorted = {1, 3, 3, 5, 7}; // 먼저 정렬 필요
// 3이是否存在
bool exists = std::binary_search(sorted.begin(), sorted.end(), 3); // true
// 첫 번째 >= 3 요소 찾기
auto lower = std::lower_bound(sorted.begin(), sorted.end(), 3);
std::cout << "lower_bound 인덱스: " << lower - sorted.begin() << std::endl; // 출력: 1
// 첫 번째 > 3 요소 찾기
auto upper = std::upper_bound(sorted.begin(), sorted.end(), 3);
std::cout << "upper_bound 인덱스: " << upper - sorted.begin() << std::endl; // 출력: 33.4 merge
두 정렬된 범위를 새 컨테이너로 병합 (정렬 유지)
std::vector<int> left = {1, 3, 5};
std::vector<int> right = {2, 4, 6};
std::vector<int> merged(left.size() + right.size());
// left와 right 병합 (둘 다 정렬 필요)
std::merge(left.begin(), left.end(), right.begin(), right.end(), merged.begin()); // merged: [1,2,3,4,5,6]4. 힙 알고리즘
STL은 범위를 힙으로 조작하는 알고리즘을 제공합니다: make_heap, push_heap, pop_heap, sort_heap 등
std::vector<int> heap_data = {4, 1, 3, 2, 5};
std::make_heap(heap_data.begin(), heap_data.end()); // 최대 힙 구성, heap_data: {5, 4, 3, 2, 1}
heap_data.push_back(6);
std::push_heap(heap_data.begin(), heap_data.end()); // 새 요소를 힙에 추가, heap_data: {6, 4, 5, 2, 1, 3}
std::pop_heap(heap_data.begin(), heap_data.end()); // 최대 요소를 끝으로 이동, heap_data: {5, 4, 3, 2, 1, 6}
int top = heap_data.back(); // 최대 요소 6 획득
heap_data.pop_back(); // 최대 요소 제거
std::sort_heap(heap_data.begin(), heap_data.end()); // 힙을 오름차순으로 정렬, heap_data: {1, 2, 3, 4, 5}5. 최소/최대 알고리즘
5.1 min과 max
두 값 또는 초기화 목록에서 최소/최대 값 반환
int x = 5, y = 3;
int minimum = std::min(x, y); // 3
int maximum = std::max(x, y); // 5
auto min_of_init = std::min({4, 2, 8, 5, 1}); // 1
auto max_of_init = std::max({4, 2, 8, 5, 1}); // 85.2 min_element와 max_element
범위 내 최소/최대 요소의 반복자 반환
std::vector<int> data = {3, 1, 4, 2, 5};
auto min_pos = std::min_element(data.begin(), data.end()); // 1 가리킴
auto max_pos = std::max_element(data.begin(), data.end()); // 5 가리킴5.3 minmax_element (C++11)
범위 내 최소와 최대 요소를 동시에 반환
std::vector<int> data = {3, 1, 4, 2, 5};
auto result = std::minmax_element(data.begin(), data.end());
// result.first는 1 가리킴, result.second는 5 가리킴6. 수치 알고리즘 (<numeric> 헤더)
6.1 accumulate
범위 내 요소의 누적 합계 (또는 사용자 정의 연산) 계산
#include <numeric>
std::vector<int> data = {1, 2, 3, 4, 5};
int total = std::accumulate(data.begin(), data.end(), 0); // 합계, 초기값 0, 결과 15
int product = std::accumulate(data.begin(), data.end(), 1, std::multiplies<int>()); // 곱, 초기값 1, 결과 1206.2 inner_product
두 범위의 내적 (또는 사용자 정의 연산) 계산
std::vector<int> a = {1, 2, 3};
std::vector<int> b = {4, 5, 6};
int dot = std::inner_product(a.begin(), a.end(), b.begin(), 0); // 1*4 + 2*5 + 3*6 = 326.3 iota
연속적으로 증가하는 값으로 범위 채우기
std::vector<int> vec(5);
std::iota(vec.begin(), vec.end(), 10); // 10, 11, 12, 13, 14로 채움6.4 partial_sum
부분 합 계산하고 결과를 대상 범위에 저장
std::vector<int> source = {1, 2, 3, 4, 5};
std::vector<int> dest(source.size());
std::partial_sum(source.begin(), source.end(), dest.begin()); // dest: {1, 3, 6, 10, 15}6.5 adjacent_difference
인접 요소의 차이를 계산하고 결과를 대상 범위에 저장
std::vector<int> source = {1, 2, 3, 4, 5};
std::vector<int> dest(source.size());
std::adjacent_difference(source.begin(), source.end(), dest.begin()); // dest: {1, 1, 1, 1, 1}7. 기타 알고리즘
7.1 generate
생성 함수로 범위 채우기
std::vector<int> vec(5);
int counter = 0;
std::generate(vec.begin(), vec.end(), [&counter]() {
return counter++;
}); // 0, 1, 2, 3, 4로 채움7.2 generate_n
생성 함수로 범위의 시작 n개 요소 채우기
std::vector<int> vec(5);
int num = 10;
std::generate_n(vec.begin(), 3, [&num]() {
return num++;
}); // 처음 세 요소는 10, 11, 12, 나머지 두 요소는 변경되지 않음7.3 includes
정렬된 범위가 다른 정렬된 범위의 모든 요소를 포함하는지 확인
std::vector<int> container1 = {1, 2, 3, 4, 5};
std::vector<int> container2 = {2, 4};
bool has_all = std::includes(container1.begin(), container1.end(), container2.begin(), container2.end()); // true7.4 set_union, set_intersection, set_difference, set_symmetric_difference
집합 연산 수행: 합집합, 교집합, 차집합, 대칭 차집합
std::vector<int> set_a = {1, 2, 3, 4, 5};
std::vector<int> set_b = {3, 4, 5, 6, 7};
std::vector<int> output;
// 합집합
std::set_union(set_a.begin(), set_a.end(), set_b.begin(), set_b.end(), std::back_inserter(output));
// output: {1, 2, 3, 4, 5, 6, 7}
// 교집합
output.clear();
std::set_intersection(set_a.begin(), set_a.end(), set_b.begin(), set_b.end(), std::back_inserter(output));
// output: {3, 4, 5}
// 차집합 (set_a - set_b)
output.clear();
std::set_difference(set_a.begin(), set_a.end(), set_b.begin(), set_b.end(), std::back_inserter(output));
// output: {1, 2}
// 대칭 차집합 (set_a ∪ set_b - set_a ∩ set_b)
output.clear();
std::set_symmetric_difference(set_a.begin(), set_a.end(), set_b.begin(), set_b.end(), std::back_inserter(output));
// output: {1, 2, 6, 7}8. 자주 묻는 질문
sort와stable_sort의 차이점은?sort는 빠른 정렬 (실제로는 introsort 알고리즘) 사용, 비안정 (동일 요소 상대 위치 변경 가능), 평균 시간 복잡도 O(n log n)stable_sort는 병합 정렬 사용, 안정 (동일 요소 상대 위치 불변), 시간 복잡도 O(n log n), 약간의 공간 오버헤드 존재
- 왜
remove알고리즘은erase와 함께 사용해야 하는가?
remove알고리즘의 원리는 삭제할 요소를 "덮어쓰기"하여 유지할 요소를前面으로 이동시키고 새 논리적 끝 반복자를 반환하지만, 컨테이너의 실제 크기를 수정하지 않습니다.erase는 반복자 범위로 실제 요소를 삭제하고 컨테이너 크기를 수정합니다. 따라서 함께 사용해야 합니다:container.erase(std::remove(...), container.end()) - 어떤 알고리즘들이 정렬된 컨테이너가 필요한가?
이진 탐색 系列 (binary_search,lower_bound,upper_bound), 집합 算法 (set_intersection,set_union등),merge등 - 이러한 알고리즘들은 효율한 작업 (예: 이진 탐색 O(log n))을 위해 정렬된 상태를 필요로 합니다.