1. 비변형 시퀀스 알고리즘 (Non-modifying Sequence Operations)

컨테이너의 원소를 직접 변경하지 않고 탐색하거나 검사하는 알고리즘들입니다.

1.1 탐색 (find 계열)

• find(first, last, value): 특정 값과 일치하는 첫 번째 원소의 반복자를 반환합니다.
• find_if(first, last, pred): 조건자(predicate)를 만족하는 첫 번째 원소를 찾습니다.
• find_end(first1, last1, first2, last2): 부분 시퀀스가 마지막으로 등장하는 위치를 탐색합니다.

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

int main() {
    std::vector<int> dataSet = {10, 30, 50, 70, 90};

    // 50인 원소 탐색
    auto iter = std::find(dataSet.begin(), dataSet.end(), 50);
    if (iter != dataSet.end()) {
        std::cout << "Target found: " << *iter << '\n';
    }

    // 60보다 큰 첫 번째 원소 탐색
    auto iter2 = std::find_if(dataSet.begin(), dataSet.end(), [](int val) {
        return val > 60;
    });
    if (iter2 != dataSet.end()) {
        std::cout << "First element > 60: " << *iter2 << '\n'; // 70 출력
    }

    // 부분 시퀀스 탐색
    std::vector<int> subSeq = {30, 50};
    auto iter3 = std::find_end(dataSet.begin(), dataSet.end(), subSeq.begin(), subSeq.end());
    if (iter3 != dataSet.end()) {
        std::cout << "Subsequence index: " << std::distance(dataSet.begin(), iter3) << '\n'; // 1 출력
    }
    return 0;
}

1.2 개수 세기 (count 계열)

• count(first, last, value): 특정 값과 일치하는 원소의 개수를 반환합니다.
• count_if(first, last, pred): 조건자를 만족하는 원소의 개수를 셉니다.

std::vector<int> items = {11, 22, 33, 22, 44, 22};
int targetCount = std::count(items.begin(), items.end(), 22); // 3

int oddCount = std::count_if(items.begin(), items.end(), [](int num) { 
    return num % 2 != 0; 
}); // 2 (11, 33)

1.3 순회 및 적용 (for_each)

지정된 범위의 모든 원소에 특정 함수나 람다식을 적용합니다.

std::vector<int> values = {2, 4, 6, 8, 10};
std::for_each(values.begin(), values.end(), [](int& v) { 
    v += 5; // 각 원소에 5를 더함
});
// values는 이제 {7, 9, 11, 13, 15}가 됨

1.4 비교 및 불일치 검사 (equal, mismatch)

• equal(first1, last1, first2): 두 범위의 원소가 모두 동일한지 확인합니다.
• mismatch(first1, last1, first2): 두 범위에서 처음으로 일치하지 않는 원소의 반복자 쌍을 반환합니다.

std::vector<int> seqA = {10, 20, 30};
std::vector<int> seqB = {10, 20, 99};
std::vector<int> seqC = {10, 20, 30, 40};

bool isSame = std::equal(seqA.begin(), seqA.end(), seqB.begin()); // false

auto diff = std::mismatch(seqA.begin(), seqA.end(), seqC.begin());
if (diff.first != seqA.end()) {
    std::cout << "Mismatch found.\n";
} else {
    std::cout << "seqA is a prefix of seqC.\n"; // 이 부분이 실행됨
}

1.5 조건 만족 여부 검사 (all_of, any_of, none_of)

범위 내의 원소들이 조건을 모두 만족하는지, 일부 만족하는지, 혹은 전혀 만족하지 않는지 검사합니다.

std::vector<int> scores = {85, 90, 78, 92};
bool allPass = std::all_of(scores.begin(), scores.end(), [](int s) { return s >= 60; }); // true
bool hasPerfect = std::any_of(scores.begin(), scores.end(), [](int s) { return s == 100; }); // false
bool noFail = std::none_of(scores.begin(), scores.end(), [](int s) { return s < 60; }); // true

2. 변형 시퀀스 알고리즘 (Modifying Sequence Operations)

컨테이너의 원소를 복사, 이동, 변환하거나 직접 수정하는 알고리즘입니다.

2.1 복사 (copy 계열)

• copy(first, last, result): 범위의 원소를 대상 위치로 복사합니다.
• copy_if(first, last, result, pred): 조건을 만족하는 원소만 복사합니다.

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

std::copy(source.begin(), source.end(), destination.begin());

std::vector<int> filtered;
std::copy_if(source.begin(), source.end(), std::back_inserter(filtered), [](int x) {
    return x % 2 != 0; // 홀수만 복사
}); // filtered: {1, 3, 5}

팁: std::back_inserter을 사용하면 대상 컨테이너의 크기를 미리 할당하지 않아도 push_back이 자동으로 호출됩니다.

2.2 변환 (transform)

원소에 특정 연산을 적용한 결과를 다른 범위에 저장합니다.

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

// 단일 범위 변환 (세제곱)
std::transform(base.begin(), base.end(), cubes.begin(), [](int n) {
    return n * n * n;
}); // cubes: {8, 27, 64}

// 두 범위를 활용한 변환 (벡터 덧셈)
std::vector<int> vecX = {10, 20, 30};
std::vector<int> vecY = {1, 2, 3};
std::vector<int> vecSum(3);
std::transform(vecX.begin(), vecX.end(), vecY.begin(), vecSum.begin(), [](int a, int b) {
    return a + b;
}); // vecSum: {11, 22, 33}

2.3 교체 (replace 계열)

• replace(first, last, old_val, new_val): 특정 값을 새로운 값으로 바꿉니다.
• replace_if(first, last, pred, new_val): 조건을 만족하는 원소를 교체합니다.
• replace_copy(first, last, result, old_val, new_val): 원본은 유지한 채 복사본에서 교체합니다.

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

std::replace(data.begin(), data.end(), 10, 99); // data: {5, 99, 15, 99, 25}

std::replace_if(data.begin(), data.end(), [](int v) { return v > 20; }, 0); // data: {5, 99, 15, 99, 0}

std::vector<int> copiedData;
std::replace_copy(data.begin(), data.end(), std::back_inserter(copiedData), 99, 100); 
// copiedData: {5, 100, 15, 100, 0} (원본 data는 변경되지 않음)

2.4 제거 (remove 계열)

remove와 remove_if는 원소를 물리적으로 삭제하지 않고, 살아남을 원소들을 앞쪽으로 덮어쓴 후 새로운 논리적 끝 반복자를 반환합니다. 실제 크기 축소를 위해서는 erase와 함께 사용해야 합니다(Erase-Remove Idiom).

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

// 논리적 제거 (값이 2인 원소를 뒤로 보냄)
auto newEnd = std::remove(nums.begin(), nums.end(), 2); 
// nums의 상태: {1, 3, 4, 2, 4} (뒤쪽 원소들은 쓰레기 값)

// 물리적 제거 (컨테이너 크기 조정)
nums.erase(newEnd, nums.end()); // nums: {1, 3, 4}

// 람다식을 활용한 짝수 제거
nums = {1, 2, 3, 4, 5};
nums.erase(
    std::remove_if(nums.begin(), nums.end(), [](int n) { return n % 2 == 0; }),
    nums.end()
); // nums: {1, 3, 5}

2.5 중복 제거, 뒤집기, 회전, 섞기

• unique: 인접한 중복 원소를 제거합니다. (사전 정렬 필요)
• reverse: 원소의 순서를 뒤집습니다.
• rotate: 지정한 중간 원소를 첫 번째 위치로 오도록 회전시킵니다.
• shuffle: 난수 엔진을 사용하여 원소를 무작위로 섞습니다.

#include <random>

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

std::reverse(arr.begin(), arr.end()); // arr: {4, 3, 2, 1}

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

std::random_device rd;
std::mt19937 gen(rd());
std::shuffle(arr.begin(), arr.end(), gen); // 무작위 섞기

3. 정렬 및 탐색 알고리즘 (Sorting and Searching)

3.1 정렬 (sort 계열)

• sort: 평균 O(N log N) 시간 복잡도의 비지속적(Unstable) 정렬 (Introsort).
• stable_sort: 동일한 값의 상대적 순서를 보장하는 지속적(Stable) 정렬.
• partial_sort: 상위 N개의 원소만 정렬하여 앞부분에 배치.

std::vector<int> list = {8, 3, 9, 1, 5, 2};
std::sort(list.begin(), list.end()); // 오름차순: {1, 2, 3, 5, 8, 9}
std::sort(list.begin(), list.end(), std::greater<int>()); // 내림차순

std::vector<std::pair<int, int>> pairs = {{2, 1}, {1, 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> partialList = {9, 4, 7, 2, 5, 8};
std::partial_sort(partialList.begin(), partialList.begin() + 3, partialList.end());
// 앞의 3개 원소는 가장 작은 {2, 4, 5}로 정렬됨

3.2 N번째 원소 (nth_element)

지정된 인덱스에 정렬되었을 때 해당 위치에 올 원소를 배치하고, 그 왼쪽은 더 작은 값, 오른쪽은 더 큰 값으로 분할합니다. (Quickselect 알고리즘 기반)

std::vector<int> data = {7, 2, 9, 4, 5, 1};
std::nth_element(data.begin(), data.begin() + 2, data.end());
// data[2]에는 정렬 시 3번째로 작은 값인 4가 위치하며, 왼쪽은 4보다 작고 오른쪽은 4보다 큼

3.3 이진 탐색 (Binary Search 계열)

반드시 정렬된 컨테이너에서만 사용해야 합니다.

• binary_search: 값의 존재 여부를 부울 값으로 반환.
• lower_bound: 특정 값 이상인 첫 번째 원소의 반복자.
• upper_bound: 특정 값 초과인 첫 번째 원소의 반복자.

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

bool has20 = std::binary_search(sortedData.begin(), sortedData.end(), 20); // true

auto lb = std::lower_bound(sortedData.begin(), sortedData.end(), 20); // 첫 번째 20을 가리킴 (인덱스 1)
auto ub = std::upper_bound(sortedData.begin(), sortedData.end(), 20); // 30을 가리킴 (인덱스 3)

3.4 병합 (merge)

두 개의 정렬된 범위를 하나의 정렬된 범위로 합칩니다.

std::vector<int> groupA = {1, 4, 7};
std::vector<int> groupB = {2, 5, 8};
std::vector<int> mergedGroup(groupA.size() + groupB.size());

std::merge(groupA.begin(), groupA.end(), groupB.begin(), groupB.end(), mergedGroup.begin());
// mergedGroup: {1, 2, 4, 5, 7, 8}

4. 힙 및 최솟값/최댓값 알고리즘

4.1 힙 연산 (Heap Operations)

<algorithm> 헤더에서 제공하는 힙 구성 및 조작 함수들입니다.

std::vector<int> heapVec = {3, 1, 4, 1, 5};
std::make_heap(heapVec.begin(), heapVec.end()); // 최대 힙 구성

heapVec.push_back(9);
std::push_heap(heapVec.begin(), heapVec.end()); // 새 원소를 힙에 추가

std::pop_heap(heapVec.begin(), heapVec.end()); // 최대 원소를 맨 뒤로 이동
int maxVal = heapVec.back();
heapVec.pop_back(); // 실제 제거

std::sort_heap(heapVec.begin(), heapVec.end()); // 힙을 오름차순으로 정렬

4.2 최솟값/최댓값 찾기

• min / max: 두 값 또는 초기화 리스트에서의 최소/최대값.
• min_element / max_element: 범위 내의 최소/최대 원소의 반복자.
• minmax_element: 최소 및 최대 원소의 반복자 쌍을 한 번에 반환.

std::vector<int> metrics = {42, 17, 89, 23, 55};
auto minIt = std::min_element(metrics.begin(), metrics.end()); // 17을 가리킴
auto maxIt = std::max_element(metrics.begin(), metrics.end()); // 89을 가리킴

auto bounds = std::minmax_element(metrics.begin(), metrics.end());
// bounds.first는 17, bounds.second는 89를 가리킴

5. 수치 연산 알고리즘 (Numeric Operations)

<numeric> 헤더에 정의된 수학 및 누적 연산 관련 알고리즘입니다.

5.1 누적 및 내적

• accumulate: 범위의 원소들을 누적 연산 (기본은 덧셈).
• inner_product: 두 범위의 내적을 계산.

#include <numeric>

std::vector<int> vals = {2, 3, 4};
int totalSum = std::accumulate(vals.begin(), vals.end(), 0); // 9
int totalProduct = std::accumulate(vals.begin(), vals.end(), 1, std::multiplies<int>()); // 24

std::vector<int> v1 = {1, 2, 3};
std::vector<int> v2 = {10, 20, 30};
int dotProduct = std::inner_product(v1.begin(), v1.end(), v2.begin(), 0); // 10+40+90 = 140

5.2 시퀀스 생성 및 차분

• iota: 연속된 증가하는 값으로 범위를 채웁니다.
• partial_sum: 부분 합을 계산하여 저장합니다.
• adjacent_difference: 인접한 원소 간의 차이를 계산합니다.

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

std::vector<int> raw = {1, 3, 6, 10};
std::vector<int> pSum(4);
std::partial_sum(raw.begin(), raw.end(), pSum.begin()); // {1, 4, 10, 20}

std::vector<int> diffs(4);
std::adjacent_difference(raw.begin(), raw.end(), diffs.begin()); // {1, 2, 3, 4}

6. 기타 유틸리티 및 집합 연산

6.1 원소 생성 (generate)

함수 객체나 람다식을 호출하여 반환된 값으로 범위를 채웁니다.

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

6.2 집합 연산 (Set Operations)

정렬된 두 범위에 대해 합집합, 교집합, 차집합 등을 수행합니다.

std::vector<int> setA = {1, 2, 3, 4, 5};
std::vector<int> setB = {3, 4, 5, 6, 7};
std::vector<int> resultSet;

// 교집합
std::set_intersection(setA.begin(), setA.end(), setB.begin(), setB.end(), std::back_inserter(resultSet));
// resultSet: {3, 4, 5}

resultSet.clear();
// 합집합
std::set_union(setA.begin(), setA.end(), setB.begin(), setB.end(), std::back_inserter(resultSet));
// resultSet: {1, 2, 3, 4, 5, 6, 7}

resultSet.clear();
// 차집합 (setA - setB)
std::set_difference(setA.begin(), setA.end(), setB.begin(), setB.end(), std::back_inserter(resultSet));
// resultSet: {1, 2}

7. 핵심 주의사항 및 심화 개념

• 정렬 알고리즘의 선택: std::sort는 내부적으로 Introsort를 사용하여 빠르지만 순서를 보장하지 않습니다. 반면 std::stable_sort는 Merge Sort 기반이라 동일한 키를 가진 원소의 기존 순서를 유지해야 할 때 필수적입니다.
• Erase-Remove 관용구: std::remove 계열 함수는 컨테이너의 메모리를 할당 해제하지 않습니다. 단지 불필요한 원소들을 뒤로 보내고 새로운 논리적 경계만 반환하므로, 반드시 erase 메서드와 결합하여 물리적 크기를 줄여야 합니다.
• 사전 정렬 요구사항: binary_search, lower_bound, set_intersection 등의 알고리즘은 입력 범위가 반드시 정렬되어 있어야 정상적으로 동작하며, 그렇지 않을 경우 정의되지 않은 행동(Undefined Behavior)이나 잘못된 결과를 초래합니다.