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): 부분 시퀀스가 마지막으로 나타나는 위치를 찾음
std::vector<int> 데이터 = {10, 30, 50, 70, 90};
// 값 50을 찾기
auto 반복자 = std::find(데이터.begin(), 데이터.end(), 50);
if (반복자 != 데이터.end()) {
std::cout << "찾음: " << *반복자 << std::endl; // 출력: 50
}
// 6보다 큰 첫 번째 요소 찾기
auto 반복자2 = std::find_if(데이터.begin(), 데이터.end(), [](int x) {
return x > 60;
});
std::cout << "첫 번째 >6: " << *반복자2 << std::endl; // 출력: 70
// 부분 시퀀스 찾기
std::vector<int> 부분 = {30, 50};
auto 반복자3 = std::find_end(데이터.begin(), 데이터.end(), 부분.begin(), 부분.end());
if (반복자3 != 데이터.end()) {
std::cout << "부분 시퀀스 시작 인덱스: " << 반복자3 - 데이터.begin() << std::endl; // 출력: 1
}
1.2 count와 count_if
count(begin, end, value):value와 같은 요소의 개수를 셉니다count_if(begin, end, predicate): 조건자를 만족하는 요소의 개수를 셉니다
std::vector<int> 컬렉션 = {1, 2, 3, 2, 4, 2};
int 개수 = std::count(컬렉션.begin(), 컬렉션.end(), 2); // 2의 개수 세기, 결과 3
int 짝수개수 = std::count_if(컬렉션.begin(), 컬렉션.end(), [](int x) {
return x % 2 == 0;
}); // 짝수 개수, 결과 3
1.3 for_each
범위의 각 요소에 함수를 적용합니다
std::vector<int> 숫자들 = {1, 2, 3, 4, 5};
std::for_each(숫자들.begin(), 숫자들.end(), [](int& x) {
x *= 2; // 각 요소를 2배로 만듦
});
// 이제 숫자들은 {2, 4, 6, 8, 10}이 됨
1.4 equal과 mismatch
equal(b1, e1, b2): 두 범위[b1,e1)와[b2, b2+(e1-b1))가 같은지 판단mismatch(b1, e1, b2): 두 범위에서 첫 번로 다른 요소의 반복자 쌍(pair)을 반환
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 동일 = std::equal(벡터A.begin(), 벡터A.end(), 벡터B.begin());
std::cout << "A == B? " << std::boolalpha << 동일 << std::endl; // 출력: false
// 벡터A와 벡터C의 첫 번로 다른 요소 찾기
auto 불일치 = std::mismatch(벡터A.begin(), 벡터A.end(), 벡터C.begin());
if (불일치.first != 벡터A.end()) {
std::cout << "불일치: " << *불일치.first << " vs " << *불일치.second << std::endl; // 출력 없음 (A와 C의 첫 3 요소 동일)
}
1.5 all_of, any_of, none_of
범위 내 요소가 모두, 일부 또는 전혀 조건을 만족하는지 확인
std::vector<int> 데이터 = {2, 4, 6, 8};
bool 모두짝수 = std::all_of(데이터.begin(), 데이터.end(), [](int x) {
return x % 2 == 0;
}); // true
bool 홀수존재 = std::any_of(데이터.begin(), 데이터.end(), [](int x) {
return x % 2 != 0;
}); // false
bool 음수없음 = std::none_of(데이터.begin(), 데이터.end(), [](int x) {
return x < 0;
}); // true
2. 변경되는 시퀀스 알고리즘
이 알고리즘들은 작업하는 컨테이너의 요소를 변경합니다.
2.1 copy와 copy_if
copy(begin, end, dest):[begin, end)의 요소를dest시작 위치로 복사copy_if(begin, end, dest, predicate): 조건자를 만족하는 요소만dest로 복사
std::vector<int> 원본 = {1, 2, 3, 4, 5};
std::vector<int> 대상(5); // 충분한 공간을 미리 할당
// 모든 요소 복사
std::copy(원본.begin(), 원본.end(), 대상.begin()); // 대상: [1,2,3,4,5]
// 짝수 요소만 새 컨테이너로 복사
std::vector<int> 짝수들;
std::copy_if(원본.begin(), 원본.end(), std::back_inserter(짝수들), [](int x) {
return x % 2 == 0;
}); // 짝수들: [2,4]
주의: back_inserter(대상)는 자동으로 push_back을 호출하므로 미리 공간을 할당할 필요가 없습니다.
2.2 transform
범위의 각 요소에 함수를 적용하고 결과를 다른 범위에 저장
std::vector<int> 숫자들 = {1, 2, 3};
std::vector<int> 제곱수(3);
// 제곱 계산 (단일 매개변수 변환)
std::transform(숫자들.begin(), 숫자들.end(), 제곱수.begin(), [](int x) {
return x * x;
}); // 제곱수: [1,4,9]
// 두 컨테이너 요소 더하기 (이중 매개변수 변환)
std::vector<int> A = {1, 2, 3};
std::vector<int> B = {4, 5, 6};
std::vector<int> 합(3);
std::transform(A.begin(), A.end(), B.begin(), 합.begin(), [](int x, int y) {
return x + y;
}); // 합: [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> 데이터 = {1, 2, 3, 2, 5};
// 모든 2를 20으로 교체
std::replace(데이터.begin(), 데이터.end(), 2, 20); // 데이터: [1,20,3,20,5]
// 10보다 큰 요소를 0으로 교체
std::replace_if(데이터.begin(), 데이터.end(), [](int x) {
return x > 10;
}, 0); // 데이터: [1,0,3,0,5]
// 복사 시 3을 300으로 교체 (원본 컨테이너 변경 없음)
std::vector<int> 결과;
std::replace_copy(데이터.begin(), 데이터.end(), std::back_inserter(결과), 3, 300); // 결과: [1,0,300,0,5]
2.4 remove, remove_if와 erase
remove(begin, end, value):value와 같은 요소를 "이동"하여 컨테이너 끝으로 보내고, 새로운 논리적 끝 반복자를 반환 (실제로 요소를 삭제하지 않음,erase와 함께 사용 필요)remove_if(begin, end, predicate): 조건자를 만족하는 요소를 끝으로 이동
std::vector<int> 데이터 = {1, 2, 3, 2, 4};
// 모든 2를 논리적으로 삭제 (끝으로 이동)
auto 새끝 = std::remove(데이터.begin(), 데이터.end(), 2); // 데이터: [1,3,4,2,2]
// 물리적 삭제 (실제로 요소 제거)
데이터.erase(새끝, 데이터.end()); // 데이터: [1,3,4]
// 람다와 함께 짝수 삭제
데이터 = {1, 2, 3, 4, 5};
데이터.erase(std::remove_if(데이터.begin(), 데이터.end(), [](int x) {
return x % 2 == 0;
}), 데이터.end()); // 데이터: [1,3,5]
2.5 unique
연속된 중복 요소를 제거하고 새로운 논리적 끝 반복자를 반환. 일반적으로 erase와 함께 사용됩니다.
std::vector<int> 컬렉션 = {1, 1, 2, 2, 3, 3, 3, 4, 5};
auto 마지막 = std::unique(컬렉션.begin(), 컬렉션.end());
컬렉션.erase(마지막, 컬렉션.end()); // 컬렉션이 {1, 2, 3, 4, 5}로 변경됨
2.6 reverse
범위 내 요소의 순서를 반전시킵니다
std::vector<int> 컬렉션 = {1, 2, 3, 4, 5};
std::reverse(컬렉션.begin(), 컬렉션.end()); // 컬렉션이 {5, 4, 3, 2, 1}로 변경됨
2.7 rotate
범위를 회전하여 중간 요소를 새로운 첫 번째 요소로 만듭니다
std::vector<int> 컬렉션 = {1, 2, 3, 4, 5};
std::rotate(컬렉션.begin(), 컬렉션.begin() + 2, 컬렉션.end()); // 3을 시작점으로 회전, 컬렉션이 {3, 4, 5, 1, 2}로 변경됨
2.8 shuffle
범위 내 요소를 무작위로 재배열합니다 (C++11 이상 필요)
#include <random>
#include <algorithm>
std::vector<int> 컬렉션 = {1, 2, 3, 4, 5};
std::random_device rd;
std::mt19937 g(rd());
std::shuffle(컬렉션.begin(), 컬렉션.end(), g); // 컬렉션의 요소를 무작위로 섞음
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> 데이터 = {5, 3, 1, 4, 2};
std::sort(데이터.begin(), 데이터.end()); // 기본 오름차순, 데이터가 {1, 2, 3, 4, 5}로 변경됨
std::sort(데이터.begin(), 데이터.end(), std::greater<int>()); // 내림차순, 데이터가 {5, 4, 3, 2, 1}로 변경됨
std::sort(데이터.begin(), 데이터.end(), [](int a, int b) {
return a < b;
}); // 오름차순, 사용자 정의 비교
std::vector<std::pair<int, int>> 쌍들 = {{1, 2}, {2, 1}, {1, 1}, {2, 2}};
std::stable_sort(쌍들.begin(), 쌍들.end(), [](const auto& a, const auto& b) {
return a.first < b.first; // first 기준 정렬, 같은 요소의 상대적 순서 유지
});
std::vector<int> 데이터 = {5, 3, 1, 4, 2, 6};
// 가장 작은 3개 요소를 앞에 가져와 정렬
std::partial_sort(데이터.begin(), 데이터.begin() + 3, 데이터.end());
// 이제 데이터의 첫 3 요소는 1, 2, 3이고, 뒤는 정렬되지 않은 4, 5, 6임
3.2 nth_element
범위를 재배열하여 지정된 위치의 요소가 정렬된 위치에 오도록 하고, 왼쪽 요소들은 그것보다 작거나 같고, 오른쪽 요소들은 그것보다 크거나 같도록 만듭니다
std::vector<int> 데이터 = {5, 3, 1, 4, 2, 6};
// 세 번째로 작은 요소(인덱스 2) 찾기
std::nth_element(데이터.begin(), 데이터.begin() + 2, 데이터.end());
// 이제 데이터[2]는 3이고, 왼쪽 요소들은 <=3이고, 오른쪽 요소들은 >=3임
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> 정렬된 = {1, 3, 3, 5, 7}; // 반드시 먼저 정렬되어야 함
// 3이 존재하는지 확인
bool 존재 = std::binary_search(정렬된.begin(), 정렬된.end(), 3); // true
// 첫 번째 >=3인 요소 찾기
auto 하한 = std::lower_bound(정렬된.begin(), 정렬된.end(), 3);
std::cout << "하한 인덱스: " << 하한 - 정렬된.begin() << std::endl; // 출력: 1
// 첫 번째 >3인 요소 찾기
auto 상한 = std::upper_bound(정렬된.begin(), 정렬된.end(), 3);
std::cout << "상한 인덱스: " << 상한 - 정렬된.begin() << std::endl; // 출력: 3
3.4 merge
두 개의 정렬된 범위를 새 컨테이너로 병합 (정렬 유지)
std::vector<int> A = {1, 3, 5};
std::vector<int> B = {2, 4, 6};
std::vector<int> 병합된(A.size() + B.size());
// A와 B 병합 (둘 다 정렬되어야 함)
std::merge(A.begin(), A.end(), B.begin(), B.end(), 병합된.begin()); // 병합된: [1,2,3,4,5,6]
4. 힙 알고리즘
STL은 범위를 힙으로 조작하는 알고리즘인 make_heap, push_heap, pop_heap, sort_heap 등을 제공합니다.
std::vector<int> 데이터 = {4, 1, 3, 2, 5};
std::make_heap(데이터.begin(), 데이터.end()); // 최대 힙 구성, 데이터가 {5, 4, 3, 2, 1}로 변경됨
데이터.push_back(6);
std::push_heap(데이터.begin(), 데이터.end()); // 새 요소를 힙에 추가, 데이터가 {6, 4, 5, 2, 1, 3}로 변경됨
std::pop_heap(데이터.begin(), 데이터.end()); // 최대 요소를 끝으로 이동, 데이터가 {5, 4, 3, 2, 1, 6}로 변경됨
int 최대값 = 데이터.back(); // 최대 요소 6 가져오기
데이터.pop_back(); // 최대 요소 제거
std::sort_heap(데이터.begin(), 데이터.end()); // 힙을 오름차순 시퀀스로 정렬, 데이터가 {1, 2, 3, 4, 5}로 변경됨
5. 최소/최대값 알고리즘
5.1 min과 max
두 값 또는 초기화 목록에서 최소/최대값을 반환
int a = 5, b = 3;
int 최소값 = std::min(a, b); // 3
int 최대값 = std::max(a, b); // 5
auto 목록최소 = std::min({4, 2, 8, 5, 1}); // 1
auto 목록최대 = std::max({4, 2, 8, 5, 1}); // 8
5.2 min_element와 max_element
범위 내 최소/최대 요소의 반복자를 반환
std::vector<int> 데이터 = {3, 1, 4, 2, 5};
auto 최소반복자 = std::min_element(데이터.begin(), 데이터.end()); // 1을 가리킴
auto 최대반복자 = std::max_element(데이터.begin(), 데이터.end()); // 5를 가리킴
5.3 minmax_element (C++11)
범위 내 최소와 최대 요소의 반복자를 동시에 반환
std::vector<int> 데이터 = {3, 1, 4, 2, 5};
auto 최소최대 = std::minmax_element(데이터.begin(), 데이터.end());
// 최소최대.first는 1을, 최소최대.second는 5를 가리킴
6. 수치 알고리즘 (<numeric>에 있음)
6.1 accumulate
범위 내 요소의 누적 합을 계산 (또는 사용자 정의 작업)
#include <numeric>
std::vector<int> 데이터 = {1, 2, 3, 4, 5};
int 합 = std::accumulate(데이터.begin(), 데이터.end(), 0); // 합, 초기값 0, 결과 15
int 곱 = std::accumulate(데이터.begin(), 데이터.end(), 1, std::multiplies<int>()); // 곱, 초기값 1, 결과 120
6.2 inner_product
두 범위의 내적을 계산 (또는 사용자 정의 작업)
std::vector<int> A = {1, 2, 3};
std::vector<int> B = {4, 5, 6};
int 내적 = std::inner_product(A.begin(), A.end(), B.begin(), 0); // 1*4 + 2*5 + 3*6 = 32
6.3 iota
연속적으로 증가하는 값으로 범위를 채웁니다
std::vector<int> 데이터(5);
std::iota(데이터.begin(), 데이터.end(), 10); // 10, 11, 12, 13, 14로 채움
6.4 partial_sum
부분 합을 계산하고 결과를 대상 범위에 저장
std::vector<int> 원본 = {1, 2, 3, 4, 5};
std::vector<int> 목표(원본.size());
std::partial_sum(원본.begin(), 원본.end(), 목표.begin()); // 목표가 {1, 3, 6, 10, 15}로 변경됨
6.5 adjacent_difference
인접 요소의 차이를 계산하고 결과를 대상 범위에 저장
std::vector<int> 원본 = {1, 2, 3, 4, 5};
std::vector<int> 목표(원본.size());
std::adjacent_difference(원본.begin(), 원본.end(), 목표.begin()); // 목표가 {1, 1, 1, 1, 1}로 변경됨
7. 기타 알고리즘
7.1 generate
생성 함수로 범위를 채웁니다
std::vector<int> 데이터(5);
int n = 0;
std::generate(데이터.begin(), 데이터.end(), [&n]() {
return n++;
}); // 0, 1, 2, 3, 4로 채움
7.2 generate_n
생성 함수로 범위의 처음 n개 요소를 채웁니다
std::vector<int> 데이터(5);
int n = 10;
std::generate_n(데이터.begin(), 3, [&n]() {
return n++;
}); // 처음 3 요소가 10, 11, 12로 채워지고, 나머지는 변경되지 않음
7.3 includes
정렬된 범위가 다른 정렬된 범위의 모든 요소를 포함하는지 확인
std::vector<int> 벡터1 = {1, 2, 3, 4, 5};
std::vector<int> 벡터2 = {2, 4};
bool 포함 = std::includes(벡터1.begin(), 벡터1.end(), 벡터2.begin(), 벡터2.end()); // true
7.4 set_union, set_intersection, set_difference, set_symmetric_difference
집합 연산 수행: 합집합, 교집합, 차집합, 대칭차집합
std::vector<int> V1 = {1, 2, 3, 4, 5};
std::vector<int> V2 = {3, 4, 5, 6, 7};
std::vector<int> 결과;
// 합집합
std::set_union(V1.begin(), V1.end(), V2.begin(), V2.end(), std::back_inserter(결과));
// 결과가 {1, 2, 3, 4, 5, 6, 7}로 됨
// 교집합
결과.clear();
std::set_intersection(V1.begin(), V1.end(), V2.begin(), V2.end(), std::back_inserter(결과));
// 결과가 {3, 4, 5}로 됨
// 차집합 (V1 - V2)
결과.clear();
std::set_difference(V1.begin(), V1.end(), V2.begin(), V2.end(), std::back_inserter(결과));
// 결과가 {1, 2}로 됨
// 대칭차집합 (V1 ∪ V2 - V1 ∩ V2)
결과.clear();
std::set_symmetric_difference(V1.begin(), V1.end(), V2.begin(), V2.end(), std::back_inserter(결과));
// 결과가 {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(remove(...), container.end())와 같이 함께 사용해야 합니다.
- 어떤 알고리즘은 컨테이너가 정렬되어 있어야 하나요?
이진 검색 시리즈(binary_search, lower_bound, upper_bound), 집합 알고리즘(set_intersection, set_union 등), merge 등은 정렬된 상태를 의존하여 효율적인 작업(예: 이진 검색 O(log n))을 수행합니다.