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 ptr = std::find(data.begin(), data.end(), 6);
if (ptr != data.end()) {
    std::cout << "발견: " << *ptr << std::endl;  // 출력: 6
}

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

// 하위 시퀀스 찾기
std::vector<int> pattern = {4, 6};
auto ptr3 = std::find_end(data.begin(), data.end(), pattern.begin(), pattern.end());
if (ptr3 != data.end()) {
    std::cout << "하위 시퀀스 시작 인덱스: " << ptr3 - data.begin() << std::endl;  // 출력: 1
}

1.2 count와 count_if

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

std::vector<int> numbers = {1, 3, 3, 5, 7, 3};
int three_count = std::count(numbers.begin(), numbers.end(), 3); // 3의 개수, 결과는 3
int odd_count = std::count_if(numbers.begin(), numbers.end(), [](int n) { 
    return n % 2 != 0; 
}); // 홀수 개수, 결과는 5

1.3 for_each

범위의 각 요소에 함수를 적용합니다.

std::vector<int> values = {1, 2, 3, 4, 5};
std::for_each(values.begin(), values.end(), [](int& item) { 
    item *= 3; // 각 요소에 3을 곱함
});
// 이제 values는 {3, 6, 9, 12, 15}

1.4 equal과 mismatch

• equal(b1, e1, b2): 두 범위 [b1,e1)와 [b2, b2+(e1-b1))가 같은지 확인합니다.
• mismatch(b1, e1, b2): 두 범위에서 첫 번째로 다른 요소를 가진 반복자 쌍을 반환합니다.

std::vector<int> x = {5, 6, 7};
std::vector<int> y = {5, 6, 8};
std::vector<int> z = {5, 6, 7};

// x와 y의 처음 3개 요소 비교
bool is_same = std::equal(x.begin(), x.end(), y.begin());
std::cout << "x == y? " << std::boolalpha << is_same << std::endl;  // 출력: false

// x와 z의 첫 번째 불일치 요소 찾기
auto diff = std::mismatch(x.begin(), x.end(), z.begin());
if (diff.first != x.end()) {
    std::cout << "불일치: " << *diff.first << " vs " << *diff.second << std::endl;  // 출력 없음 (x와 z 앞 3개 요소가 동일)
}

1.5 all_of, any_of, none_of

범위의 요소가 모두, 하나라도, 또는 하나도 조건을 만족하지 않는지 확인합니다.

std::vector<int> collection = {4, 6, 8, 10};
bool all_positive = std::all_of(collection.begin(), collection.end(), [](int n) { 
    return n > 0; 
}); // true
bool any_negative = std::any_of(collection.begin(), collection.end(), [](int n) { 
    return n < 0; 
}); // false
bool none_zero = std::none_of(collection.begin(), collection.end(), [](int n) { 
    return n == 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 = {2, 4, 6, 8, 10};
std::vector<int> destination(5);  // 충분한 공간을 미리 할당해야 함

// 모든 요소 복사
std::copy(source.begin(), source.end(), destination.begin());  // destination: [2,4,6,8,10]

// 짝수만 새 컨테이너에 복사
std::vector<int> even_numbers;
std::copy_if(source.begin(), source.end(), std::back_inserter(even_numbers), [](int n) {
    return n % 2 == 0;
});  // even_numbers: [2,4,6,8,10]

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

2.2 transform

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

std::vector<int> numbers = {2, 3, 4};
std::vector<int> cubes(3);

// 큐브 계산 (단일 인자 변환)
std::transform(numbers.begin(), numbers.end(), cubes.begin(), [](int n) {
    return n * n * n;
});  // cubes: [8,27,64]

// 두 컨테이너 요소 더하기 (이중 인자 변환)
std::vector<int> first = {10, 20, 30};
std::vector<int> second = {1, 2, 3};
std::vector<int> result(3);
std::transform(first.begin(), first.end(), second.begin(), result.begin(), [](int p, int q) {
    return p + q;
});  // result: [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): 조건자를 만족하는 요소를 바꿉니다.
• replace_copy(begin, end, dest, old_val, new_val): 복사 시 요소를 바꾸지만 원래 컨테이너는 변경하지 않습니다.

std::vector<int> items = {5, 10, 15, 10, 25};

// 모든 10을 100으로 변경
std::replace(items.begin(), items.end(), 10, 100);  // items: [5,100,15,100,25]

// 50보다 큰 요소를 0으로 변경
std::replace_if(items.begin(), items.end(), [](int n) {
    return n > 50;
}, 0);  // items: [5,0,15,0,25]

// 복사 시 15를 150으로 변경 (원래 컨테이너 불변)
std::vector<int> output;
std::replace_copy(items.begin(), items.end(), std::back_inserter(output), 15, 150);  // output: [5,0,150,0,25]

2.4 remove, remove_if와 erase

• remove(begin, end, value): value와 같은 요소를 컨테이너 끝으로 "이동"하고 새로운 논리적 끝 반복자를 반환합니다 (실제로 요소를 삭제하지 않으며, erase와 함께 사용해야 함).
• remove_if(begin, end, predicate): 조건자를 만족하는 요소를 끝으로 이동합니다.

std::vector<int> collection = {3, 6, 9, 6, 12};

// 논리적으로 모든 6 삭제 (끝으로 이동)
auto new_end = std::remove(collection.begin(), collection.end(), 6);  // collection: [3,9,12,6,6]

// 물리적 삭제 (실제로 요소 제거)
collection.erase(new_end, collection.end());  // collection: [3,9,12]

// lambda와 결합하여 홀수 삭제
collection = {5, 10, 15, 20, 25};
collection.erase(std::remove_if(collection.begin(), collection.end(), [](int n) {
    return n % 2 != 0;
}), collection.end());  // collection: [10,20]

2.5 unique

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

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

2.6 reverse

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

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

2.7 rotate

범위 내 요소를 회전시켜 중간 요소가 새로운 첫 번째 요소가 되도록 합니다.

std::vector<int> items = {1, 2, 3, 4, 5};
std::rotate(items.begin(), items.begin() + 2, items.end()); // 3을 시작점으로 회전, items는 {3, 4, 5, 1, 2}가 됨

2.8 shuffle

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

#include <random>
#include <algorithm>

std::vector<int> items = {1, 2, 3, 4, 5};
std::random_device seed;
std::mt19937 generator(seed());
std::shuffle(items.begin(), items.end(), generator); // items의 요소를 무작위로 섞음

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

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

std::vector<int> numbers = {9, 5, 7, 3, 1, 8};
// 가장 작은 3개 요소를 앞에두고 정렬
std::partial_sort(numbers.begin(), numbers.begin() + 3, numbers.end());
// 이제 numbers 앞 세 요소는 1, 3, 5, 뒤에는 정렬되지 않은 7, 8, 9

3.2 nth_element

범위를 재배열하여 지정된 위치의 요소가 정렬 후 위치하고, 왼쪽의 요소는 모두 작거나 같고, 오른쪽의 요소는 모두 크거나 같습니다.

std::vector<int> numbers = {9, 5, 1, 7, 3, 8, 6};
// 세 번째로 작은 요소 찾기 (인덱스 2)
std::nth_element(numbers.begin(), numbers.begin() + 2, numbers.end());
// 이제 numbers[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> sorted_data = {2, 4, 4, 6, 8, 10};  // 먼저 정렬해야 함

// 4是否存在 확인
bool exists = std::binary_search(sorted_data.begin(), sorted_data.end(), 4);  // true

// 첫 번째 >= 4 요소 찾기
auto lower = std::lower_bound(sorted_data.begin(), sorted_data.end(), 4);
std::cout << "lower_bound 인덱스: " << lower - sorted_data.begin() << std::endl;  // 출력: 1

// 첫 번째 > 4 요소 찾기
auto upper = std::upper_bound(sorted_data.begin(), sorted_data.end(), 4);
std::cout << "upper_bound 인덱스: " << upper - sorted_data.begin() << std::endl;  // 출력: 3

3.4 merge

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

std::vector<int> left = {2, 4, 6};
std::vector<int> right = {1, 3, 5};
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 = {8, 3, 6, 2, 10};
std::make_heap(heap_data.begin(), heap_data.end()); // 최대 힙 구축, heap_data는 {10, 8, 6, 2, 3}이 됨

heap_data.push_back(12);
std::push_heap(heap_data.begin(), heap_data.end()); // 새 요소를 힙에 추가, heap_data는 {12, 8, 10, 2, 3, 6}이 됨

std::pop_heap(heap_data.begin(), heap_data.end()); // 최대 요소를 끝으로 이동, heap_data는 {10, 8, 6, 2, 3, 12}이 됨
int top_value = heap_data.back(); // 최대 요소 12 가져오기
heap_pop_back(); // 최대 요소 제거

std::sort_heap(heap_data.begin(), heap_data.end()); // 힙을 오름차순으로 정렬, heap_data는 {2, 3, 6, 8, 10}이 됨

5. 최소/최대 알고리즘

5.1 min과 max

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

int p = 7, q = 4;
int minimum = std::min(p, q); // 4
int maximum = std::max(p, q); // 7

auto min_from_list = std::min({9, 5, 12, 3, 7}); // 3
auto max_from_list = std::max({9, 5, 12, 3, 7}); // 12

5.2 min_element와 max_element

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

std::vector<int> values = {7, 3, 9, 1, 5};
auto min_pos = std::min_element(values.begin(), values.end()); // 1을 가리킴
auto max_pos = std::max_element(values.begin(), values.end()); // 9를 가리킴

5.3 minmax_element (C++11)

범위에서 최소와 최대 요소를 동시에 반환합니다.

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

6. 수치 알고리즘 (<numeric>에 있음)

6.1 accumulate

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

#include <numeric>

std::vector<int> values = {2, 3, 4, 5, 6};
int total = std::accumulate(values.begin(), values.end(), 0); // 합계, 초기값 0, 결과는 20
int product = std::accumulate(values.begin(), values.end(), 1, std::multiplies<int>()); // 곱, 초기값 1, 결과는 720

6.2 inner_product

두 범위의 내적을 계산합니다 (또는 사용자 정의 연산).

std::vector<int> v1 = {1, 2, 3};
std::vector<int> v2 = {4, 5, 6};
int dot_product = std::inner_product(v1.begin(), v1.end(), v2.begin(), 0); // 1*4 + 2*5 + 3*6 = 32

6.3 iota

연속적으로 증가하는 값으로 범위를 채웁니다.

std::vector<int> buffer(5);
std::iota(buffer.begin(), buffer.end(), 20); // 20, 21, 22, 23, 24로 채움

6.4 partial_sum

부분 합을 계산하고 결과를 대상 범위에 저장합니다.

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, 3, 6, 10, 15}가 됨

6.5 adjacent_difference

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

std::vector<int> source = {2, 4, 7, 11, 16};
std::vector<int> result(source.size());
std::adjacent_difference(source.begin(), source.end(), result.begin()); // result는 {2, 2, 3, 4, 5}가 됨

7. 기타

7.1 generate

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

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

7.2 generate_n

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

std::vector<int> buffer(5);
int start = 100;
std::generate_n(buffer.begin(), 3, [&start]() { 
    return start++; 
}); // 처음 세 요소는 100, 101, 102, 나머지 두 요소는 변경되지 않음

7.3 includes

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

std::vector<int> set_a = {1, 2, 3, 4, 5};
std::vector<int> set_b = {2, 4};
bool contains = std::includes(set_a.begin(), set_a.end(), set_b.begin(), set_b.end()); // true

7.4 set_union, set_intersection, set_difference, set_symmetric_difference

집합 연산 수행: 합집합, 교집합, 차집합, 대칭 차집합.

std::vector<int> set1 = {1, 2, 3, 4, 5};
std::vector<int> set2 = {3, 4, 5, 6, 7};
std::vector<int> outcome;

// 합집합
std::set_union(set1.begin(), set1.end(), set2.begin(), set2.end(), std::back_inserter(outcome));
// outcome은 {1, 2, 3, 4, 5, 6, 7}

// 교집합
outcome.clear();
std::set_intersection(set1.begin(), set1.end(), set2.begin(), set2.end(), std::back_inserter(outcome));
// outcome은 {3, 4, 5}

// 차집합 (set1 - set2)
outcome.clear();
std::set_difference(set1.begin(), set1.end(), set2.begin(), set2.end(), std::back_inserter(outcome));
// outcome은 {1, 2}

// 대칭 차집합 (set1 ∪ set2 - set1 ∩ set2)
outcome.clear();
std::set_symmetric_difference(set1.begin(), set1.end(), set2.begin(), set2.end(), std::back_inserter(outcome));
// outcome은 {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()), container.end()).

3. 哪些 알고리즘이 컨테이너가 정렬되어야 하는가? 이진 검색 系列 (binary_search, lower_bound, upper_bound), 집합 알고리즘 (set_intersection, set_union 등), merge 등은 효율적인 작업 (예: 이진 검색 O(log n))을 위해 정렬된 상태를 필요로 합니다.