1. 비수정 시퀀스 알고리즘

컨테이너의 데이터를 변경하지 않고 탐색이나 비교 작업을 수행하는 알고리즘입니다.

find, find_if, find_end

• find: 특정 값과 일치하는 첫 번째 요소를 찾습니다.
• find_if: 조건(서술자)을 만족하는 첫 번째 요소를 찾습니다.
• find_end: 대상 범위 내에서 특정 서브 시퀀스가 마지막으로 나타나는 위치를 반환합니다.

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

// 값 30 탐색
auto it = find(data.begin(), data.end(), 30);
if (it != data.end()) {
    cout << "찾은 값: " << *it << endl;
}

// 35보다 큰 첫 번째 요소 탐색
auto it_if = find_if(data.begin(), data.end(), [](int n) {
    return n > 35;
});
cout << "35 초과 첫 요소: " << *it_if << endl; // 40

// 서브 시퀀스 {20, 30}의 마지막 위치
vector<int> sub = {20, 30};
auto it_end = find_end(data.begin(), data.end(), sub.begin(), sub.end());
cout << "마지막 서브 시퀀스 인덱스: " << distance(data.begin(), it_end) << endl; // 5

count 및 count_if

vector<int> scores = {1, 2, 2, 3, 4, 2, 5};
// 2의 개수 확인
int num_twos = count(scores.begin(), scores.end(), 2); // 3
// 홀수 개수 확인
int odds = count_if(scores.begin(), scores.end(), [](int n) {
    return n % 2 != 0;
}); // 4

all_of, any_of, none_of

vector<int> values = {2, 4, 6, 8};
bool is_all_even = all_of(values.begin(), values.end(), [](int n) { return n % 2 == 0; }); // true
bool has_negative = any_of(values.begin(), values.end(), [](int n) { return n < 0; });   // false
bool none_zero = none_of(values.begin(), values.end(), [](int n) { return n == 0; });    // true

2. 시퀀스 수정 알고리즘

요소의 순서를 바꾸거나 값을 직접 수정하는 방식입니다.

transform

입력 범위의 각 요소에 연산을 적용하여 다른 범위로 결과를 저장합니다.

vector<int> base = {1, 2, 3, 4};
vector<int> results;

// 각 요소에 10을 더함
transform(base.begin(), base.end(), back_inserter(results), [](int n) {
    return n + 10;
}); // {11, 12, 13, 14}

remove, remove_if 및 erase (Erase-Remove 패턴)

remove 알고리즘은 요소를 실제로 삭제하지 않고 뒤로 밀어내기만 하므로, erase와 함께 사용해야 컨테이너 크기가 실제로 줄어듭니다.

vector<int> items = {1, 10, 2, 10, 3, 10};

// 값이 10인 요소 제거
items.erase(remove(items.begin(), items.end(), 10), items.end());
// items: {1, 2, 3}

// 짝수 요소 제거
items = {1, 2, 3, 4, 5, 6};
items.erase(remove_if(items.begin(), items.end(), [](int n) {
    return n % 2 == 0;
}), items.end());
// items: {1, 3, 5}

replace 및 replace_if

vector<int> nums = {1, 2, 3, 1, 2, 3};
// 1을 9로 변경
replace(nums.begin(), nums.end(), 1, 9); // {9, 2, 3, 9, 2, 3}
// 5보다 작은 수를 0으로 변경
replace_if(nums.begin(), nums.end(), [](int n) { return n < 5; }, 0); // {0, 0, 0, 0, 0, 0}

3. 정렬 및 탐색 알고리즘

sort, stable_sort

vector<int> v = {5, 2, 9, 1, 5, 6};
// 일반 정렬 (불안정)
sort(v.begin(), v.end()); 

// 안정 정렬 (동일한 값의 상대적 순서 유지)
vector<pair<int, string>> p = {{2, "a"}, {1, "b"}, {2, "c"}};
stable_sort(p.begin(), p.end(), [](auto a, auto b) {
    return a.first < b.first;
}); // {1, "b"}, {2, "a"}, {2, "c"} 순서 보장

이진 탐색 (binary_search, lower_bound, upper_bound)

해당 알고리즘들은 반드시 정렬된 상태에서 사용해야 합니다.

vector<int> sorted_v = {10, 20, 20, 30, 40};

bool found = binary_search(sorted_v.begin(), sorted_v.end(), 20); // true

// 20이 시작되는 위치 (첫 번째 20)
auto lb = lower_bound(sorted_v.begin(), sorted_v.end(), 20); 
// 20이 끝나는 다음 위치 (30의 위치)
auto ub = upper_bound(sorted_v.begin(), sorted_v.end(), 20);

4. 수치 알고리즘 (<numeric> 헤더)

accumulate 및 iota

#include <numeric>

vector<int> arr(5);
// 1부터 1씩 증가하며 채움
iota(arr.begin(), arr.end(), 1); // {1, 2, 3, 4, 5}

// 합계 계산
int total = accumulate(arr.begin(), arr.end(), 0); // 15
// 곱셈 연산 적용
int prod = accumulate(arr.begin(), arr.end(), 1, multiplies<int>()); // 120

5. 힙(Heap) 알고리즘

우선순위 큐를 직접 구현하거나 범위를 힙 구조로 유지할 때 유용합니다.

vector<int> heap_data = {3, 1, 4, 1, 5, 9};
make_heap(heap_data.begin(), heap_data.end()); // 최대 힙 생성

heap_data.push_back(7);
push_heap(heap_data.begin(), heap_data.end()); // 새 요소 추가 후 힙 유지

pop_heap(heap_data.begin(), heap_data.end()); // 최상단 노드를 맨 뒤로 보냄
int max_val = heap_data.back();
heap_data.pop_back(); // 실제 제거

주요 핵심 정리

1. 정렬의 차이: sort는 Introsort를 사용해 평균 O(N log N)을 보장하지만 불안정 정렬입니다. stable_sort는 병합 정렬 기반으로 순서를 유지하지만 추가 메모리를 사용할 수 있습니다.
2. Erase-Remove 관용구: remove는 논리적인 위치만 조정하므로 컨테이너의 erase 멤버 함수를 호출해야 물리적인 메모리 정리가 완료됩니다.
3. 정렬 필수 알고리즘: 이진 탐색(binary_search)이나 집합 연산(set_union 등)은 입력 데이터가 반드시 정렬되어 있어야 올바른 결과를 반환합니다.