1. 원본 수정하지 않는 알고리즘 (Non-modifying Algorithms)
이 유형의 알고리즘들은 컨테이너 내부 요소를 변경하지 않고, 오직 읽기(read) 작업만 수행한다.
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): 특정 부분 시퀀스가 마지막으로 등장하는 위치의 반복자를 반환한다.
std::vector<int> data = {2, 4, 6, 8, 10};
// 값이 '6'인 요소 검색
auto iter = std::find(data.begin(), data.end(), 6);
if (iter != data.end()) {
std::cout << "발견된 값: " << *iter << std::endl; // 출력: 6
}
// 첫 번째로 '5'보다 큰 요소 검색
auto iter2 = std::find_if(data.begin(), data.end(), [](int x) {
return x > 5;
});
std::cout << "5 초과 첫 값: " << *iter2 << std::endl; // 출력: 6
// 부분 시퀀스 {4, 6}의 마지막 등장 위치 검색
std::vector<int> pattern = {4, 6};
auto iter3 = std::find_end(data.begin(), data.end(), pattern.begin(), pattern.end());
if (iter3 != data.end()) {
std::cout << "부분 시퀀스 시작 인덱스: " << (iter3 - data.begin()) << std::endl; // 출력: 1
}
1.2 count & count_if
count(begin, end, value):value와 동일한 요소의 총 개수를 센다.count_if(begin, end, predicate): 주어진 조건을 만족하는 요소의 총 개수를 센다.
std::vector<int> vals = {1, 3, 3, 5, 3, 7};
int cntThree = std::count(vals.begin(), vals.end(), 3); // 결과: 3
int cntOdd = std::count_if(vals.begin(), vals.end(), [](int x) {
return (x % 2 != 0);
}); // 홀수 개수, 결과: 5
1.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, 55}
1.4 equal & mismatch
equal(b1, e1, b2): 두 범위[b1,e1)와[b2, b2+(e1-b1))가 동일한지 검사한다.mismatch(b1, e1, b2): 두 범위에서 첫 번째로 일치하지 않는 요소들의 반복자 쌍(pair)을 반환한다.
std::vector<int> v1 = {10, 20, 30};
std::vector<int> v2 = {10, 20, 40};
std::vector<int> v3 = {10, 20, 30, 50};
// v1과 v2의 앞 3개 요소 비교
bool isEq = std::equal(v1.begin(), v1.end(), v2.begin());
std::cout << "v1 == v2? " << std::boolalpha << isEq << std::endl; // 출력: false
// v1과 v3의 첫 불일치 탐색
auto mispair = std::mismatch(v1.begin(), v1.end(), v3.begin());
if (mispair.first != v1.end()) {
// v1과 v3는 앞 3개가 같으므로 이 조건문은 실행되지 않음
}
1.5 all_of, any_of, none_of
범위 내의 모든, 일부, 또는 어떤 요소도 조건을 만족하지 않는지 검사한다.
std::vector<int> data = {4, 6, 8, 10};
bool allEven = std::all_of(data.begin(), data.end(), [](int x) {
return x % 2 == 0;
}); // true
bool anyOdd = std::any_of(data.begin(), data.end(), [](int x) {
return x % 2 != 0;
}); // false
bool noneNeg = std::none_of(data.begin(), data.end(), [](int x) {
return x < 0;
}); // true
2. 원본을 변경하는 알고리즘 (Modifying Algorithms)
이 알고리즘들은 컨테이너 내부 요소를 직접 변경하거나, 다른 위치로 복사하는 과정에서 변경을 수행한다.
2.1 copy & copy_if
copy(begin, end, dest):[begin, end)범위의 요소를dest위치로 복사한다.copy_if(begin, end, dest, predicate): 조건을 만족하는 요소만dest로 복사한다.
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> evens;
std::copy_if(source.begin(), source.end(), std::back_inserter(evens), [](int x) {
return x % 2 == 0;
}); // evens: {2,4}
2.2 transform
시퀀스의 각 요소에 함수를 적용하고, 그 결과를 다른(또는 같은) 시퀀스에 저장한다.
std::vector<int> numbers = {2, 3, 4};
std::vector<int> doubled(3);
// 단일 인자 변환: 각 요소를 2배로
std::transform(numbers.begin(), numbers.end(), doubled.begin(), [](int x) {
return x * 2;
}); // doubled: {4, 6, 8}
// 두 컨테이너의 요소를 더하기 (이항 변환)
std::vector<int> left = {10, 20, 30};
std::vector<int> right = {1, 2, 3};
std::vector<int> sum(3);
std::transform(left.begin(), left.end(), right.begin(), sum.begin(), [](int a, int b) {
return a + b;
}); // sum: {11, 22, 33}
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로 교체한다 (원본 유지).
std::vector<int> values = {10, 20, 30, 20, 50};
// 모든 '20'을 '200'으로 변경
std::replace(values.begin(), values.end(), 20, 200); // values: {10,200,30,200,50}
// 100보다 큰 요소를 '0'으로 변경
std::replace_if(values.begin(), values.end(), [](int x) {
return x > 100;
}, 0); // values: {10,0,30,0,50}
// 복사하면서 '30'을 '300'으로 변경 (원본 유지)
std::vector<int> resultVec;
std::replace_copy(values.begin(), values.end(), std::back_inserter(resultVec), 30, 300);
// resultVec: {10,0,300,0,50}
2.4 remove & remove_if
remove 계열은 실제로 요소를 삭제하지 않고, 삭제 대상이 아닌 요소를 앞쪽으로 모은다. 이후 erase와 함께 사용해야 물리적 삭제가 이루어진다.
std::vector<int> items = {5, 10, 15, 10, 20};
// 논리적 삭제: '10'을 뒤로 밀어냄
auto newLogicalEnd = std::remove(items.begin(), items.end(), 10); // items: {5,15,20,10,10}
// 물리적 삭제
items.erase(newLogicalEnd, items.end()); // items: {5,15,20}
// 람다와 조합하여 홀수 제거
items = {1, 2, 3, 4, 5, 6};
items.erase(std::remove_if(items.begin(), items.end(), [](int x) {
return x % 2 != 0;
}), items.end()); // items: {2,4,6}
2.5 unique
연속된 중복 요소를 제거하고, 새로운 논리적 끝 반복자를 반환한다. 보통 erase와 함께 사용한다.
std::vector<int> data = {1, 1, 2, 2, 3, 4, 4, 4, 5};
auto last = std::unique(data.begin(), data.end());
data.erase(last, data.end()); // data: {1, 2, 3, 4, 5}
2.6 reverse
시퀀스의 요소 순서를 뒤집는다.
std::vector<int> items = {100, 200, 300, 400};
std::reverse(items.begin(), items.end()); // items: {400, 300, 200, 100}
2.7 rotate
시퀀스를 회전시켜, 중간 지점의 요소가 새로운 첫 번째 요소가 되도록 한다.
std::vector<int> data = {10, 20, 30, 40, 50};
std::rotate(data.begin(), data.begin() + 2, data.end());
// data: {30, 40, 50, 10, 20}
2.8 shuffle
시퀀스의 요소를 무작위로 섞는다. (C++11 이상 필요)
#include <random>
#include <algorithm>
std::vector<int> data = {1, 2, 3, 4, 5, 6};
std::random_device rd;
std::mt19937 randomEngine(rd());
std::shuffle(data.begin(), data.end(), randomEngine);
// data의 요소가 임의 순서로 섞임
3. 정렬 관련 알고리즘 (Sorting and Related)
3.1 sort, stable_sort & partial_sort
sort(begin, end): 불안정 정렬(intro sort 기반)을 수행한다. 평균 시간 복잡도는 O(n log n)이다.stable_sort(begin, end): 안정 정렬을 수행한다. 동일한 값의 상대적 순서가 유지된다. (보통 병합 정렬 기반)partial_sort(begin, mid, end):[begin, mid)범위가 전체에서 가장 작은 요소들로 정렬되도록 부분 정렬한다.
std::vector<int> nums = {9, 3, 7, 1, 5};
std::sort(nums.begin(), nums.end()); // 오름차순: {1, 3, 5, 7, 9}
// 내림차순 정렬
std::sort(nums.begin(), nums.end(), std::greater<int>()); // {9, 7, 5, 3, 1}
// 사용자 정의 비교 람다 (오름차순)
std::sort(nums.begin(), nums.end(), [](int a, int b) { return a < b; });
// pair 벡터의 안정 정렬 예시
std::vector<std::pair<int, int>> pairs = {{2, 10}, {1, 20}, {2, 5}};
std::stable_sort(pairs.begin(), pairs.end(), [](const auto& p1, const auto& p2) {
return p1.first < p2.first; // 첫 번째 요소 기준, 값이 같으면 원래 순서 유지
});
// 부분 정렬: 앞의 3개 요소만 정렬
std::vector<int> numbers = {8, 2, 6, 4, 9, 1};
std::partial_sort(numbers.begin(), numbers.begin() + 3, numbers.end());
// numbers의 앞 3개: {1, 2, 4} (가장 작은 3개)
3.2 nth_element
시퀀스를 재배열하여, n번째 위치의 요소가 전체가 정렬되었을 때 그 위치에 있을 값이 되도록 한다. n번째 왼쪽 요소들은 모두 n번째보다 작거나 같고, 오른쪽 요소들은 모두 크거나 같다.
std::vector<int> data = {9, 1, 8, 2, 7, 3};
// 4번째로 작은 요소를 찾음 (인덱스 3)
std::nth_element(data.begin(), data.begin() + 3, data.end());
// data[3]은 '7'이 됨. data[0..2] <= 7 <= data[4..5]
3.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> sortedData = {10, 20, 20, 30, 50};
// '20' 존재 여부 확인
bool found = std::binary_search(sortedData.begin(), sortedData.end(), 20); // true
// '20' 이상의 첫 위치 반환
auto lowIter = std::lower_bound(sortedData.begin(), sortedData.end(), 20);
std::cout << "lower_bound index: " << (lowIter - sortedData.begin()) << std::endl; // 출력: 1
// '20'보다 큰 첫 위치 반환
auto upIter = std::upper_bound(sortedData.begin(), sortedData.end(), 20);
std::cout << "upper_bound index: " << (upIter - sortedData.begin()) << std::endl; // 출력: 3
3.4 merge
두 개의 정렬된 범위를 병합하여, 정렬된 상태의 새로운 컨테이너를 만든다.
std::vector<int> front = {2, 4, 6};
std::vector<int> back = {1, 3, 5};
std::vector<int> merged(front.size() + back.size());
std::merge(front.begin(), front.end(), back.begin(), back.end(), merged.begin());
// merged: {1, 2, 3, 4, 5, 6}
4. 힙(Heap) 관련 알고리즘
STL은 범위를 힙 자료구조로 다루기 위한 함수들을 제공한다. (make_heap, push_heap, pop_heap, sort_heap)
std::vector<int> heapData = {30, 10, 20, 5, 15};
std::make_heap(heapData.begin(), heapData.end()); // 최대 힙 생성: {30, 15, 20, 5, 10}
heapData.push_back(25);
std::push_heap(heapData.begin(), heapData.end()); // 새 요소를 힙에 추가: {30, 25, 20, 5, 10, 15}
std::pop_heap(heapData.begin(), heapData.end()); // 최대값을 마지막으로 이동: {25, 15, 20, 5, 10, 30}
int maxVal = heapData.back(); // 최대값 30 획득
heapData.pop_back(); // 최대값 제거
std::sort_heap(heapData.begin(), heapData.end());
// 힙을 오름차순으로 정렬: {5, 10, 15, 20, 25}
5. 최소/최대값 관련 알고리즘
5.1 min & max
두 값 또는 초기화 리스트 내의 최소/최대값을 반환한다.
int a = 100, b = 50;
int minVal = std::min(a, b); // 50
int maxVal = std::max(a, b); // 100
auto minFromList = std::min({8, 3, 12, 5}); // 3
auto maxFromList = std::max({8, 3, 12, 5}); // 12
5.2 min_element & max_element
범위 내에서 최소/최대 요소의 반복자를 반환한다.
std::vector<int> scores = {88, 72, 95, 61, 84};
auto minScoreIter = std::min_element(scores.begin(), scores.end()); // 61을 가리킴
auto maxScoreIter = std::max_element(scores.begin(), scores.end()); // 95를 가리킴
5.3 minmax_element (C++11)
범위 내에서 최소와 최대 요소의 반복자를 한 번에 반환한다.
std::vector<int> values = {45, 12, 78, 23, 56};
auto minmaxPair = std::minmax_element(values.begin(), values.end());
// minmaxPair.first는 12를 가리킴, minmaxPair.second는 78을 가리킴
6. 수치 연산 알고리즘 (<numeric> 헤더)
6.1 accumulate
범위 요소의 누적 합계(또는 사용자 정의 연산)를 계산한다.
#include <numeric>
std::vector<int> quantities = {10, 20, 30, 40};
int total = std::accumulate(quantities.begin(), quantities.end(), 0); // 총합: 100
int product = std::accumulate(quantities.begin(), quantities.end(), 1, std::multiplies<int>()); // 곱: 240000
6.2 inner_product
두 범위의 내적(또는 사용자 정의 연산)을 계산한다.
std::vector<int> va = {2, 3, 4};
std::vector<int> vb = {5, 6, 7};
int dotProduct = std::inner_product(va.begin(), va.end(), vb.begin(), 0); // 2*5 + 3*6 + 4*7 = 56
6.3 iota
특정 시작값부터 1씩 증가하는 연속된 값으로 범위를 채운다.
std::vector<int> seq(6);
std::iota(seq.begin(), seq.end(), 100); // seq: {100, 101, 102, 103, 104, 105}
6.4 partial_sum
범위의 부분 합을 계산하여 결과 범위에 저장한다.
std::vector<int> in = {1, 2, 3, 4, 5};
std::vector<int> out(in.size());
std::partial_sum(in.begin(), in.end(), out.begin());
// out: {1, 3, 6, 10, 15}
6.5 adjacent_difference
인접한 요소 간의 차이를 계산하여 결과 범위에 저장한다.
std::vector<int> in = {10, 20, 30, 40, 50};
std::vector<int> out(in.size());
std::adjacent_difference(in.begin(), in.end(), out.begin());
// out: {10, 10, 10, 10, 10}
7. 기타 유틸리티 알고리즘
7.1 generate & generate_n
함수(또는 람다)가 반환하는 값으로 범위를 채운다.
std::vector<int> container(5);
int counter = 0;
std::generate(container.begin(), container.end(), [&counter]() {
return counter++;
}); // container: {0, 1, 2, 3, 4}
// 앞의 3개 요소만 채우기
std::vector<int> partial(5, -1);
int startVal = 10;
std::generate_n(partial.begin(), 3, [&startVal]() {
return startVal++;
}); // partial: {10, 11, 12, -1, -1}
7.2 includes
정렬된 범위가 다른 정렬된 범위의 모든 요소를 포함하는지 검사한다.
std::vector<int> superset = {1, 2, 3, 4, 5};
std::vector<int> subset = {2, 4};
bool isIncluded = std::includes(superset.begin(), superset.end(),
subset.begin(), subset.end()); // true
7.3 집합 연산: set_union, set_intersection 등
합집합, 교집합, 차집합, 대칭 차집합을 계산한다. 입력 범위는 정렬되어 있어야 한다.
std::vector<int> setA = {1, 2, 3, 4, 5};
std::vector<int> setB = {3, 4, 5, 6, 7};
std::vector<int> result;
// 합집합
std::set_union(setA.begin(), setA.end(), setB.begin(), setB.end(),
std::back_inserter(result));
// result: {1, 2, 3, 4, 5, 6, 7}
// 교집합
result.clear();
std::set_intersection(setA.begin(), setA.end(), setB.begin(), setB.end(),
std::back_inserter(result));
// result: {3, 4, 5}
// 차집합 (A - B)
result.clear();
std::set_difference(setA.begin(), setA.end(), setB.begin(), setB.end(),
std::back_inserter(result));
// result: {1, 2}
// 대칭 차집합 (A ∪ B - A ∩ B)
result.clear();
std::set_symmetric_difference(setA.begin(), setA.end(), setB.begin(), setB.end(),
std::back_inserter(result));
// result: {1, 2, 6, 7}
8. 자주 묻는 질문
sort와stable_sort의 차이점은?
sort는 불안정 정렬(intro sort)을 사용하므로, 동일한 값을 가진 요소들의 상대적 순서가 유지되지 않을 수 있다. 반면stable_sort는 안정 정렬(merge sort 기반)을 사용하여 동등한 요소들의 원래 순서를 보장한다.stable_sort는sort보다 메모리를 더 사용할 수 있다.- 왜
remove를 사용한 후에 반드시erase를 호출해야 하나?
remove알고리즘은 실제로 메모리에서 요소를 삭제하는 것이 아니라, 유지할 요소를 앞쪽으로 이동시키고 '논리적 끝'을 가리키는 반복자만 반환한다. 컨테이너의 크기(size)는 변하지 않는다. 물리적으로 요소를 제거하고 크기를 변경하려면erase를 호출해야 한다. 이를 두 단계로 나누는 이유는remove가 컨테이너의 구조에 독립적으로 동작할 수 있도록 하기 위함이다. - 사용 전에 반드시 정렬이 필요한 알고리즘의 종류는?
이분 탐색 계열(binary_search,lower_bound,upper_bound), 집합 연산(set_union,set_intersection등),merge,includes등은 로그 또는 선형 시간 복잡도로 동작하기 위해 입력 데이터가 정렬되어 있어야 한다. 정렬되지 않은 데이터에 사용하면 예측 불가능한 결과나 잘못된 출력이 발생할 수 있다.