1. 비변형 시퀀스 알고리즘

원본 컨테이너의 요소를 변경하지 않는 알고리즘들입니다.

1.1 find 계열

• find(first, last, val): 첫 번째로 val과 일치하는 요소의 반복자 반환
• find_if(first, last, pred): 조건을 만족하는 첫 번째 요소 탐색
• find_end(first, last, s_first, s_last): 부분 시퀀스의 마지막 등장 위치

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 << "\n";  // 6 출력
}

// 조건 검색: 5보다 큰 첫 번째 값
auto pred = [](int v) { return v > 5; };
auto found = std::find_if(data.begin(), data.end(), pred);
std::cout << "5 초과 첫 값: " << *found << "\n";  // 6 출력

// 부분 시퀀스 탐색
std::vector<int> pattern = {4, 6};
auto last_pos = std::find_end(data.begin(), data.end(), 
                              pattern.begin(), pattern.end());
std::cout << "패턴 시작 인덱스: " << last_pos - data.begin() << "\n";  // 1

1.2 count 계열

std::vector<int> scores = {85, 92, 85, 78, 85};
auto occurrences = std::count(scores.begin(), scores.end(), 85);  // 3

auto high_scores = std::count_if(scores.begin(), scores.end(),
    [](int s) { return s >= 90; });  // 1

1.3 for_each

std::vector<int> values = {10, 20, 30};
std::for_each(values.begin(), values.end(), [](int& x) {
    x += 5;  // 각 요소에 5 더하기
});
// 결과: {15, 25, 35}

1.4 equal과 mismatch

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

bool identical = std::equal(seq1.begin(), seq1.end(), seq2.begin());
// false (3 != 4)

auto diff = std::mismatch(seq1.begin(), seq1.end(), seq2.begin());
if (diff.first != seq1.end()) {
    std::cout << "불일치: " << *diff.first 
              << " vs " << *diff.second << "\n";
}

1.5 all_of, any_of, none_of

std::vector<int> nums = {2, 4, 6, 8};

bool all_positive = std::all_of(nums.begin(), nums.end(), 
    [](int n) { return n > 0; });        // true

bool has_odd = std::any_of(nums.begin(), nums.end(),
    [](int n) { return n % 2 == 1; });   // false

bool no_negative = std::none_of(nums.begin(), nums.end(),
    [](int n) { return n < 0; });        // true

2. 변형 시퀀스 알고리즘

원본 데이터를 직접 수정하는 알고리즘입니다.

2.1 copy와 copy_if

std::vector<int> origin = {1, 2, 3, 4, 5};
std::vector<int> buffer(5);

std::copy(origin.begin(), origin.end(), buffer.begin());
// buffer: {1, 2, 3, 4, 5}

std::vector<int> filtered;
std::copy_if(origin.begin(), origin.end(), 
             std::back_inserter(filtered),
             [](int n) { return n % 2 == 1; });
// filtered: {1, 3, 5}

2.2 transform

std::vector<int> base = {1, 2, 3};
std::vector<int> squared(base.size());

// 단항 변환
std::transform(base.begin(), base.end(), squared.begin(),
    [](int n) { return n * n; });
// squared: {1, 4, 9}

// 이항 변환
std::vector<int> left = {10, 20, 30};
std::vector<int> right = {1, 2, 3};
std::vector<int> combined(left.size());

std::transform(left.begin(), left.end(), right.begin(), combined.begin(),
    [](int a, int b) { return a - b; });
// combined: {9, 18, 27}

2.3 replace 계열

std::vector<int> items = {1, 2, 3, 2, 5};

std::replace(items.begin(), items.end(), 2, 99);
// items: {1, 99, 3, 99, 5}

std::replace_if(items.begin(), items.end(),
    [](int n) { return n > 50; }, 0);
// items: {1, 0, 3, 0, 5}

std::vector<int> snapshot;
std::replace_copy(items.begin(), items.end(), std::back_inserter(snapshot),
    3, 300);
// snapshot: {1, 0, 300, 0, 5}, items는 불변

2.4 remove와 erase 관용구

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

// 논리적 제거 (실제 삭제는 아님)
auto logical_end = std::remove(collection.begin(), collection.end(), 2);
// collection: {1, 3, 4, 2, 2}

// 실제 삭제 (erase-remove 관용구)
collection.erase(logical_end, collection.end());
// collection: {1, 3, 4}

// 조건 제거 한 줄로
collection = {1, 2, 3, 4, 5, 6};
collection.erase(
    std::remove_if(collection.begin(), collection.end(),
        [](int n) { return n % 2 == 0; }),
    collection.end()
);
// collection: {1, 3, 5}

2.5 unique

std::vector<int> dupes = {1, 1, 2, 2, 2, 3, 3};
auto new_end = std::unique(dupes.begin(), dupes.end());
dupes.erase(new_end, dupes.end());
// dupes: {1, 2, 3}

2.6 reverse와 rotate

std::vector<int> order = {10, 20, 30, 40, 50};
std::reverse(order.begin(), order.end());
// order: {50, 40, 30, 20, 10}

std::rotate(order.begin(), order.begin() + 2, order.end());
// 30을 중심으로 회전, order: {30, 20, 10, 50, 40}

2.8 shuffle

#include <random>

std::vector<int> deck = {1, 2, 3, 4, 5};
std::random_device rd;
std::mt19937 engine(rd());
std::shuffle(deck.begin(), deck.end(), engine);

3. 정렬 및 관련 알고리즘

3.1 sort, stable_sort, partial_sort

std::vector<int> unsorted = {5, 2, 8, 1, 9};

std::sort(unsorted.begin(), unsorted.end());
// {1, 2, 5, 8, 9}

std::sort(unsorted.begin(), unsorted.end(), std::greater<int>());
// {9, 8, 5, 2, 1}

// 안정 정렬
std::vector<std::pair<int, char>> pairs = {{1, 'a'}, {2, 'x'}, {1, 'b'}};
std::stable_sort(pairs.begin(), pairs.end(),
    [](const auto& a, const auto& b) { return a.first < b.first; });
// {(1, 'a'), (1, 'b'), (2, 'x')}

// 부분 정렬: 가장 작은 3개만 앞으로
std::vector<int> partial = {9, 3, 7, 1, 5, 2, 8};
std::partial_sort(partial.begin(), partial.begin() + 3, partial.end());
// partial: {1, 2, 3, 9, 7, 5, 8} (앞 3개만 정렬됨)

3.2 nth_element

std::vector<int> median = {9, 3, 7, 1, 5, 2, 8};
std::nth_element(median.begin(), median.begin() + 3, median.end());
// median[3] == 5, 좌측은 ≤5, 우측은 ≥5

3.3 이진 탐색 계열

std::vector<int> sorted_arr = {1, 3, 3, 5, 7, 9};

bool exists = std::binary_search(sorted_arr.begin(), sorted_arr.end(), 3);
// true

auto lower = std::lower_bound(sorted_arr.begin(), sorted_arr.end(), 3);
// *lower == 3, 인덱스 1

auto upper = std::upper_bound(sorted_arr.begin(), sorted_arr.end(), 3);
// *upper == 5, 인덱스 3

3.4 merge

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

std::merge(arr_a.begin(), arr_a.end(), arr_b.begin(), arr_b.end(), merged.begin());
// merged: {1, 2, 3, 4, 5, 6}

4. 힙 알고리즘

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

std::make_heap(heap.begin(), heap.end());  // 최대 힙 구성
// heap: {5, 4, 3, 2, 1}

heap.push_back(6);
std::push_heap(heap.begin(), heap.end());  // 새 요소 힙에 삽입

std::pop_heap(heap.begin(), heap.end());   // 최대값을 끝으로 이동
int max_val = heap.back();  // 6
heap.pop_back();

std::sort_heap(heap.begin(), heap.end());  // 힙 → 오름차순 정렬

5. 최소/최대 알고리즘

int x = 7, y = 3;
int smaller = std::min(x, y);  // 3
int larger = std::max(x, y);   // 7

auto list_min = std::min({5, 2, 8, 1});  // 1

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

auto both = std::minmax_element(range.begin(), range.end());
// *both.first == 1, *both.second == 5

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

6.1 accumulate

std::vector<int> prices = {10, 20, 30, 40};
int total = std::accumulate(prices.begin(), prices.end(), 0);  // 100

int factorial = std::accumulate(prices.begin(), prices.end(), 1,
    std::multiplies<int>());

6.2 inner_product

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

6.3 iota

std::vector<int> sequence(5);
std::iota(sequence.begin(), sequence.end(), 100);
// sequence: {100, 101, 102, 103, 104}

6.4 partial_sum과 adjacent_difference

std::vector<int> src = {1, 2, 3, 4, 5};
std::vector<int> prefix(src.size());

std::partial_sum(src.begin(), src.end(), prefix.begin());
// prefix: {1, 3, 6, 10, 15}

std::vector<int> diff(src.size());
std::adjacent_difference(src.begin(), src.end(), diff.begin());
// diff: {1, 1, 1, 1, 1}

7. 기타 유용한 알고리즘

7.1 generate / generate_n

std::vector<int> generated(5);
int seed = 0;
std::generate(generated.begin(), generated.end(), [&seed]() {
    return seed++ * 10;  // 0, 10, 20, 30, 40
});

std::vector<int> partial_gen(5, 0);
int start = 100;
std::generate_n(partial_gen.begin(), 3, [&start]() {
    return start += 5;  // 앞 3개: 105, 110, 115
});

7.2 집합 연산

std::vector<int> set_a = {1, 2, 3, 4, 5};
std::vector<int> set_b = {3, 4, 5, 6, 7};
std::vector<int> out;

// 포함 관계
bool subset = std::includes(set_a.begin(), set_a.end(),
                            set_b.begin(), set_b.end());  // false

// 합집합
std::set_union(set_a.begin(), set_a.end(), set_b.begin(), set_b.end(),
               std::back_inserter(out));

// 교집합
out.clear();
std::set_intersection(set_a.begin(), set_a.end(), set_b.begin(), set_b.end(),
                      std::back_inserter(out));
// {3, 4, 5}

// 차집합 (A - B)
out.clear();
std::set_difference(set_a.begin(), set_a.end(), set_b.begin(), set_b.end(),
                    std::back_inserter(out));
// {1, 2}

// 대칭 차집합
out.clear();
std::set_symmetric_difference(set_a.begin(), set_a.end(),
                              set_b.begin(), set_b.end(),
                              std::back_inserter(out));
// {1, 2, 6, 7}

8. 핵심 개념 정리