비수정형 시퀀스 알고리즘

이들 알고리즘은 컨테이너의 요소를 변경하지 않고 탐색 또는 검사를 수행합니다.

요소 탐색: find 계열 함수

• find(시작, 끝, 값): 지정된 값과 일치하는 첫 번째 요소의 반복자를 반환. 못 찾으면 end().
• find_if(시작, 끝, 조건): 조건을 만족하는 첫 번째 요소를 찾음.
• find_end(시작1, 끝1, 시작2, 끝2): 두 번째 범위의 시퀀스가 첫 번째 범위에서 마지막으로 나타나는 위치를 찾음.

#include <vector>
#include <iostream>
#include <algorithm>

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
}

// 7보다 큰 첫 번째 값 찾기
auto large = std::find_if(data.begin(), data.end(), [](int x) {
    return x > 7;
});
std::cout << "첫 번째 큰 수: " << *large << "\n"; // 출력: 8

// 부분 시퀀스 찾기
std::vector<int> pattern = {4, 6};
auto match = std::find_end(data.begin(), data.end(), pattern.begin(), pattern.end());
if (match != data.end()) {
    std::cout << "패턴 시작 인덱스: " << (match - data.begin()) << "\n"; // 출력: 1
}

조건 기반 카운팅

• count(시작, 끝, 값): 특정 값과 동일한 요소의 개수를 반환.
• count_if(시작, 끝, 조건): 조건을 충족하는 요소 수를 셈.

std::vector<int> values = {1, 2, 2, 3, 2, 4};
int count_two = std::count(values.begin(), values.end(), 2); // 결과: 3
int even_count = std::count_if(values.begin(), values.end(), [](int n) {
    return n % 2 == 0;
}); // 짝수 개수: 4

범위 기반 함수 적용

• for_each(시작, 끝, 함수): 각 요소에 대해 함수를 실행. 원본 수정 가능.

std::vector<int> nums = {1, 2, 3};
std::for_each(nums.begin(), nums.end(), [](int& val) {
    val += 5;
});
// nums: {6, 7, 8}

두 범위 비교

• equal(시작1, 끝1, 시작2): 두 시퀀스가 동일한지 확인.
• mismatch(시작1, 끝1, 시작2): 처음 불일치하는 요소 쌍을 반환.

std::vector<int> a = {1, 2, 3}, b = {1, 2, 4};
bool same = std::equal(a.begin(), a.end(), b.begin()); // false

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

조건 집합 평가

• all_of: 모든 요소가 조건을 만족하는지.
• any_of: 하나라도 조건을 만족하는지.
• none_of: 어떤 요소도 조건을 만족하지 않는지.

std::vector<int> seq = {2, 4, 6, 8};
bool all_even = std::all_of(seq.begin(), seq.end(), [](int x) { return x % 2 == 0; }); // true
bool has_odd = std::any_of(seq.begin(), seq.end(), [](int x) { return x % 2 == 1; }); // false
bool no_negative = std::none_of(seq.begin(), seq.end(), [](int x) { return x < 0; }); // true

수정형 시퀀스 알고리즘

이 알고리즘들은 컨테이너 내부의 데이터를 직접 변경하거나 새로운 구조를 생성합니다.

데이터 복사

• copy(시작, 끝, 대상): 요소를 다른 위치로 복사.
• copy_if(시작, 끝, 대상, 조건): 조건에 맞는 요소만 복사.

std::vector<int> src = {10, 20, 30, 40};
std::vector<int> dst(src.size());
std::copy(src.begin(), src.end(), dst.begin());

std::vector<int> filtered;
std::copy_if(src.begin(), src.end(), std::back_inserter(filtered), [](int x) {
    return x > 25;
}); // filtered: {30, 40}

변환 처리: transform

• 단항 연산: 각 요소를 변환하여 저장.
• 이항 연산: 두 시퀀스의 요소를 조합.

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

// 제곱 계산
std::transform(input.begin(), input.end(), output.begin(), [](int x) {
    return x * x;
});

// 두 벡터 요소 더하기
std::vector<int> left = {1, 2, 3}, right = {4, 5, 6}, result(3);
std::transform(left.begin(), left.end(), right.begin(), result.begin(), std::plus<int>());

값 교체 및 제거

• replace: 특정 값을 새 값으로 변경.
• remove + erase: 요소를 논리적으로 이동 후 실제 삭제.
• unique: 인접 중복 제거.

std::vector<int> items = {5, 1, 1, 2, 2, 3};
std::replace(items.begin(), items.end(), 1, 9); // 1 → 9

// 짝수 제거
items.erase(std::remove_if(items.begin(), items.end(), [](int x) {
    return x % 2 == 0;
}), items.end());

// 연속 중복 제거
std::vector<int> dupes = {1, 1, 2, 2, 2, 3};
auto last = std::unique(dupes.begin(), dupes.end());
dupes.erase(last, dupes.end()); // {1, 2, 3}

순서 재배치

• reverse: 순서를 뒤집음.
• rotate: 특정 지점을 중심으로 회전.
• shuffle: 무작위로 섞음.

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

std::rotate(order.begin(), order.begin() + 2, order.end()); // {3,4,5,1,2}

std::random_device rd;
std::shuffle(order.begin(), order.end(), std::mt19937(rd()));

정렬 및 관련 알고리즘

정렬 함수

• sort: 고속 정렬 (불안정).
• stable_sort: 안정 정렬 (순서 유지).
• partial_sort: 일부만 정렬.
• nth_element: N번째 위치 고정.

std::vector<int> arr = {9, 3, 7, 1, 5};
std::sort(arr.begin(), arr.end()); // 오름차순

std::vector<std::pair<int, char>> pairs = {{2,'a'}, {1,'b'}, {2,'c'}};
std::stable_sort(pairs.begin(), pairs.end(), [](const auto& a, const auto& b) {
    return a.first < b.first;
}); // first 기준 정렬, 같은 값은 원래 순서 유지

std::nth_element(arr.begin(), arr.begin() + 2, arr.end()); // 3번째 가장 작은 값 결정

이진 탐색 계열

• binary_search: 존재 여부 확인.
• lower_bound: 값 이상인 첫 위치.
• upper_bound: 값 초과인 첫 위치.

std::vector<int> sorted = {1, 3, 5, 5, 7};
bool found = std::binary_search(sorted.begin(), sorted.end(), 5);

auto low = std::lower_bound(sorted.begin(), sorted.end(), 5);
auto high = std::upper_bound(sorted.begin(), sorted.end(), 5);

병합 및 집합 연산

• merge: 두 정렬된 시퀀스 결합.
• set_union, set_intersection 등: 집합 연산 수행.

std::vector<int> A = {1, 2, 3}, B = {3, 4, 5}, merged;
std::merge(A.begin(), A.end(), B.begin(), B.end(), std::back_inserter(merged));

std::vector<int> intersect;
std::set_intersection(A.begin(), A.end(), B.begin(), B.end(), std::back_inserter(intersect));

힙 알고리즘

최대 힙 또는 최소 힙 형태로 데이터 관리.

std::vector<int> heap_data = {3, 1, 4, 1, 5};
std::make_heap(heap_data.begin(), heap_data.end());

heap_data.push_back(6);
std::push_heap(heap_data.begin(), heap_data.end());

std::pop_heap(heap_data.begin(), heap_data.end());
heap_data.pop_back();

std::sort_heap(heap_data.begin(), heap_data.end());

수치 계산 알고리즘 (<numeric>)

• accumulate: 누적 합 또는 사용자 정의 연산.
• inner_product: 내적 계산.
• iota: 연속 값으로 채우기.
• partial_sum: 부분 누적합.
• adjacent_difference: 인접 차이 계산.

#include <numeric>

std::vector<int> series = {1, 2, 3, 4};
int total = std::accumulate(series.begin(), series.end(), 0);
int product = std::accumulate(series.begin(), series.end(), 1, std::multiplies<int>());

std::vector<int> input(5), output(5);
std::iota(input.begin(), input.end(), 1); // 1~5
std::partial_sum(input.begin(), input.end(), output.begin()); // {1,3,6,10,15}

기타 유틸리티 알고리즘

• generate: 함수 호출 결과로 범위 채우기.
• includes: 정렬된 시퀀스 포함 여부 확인.

int counter = 0;
std::generate(input.begin(), input.end(), [&]() { return ++counter; });

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