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> numbers = {1, 3, 5, 7, 9};

// 5 검색
auto iter = find(numbers.begin(), numbers.end(), 5);
if (iter != numbers.end()) {
    std::cout << "found: " << *iter << std::endl;  // 출력: 5
}

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

// 하위 시퀀스 검색
std::vector<int> sub = {3, 5};
auto iter3 = find_end(numbers.begin(), numbers.end(), sub.begin(), sub.end());
if (iter3 != numbers.end()) {
    std::cout << "subsequence starts at index: " << iter3 - numbers.begin() << std::endl;  // 출력: 1
}

1.2 count 및 count_if

• count(begin, end, value): value와 같은 요소 개수를 세웁니다.
• count_if(begin, end, predicate): 조건식을 만족하는 요소 개수를 세웁니다.

std::vector<int> vec = {1, 2, 3, 2, 4, 2};
int cnt = std::count(vec.begin(), vec.end(), 2); // 2의 개수는 3
int even_cnt = std::count_if(vec.begin(), vec.end(), [](int x) { 
    return x % 2 == 0; 
}); // 짝수 개수는 4

1.3 for_each

범위 내 모든 요소에 함수를 적용합니다.

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}

1.4 equal 및 mismatch

• equal(b1, e1, b2): 두 범위 [b1,e1)과 [b2, b2+(e1-b1))가 동일한지 확인합니다.
• mismatch(b1, e1, b2): 두 범위에서 처음으로 다른 요소의 반복자를 반환합니다.

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 = equal(a.begin(), a.end(), b.begin());
std::cout << "a == b? " << std::boolalpha << is_equal << std::endl;  // 출력: false

// a와 c의 첫 번째 불일치 요소 찾기
auto mis = mismatch(a.begin(), a.end(), c.begin());
if (mis.first != a.end()) {
    std::cout << "mismatch: " << *mis.first << " vs " << *mis.second << std::endl;  // 출력 없음
}

1.5 all_of, any_of, none_of

범위 내 요소가 모두, 일부 또는 아무것도 조건을 만족하는지 확인합니다.

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

2. 수정 시퀀스 알고리즘

이 알고리즘들은 처리하는 컨테이너의 요소를 수정합니다.

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);  // 충분한 공간을 미리 할당해야 합니다

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

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

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

2.2 transform

범위 내 각 요소에 함수를 적용하고 결과를 다른 범위에 저장합니다.

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

// 제곱 계산 (단일 인수 변환)
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(3);
transform(a.begin(), a.end(), b.begin(), sum.begin(), [](int x, int y) {
    return x + y;
});  // sum: [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으로 교체
replace(numbers.begin(), numbers.end(), 2, 20);  // numbers: [1,20,3,20,5]

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

// 3을 300으로 교체한 후 복사(원본은 변경되지 않음)
std::vector<int> result;
replace_copy(numbers.begin(), numbers.end(), std::back_inserter(result), 3, 300);  // result: [1,0,300,0,5]

2.4 remove, remove_if 및 erase

• remove(begin, end, value): value와 같은 요소를 컨테이너 끝으로 이동합니다. 실제로 요소를 삭제하지 않습니다.
• remove_if(begin, end, predicate): 조건식을 만족하는 요소를 끝으로 이동합니다.

std::vector<int> numbers = {1, 2, 3, 2, 4};

// 모든 2를 논리적으로 삭제(끝으로 이동)
auto new_end = remove(numbers.begin(), numbers.end(), 2);  // numbers: [1,3,4,2,2]

// 물리적으로 삭제(요소 제거)
numbers.erase(new_end, numbers.end());  // numbers: [1,3,4]

// 람다와 함께 홀수 삭제
numbers = {1, 2, 3, 4, 5};
numbers.erase(remove_if(numbers.begin(), numbers.end(), [](int x) {
    return x % 2 == 0;
}), numbers.end());  // numbers: [1,3,5]

2.5 unique

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

std::vector<int> vec = {1, 1, 2, 2, 3, 3, 3, 4, 5};
auto last = std::unique(vec.begin(), vec.end());
vec.erase(last, vec.end()); // vec: {1, 2, 3, 4, 5}

2.6 reverse

범위 내 요소 순서를 반전합니다.

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

2.7 rotate

범위 내 요소를 회전시켜 중간 요소를 새로운 첫 번째 요소로 만듭니다.

std::vector<int> vec = {1, 2, 3, 4, 5};
std::rotate(vec.begin(), vec.begin() + 2, vec.end()); // 3을 기준으로 회전, vec: {3, 4, 5, 1, 2}

2.8 shuffle

범위 내 요소를 무작위로 재배열합니다(C++11 이상 필요).

#include <random>
#include <algorithm>

std::vector<int> vec = {1, 2, 3, 4, 5};
std::random_device rd;
std::mt19937 g(rd());
std::shuffle(vec.begin(), vec.end(), g); // vec 요소 무작위로 재배열

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> vec = {5, 3, 1, 4, 2};
std::sort(vec.begin(), vec.end()); // 기본 오름차순, vec: {1, 2, 3, 4, 5}
std::sort(vec.begin(), vec.end(), std::greater<int>()); // 내림차순, vec: {5, 4, 3, 2, 1}
std::sort(vec.begin(), vec.end(), [](int a, int b) { 
    return a < b; 
}); // 오름차순, 사용자 정의 비교

std::vector> vec = {{1, 2}, {2, 1}, {1, 1}, {2, 2}};
std::stable_sort(vec.begin(), vec.end(), [](const auto& a, const auto& b) {
    return a.first < b.first; // first 기준 정렬, 동일 요소의 상대 순서 유지
});

std::vector<int> vec = {5, 3, 1, 4, 2, 6};
// 가장 작은 3개 요소를 앞에 정렬
std::partial_sort(vec.begin(), vec.begin() + 3, vec.end());
// vec 앞 3개 요소는 1, 2, 3, 나머지는 정렬되지 않은 4, 5, 6

3.2 nth_element

범위를 재배치하여 지정된 위치의 요소가 정렬된 상태가 되도록 합니다. 왼쪽 요소는 모두 그보다 작거나 같고, 오른쪽 요소는 모두 그보다 크거나 같습니다.

std::vector<int> vec = {5, 3, 1, 4, 2, 6};
// 세 번째로 작은 요소(인덱스 2)
std::nth_element(vec.begin(), vec.begin() + 2, vec.end());
// vec[2]는 3, 왼쪽 요소는 3보다 작거나 같고, 오른쪽 요소는 3보다 크거나 같습니다

3.3 binary_search, lower_bound, upper_bound

이 알고리즘들은 정렬된 컨테이너에서 사용해야 합니다.

• binary_search(begin, end, value): value가 존재하는지 확인합니다(불린 반환).
• lower_bound(begin, end, value): value보다 크거나 같은 첫 번째 요소의 반복자를 반환합니다.
• upper_bound(begin, end, value): value보다 큰 첫 번째 요소의 반복자를 반환합니다.

std::vector<int> sorted = {1, 3, 3, 5, 7};  // 반드시 정렬되어야 합니다

// 3 존재 여부 확인
bool exists = binary_search(sorted.begin(), sorted.end(), 3);  // true

// 첫 번째 3 이상 요소 찾기
auto lb = lower_bound(sorted.begin(), sorted.end(), 3);
std::cout << "lower_bound index: " << lb - sorted.begin() << std::endl;  // 출력: 1

// 첫 번째 3 초과 요소 찾기
auto ub = upper_bound(sorted.begin(), sorted.end(), 3);
std::cout << "upper_bound index: " << ub - sorted.begin() << std::endl;  // 출력: 3

3.4 merge

두 정렬된 범위를 새로운 컨테이너로 병합합니다(정렬 상태 유지).

std::vector<int> a = {1, 3, 5};
std::vector<int> b = {2, 4, 6};
std::vector<int> merged(a.size() + b.size());

// a와 b 병합(정렬되어 있어야 합니다)
merge(a.begin(), a.end(), b.begin(), b.end(), merged.begin());  // merged: [1,2,3,4,5,6]

4. 힙 알고리즘

STL은 범위를 힙으로 조작하는 알고리즘을 제공합니다. make_heap, push_heap, pop_heap, sort_heap 등이 있습니다.

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}
int max_val = vec.back(); // 최대 요소 6 얻기
vec.pop_back(); // 최대 요소 제거

std::sort_heap(vec.begin(), vec.end()); // 힙을 오름차순으로 정렬, vec: {1, 2, 3, 4, 5}

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

5.1 min 및 max

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

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

auto min_of_list = std::min({4, 2, 8, 5, 1}); // 1
auto max_of_list = std::max({4, 2, 8, 5, 1}); // 8

5.2 min_element 및 max_element

범위 내 최소/최대 요소의 반복자를 반환합니다.

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를 가리킴

5.3 minmax_element (C++11)

범위 내 최소 및 최대 요소의 반복자를 동시에 반환합니다.

std::vector<int> vec = {3, 1, 4, 2, 5};
auto minmax = std::minmax_element(vec.begin(), vec.end());
// minmax.first는 1을 가리키고, minmax.second는 5을 가리킴

6. 수치 알고리즘 (<numeric> 포함)

6.1 accumulate

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

#include <numeric>

std::vector<int> vec = {1, 2, 3, 4, 5};
int sum = std::accumulate(vec.begin(), vec.end(), 0); // 합계, 초기값 0, 결과 15
int product = std::accumulate(vec.begin(), vec.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 dot = std::inner_product(a.begin(), a.end(), b.begin(), 0); // 1*4 + 2*5 + 3*6 = 32

6.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> src = {1, 2, 3, 4, 5};
std::vector<int> dst(src.size());
std::partial_sum(src.begin(), src.end(), dst.begin()); // dst: {1, 3, 6, 10, 15}

6.5 adjacent_difference

연속 요소의 차이를 계산하고 결과를 대상 범위에 저장합니다.

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

7. 기타

7.1 generate

생성 함수로 범위를 채웁니다.

std::vector<int> vec(5);
int n = 0;
std::generate(vec.begin(), vec.end(), [&n]() { 
    return n++; 
}); // 0, 1, 2, 3, 4로 채움

7.2 generate_n

생성 함수로 범위의 처음 n개 요소를 채웁니다.

std::vector<int> vec(5);
int n = 10;
std::generate_n(vec.begin(), 3, [&n]() { 
    return n++; 
}); // 처음 3개 요소는 10, 11, 12, 나머지는 변경되지 않음

7.3 includes

정렬된 범위가 다른 정렬된 범위의 모든 요소를 포함하는지 확인합니다.

std::vector<int> vec1 = {1, 2, 3, 4, 5};
std::vector<int> vec2 = {2, 4};
bool includes = std::includes(vec1.begin(), vec1.end(), vec2.begin(), vec2.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> result;

// 합집합
std::set_union(v1.begin(), v1.end(), v2.begin(), v2.end(), std::back_inserter(result));
// result: {1, 2, 3, 4, 5, 6, 7}

// 교집합
result.clear();
std::set_intersection(v1.begin(), v1.end(), v2.begin(), v2.end(), std::back_inserter(result));
// result: {3, 4, 5}

// 차집합 (v1 - v2)
result.clear();
std::set_difference(v1.begin(), v1.end(), v2.begin(), v2.end(), std::back_inserter(result));
// result: {1, 2}

// 대칭 차집합 (v1 ∪ v2 - v1 ∩ v2)
result.clear();
std::set_symmetric_difference(v1.begin(), v1.end(), v2.begin(), v2.end(), std::back_inserter(result));
// result: {1, 2, 6, 7}

8. 일반적인 질문

1. sort와 stable_sort의 차이점은 무엇인가요?
• sort는 빠른 정렬(실제로는 introsort 알고리즘)을 사용합니다. 불안정(같은 요소의 상대 순서가 바뀔 수 있음), 평균 시간 복잡도 O(n log n).
• stable_sort는 병합 정렬을 사용합니다. 안정적(같은 요소의 상대 순서 유지), 시간 복잡도 O(n log n), 공간 사용량이 약간 더 많습니다.
2. remove 알고리즘이 erase와 함께 사용되어야 하는 이유는 무엇인가요?
• remove 알고리즘은 삭제할 요소를 "덮어쓰고" 보존된 요소를 앞쪽으로 이동시킵니다. 실제 컨테이너 크기를 수정하지 않습니다. erase는 반복자 범위를 통해 요소를 실제로 삭제하고 컨테이너 크기를 수정합니다. 따라서 함께 사용해야 합니다: container.erase(remove(...), container.end()).
3. 어떤 알고리즘이 컨테이너가 정렬되어 있어야 하나요?
• 이진 탐색 시리즈(binary_search, lower_bound, upper_bound), 집합 알고리즘(set_intersection, set_union 등), merge 등은 정렬성을 기반으로 효율적인 작업을 수행합니다(예: 이진 탐색 O(log n)).