비수정형 시퀀스 알고리즘

이러한 알고리즘은 컨테이너 내 요소를 변경하지 않고 조작합니다. 주로 탐색, 카운팅, 조건 검사에 사용됩니다.

요소 탐색: find 계열 함수

• std::find: 지정된 값과 일치하는 첫 번째 요소를 반환합니다.
• std::find_if: 조건을 만족하는 첫 번째 요소를 찾습니다.
• std::find_end: 특정 하위 시퀀스가 마지막으로 나타나는 위치를 반환합니다.

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

std::vector<int> data = {10, 20, 30, 40, 50};

// 값 30 찾기
auto pos = std::find(data.begin(), data.end(), 30);
if (pos != data.end()) {
    std::cout << "발견된 값: " << *pos << "\n";
}

// 35보다 큰 첫 번째 값 찾기
auto large = std::find_if(data.begin(), data.end(), [](int val) {
    return val > 35;
});
if (large != data.end()) {
    std::cout << "조건 충족 값: " << *large << "\n";
}

카운팅 및 반복 처리

• std::count: 특정 값의 등장 횟수를 측정합니다.
• std::count_if: 조건을 만족하는 요소 수를 센다.
• std::for_each: 각 요소에 대해 함수를 적용합니다.

std::vector<int> values = {2, 4, 6, 8, 10, 4};
int count_four = std::count(values.begin(), values.end(), 4); // 결과: 2

int even_count = std::count_if(values.begin(), values.end(), [](int x) {
    return x % 2 == 0;
});

// 모든 요소 출력
std::for_each(values.begin(), values.end(), [](int x) {
    std::cout << x << " ";
});
std::cout << "\n";

범위 비교 및 조건 평가

• std::equal: 두 범위의 요소가 동일한지 확인합니다.
• std::mismatch: 처음으로 불일치하는 위치를 반환합니다.
• std::all_of, std::any_of, none_of: 전체/일부/전혀 조건을 만족하는지 판단합니다.

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

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

std::vector<int> nums = {4, 6, 8, 10};
bool all_positive = std::all_of(nums.begin(), nums.end(), [](int n) { 
    return n > 0; 
});

수정형 시퀀스 알고리즘

이 그룹은 원본 데이터를 변경하거나 새 데이터를 생성합니다.

복사 및 변환

• std::copy: 요소를 다른 위치로 복사합니다. 대상 컨테이너는 사전에 크기를 확보해야 합니다.
• std::copy_if: 조건에 맞는 요소만 복사합니다. back_inserter를 사용하면 동적 추가가 가능합니다.
• std::transform: 각 요소를 변환하여 저장합니다. 단일 또는 이항 연산 모두 지원합니다.

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

std::vector<int> odds;
std::copy_if(src.begin(), src.end(), std::back_inserter(odds), [](int x) {
    return x % 2 == 1;
});

std::vector<int> squared;
std::transform(src.begin(), src.end(), std::back_inserter(squared), [](int x) {
    return x * x;
});

요소 제거 및 정리

• std::remove, remove_if: 조건에 맞는 요소를 논리적으로 끝으로 이동시킵니다. 실제 삭제는 erase와 함께 사용해야 합니다.
• std::unique: 인접한 중복 요소를 제거합니다. 전체 중복 제거 전에 정렬이 필요할 수 있습니다.

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

seq = {1, 3, 2, 4, 2, 5};
seq.erase(std::remove(seq.begin(), seq.end(), 2), seq.end()); // 2 제거

순서 조작

• std::reverse: 요소 순서를 반전합니다.
• std::rotate: 특정 포인트를 기준으로 요소를 회전시킵니다.
• std::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::mt19937 gen(rd());
std::shuffle(order.begin(), order.end(), gen);

정렬 및 검색 알고리즘

효율적인 데이터 정렬과 검색을 위한 도구입니다.

정렬 함수

• std::sort: 일반적인 정렬. 평균 O(n log n). 안정성 보장 안 됨.
• std::stable_sort: 안정 정렬. 동일한 값의 상대적 순서 유지.
• std::partial_sort: 상위 k개 요소만 정렬합니다.
• std::nth_element: n번째 위치에 올 값을 결정하고 분할합니다.

std::vector<int> items = {9, 1, 5, 3, 7};
std::sort(items.begin(), items.end(), std::greater<int>{}); // 내림차순

std::vector<std::string> words = {"cat", "dog", "bird", "ant"};
std::stable_sort(words.begin(), words.end(), [](const auto& a, const auto& b) {
    return a.length() < b.length();
});

std::nth_element(items.begin(), items.begin() + 2, items.end());
// items[2]는 정렬 시 세 번째 위치에 오는 값

이진 검색

정렬된 컨테이너에서만 사용 가능합니다.

• std::binary_search: 존재 여부를 bool로 반환.
• std::lower_bound: 첫 번째로 같거나 큰 위치.
• std::upper_bound: 첫 번째로 큰 위치.

std::vector<int> sorted = {2, 4, 4, 6, 8};
bool found = std::binary_search(sorted.begin(), sorted.end(), 4);

auto low = std::lower_bound(sorted.begin(), sorted.end(), 4);  // 첫 번째 4
auto high = std::upper_bound(sorted.begin(), sorted.end(), 4); // 첫 번째 6

병합 및 집합 연산

• std::merge: 두 정렬된 시퀀스를 하나로 통합합니다.
• std::set_union, intersection, difference: 수학적 집합 연산을 수행합니다.

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

수치 알고리즘 (<numeric>)

• std::accumulate: 누적 합 또는 사용자 정의 연산.
• std::inner_product: 두 시퀀스의 내적.
• std::iota: 연속된 값으로 채우기.
• std::partial_sum, adjacent_difference: 부분합 및 인접 차분 계산.

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

std::vector<int> sum_result(5);
std::partial_sum(series.begin(), series.end(), sum_result.begin()); // {1,3,6,10,15}

기타 유틸리티

• std::generate, generate_n: 함수를 통해 값 생성.
• std::includes: 정렬된 컨테이너 간 포함 관계 확인.

std::vector<int> vec(5);
int seed = 100;
std::generate(vec.begin(), vec.end(), [&seed]() { return seed++; });

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