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

이 알고리즘들은 컨테이너의 요소를 변경하지 않고 조작합니다.

1.1 find 및 find_if

• find(begin, end, value): value와 첫 번째로 일치하는 요소를 찾아 반복자를 반환합니다 (찾지 못하면 end 반환).
• find_if(begin, end, predicate): 조건자를 만족하는 첫 번째 요소를 찾습니다.
• find_end(begin, end, sub_begin, sub_end): 서브시퀀스가 마지막으로出現하는 위치를 찾습니다.

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

// 값 30 찾기
auto result = std::find(data.begin(), data.end(), 30);
if (result != data.end()) {
    std::cout << "발견: " << *result << std::endl;  // 출력: 30
}

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

// 서브시퀀스 찾기
std::vector<int> pattern = {20, 30};
auto result3 = std::find_end(data.begin(), data.end(), pattern.begin(), pattern.end());
if (result3 != data.end()) {
    std::cout << "서브시퀀스 시작 위치: " << result3 - data.begin() << std::endl;  // 출력: 1
}

1.2 count 및 count_if

• count(begin, end, value): value와 일치하는 요소 개수를 셉니다.
• count_if(begin, end, predicate): 조건자를 만족하는 요소 개수를 셉니다.

std::vector<int> numbers = {5, 10, 15, 10, 20, 10};
int count_ten = std::count(numbers.begin(), numbers.end(), 10); // 10의 개수: 3
int divisible_by_five = std::count_if(numbers.begin(), numbers.end(), [](int n) { 
    return n % 5 == 0; 
}); // 5의 배수 개수: 6

1.3 for_each

범위의 각 요소에 함수를 적용합니다.

std::vector<int> items = {1, 2, 3, 4, 5};
std::for_each(items.begin(), items.end(), [](int& val) { 
    val += 10; // 각 요소에 10 더하기
});
// items는 {11, 12, 13, 14, 15}가 됨

1.4 equal 및 mismatch

• equal(b1, e1, b2): 두 범위가 동일한지 비교합니다.
• mismatch(b1, e1, b2): 첫 번째로 일치하지 않는 요소의 반복자 쌍을 반환합니다.

std::vector<int> first = {100, 200, 300};
std::vector<int> second = {100, 200, 400};
std::vector<int> third = {100, 200, 300};

// first와 second 비교
bool is_same = std::equal(first.begin(), first.end(), second.begin());
std::cout << "first == second? " << std::boolalpha << is_same << std::endl;  // 출력: false

// first와 third의 첫 불일치 찾기
auto diff = std::mismatch(first.begin(), first.end(), third.begin());
if (diff.first != first.end()) {
    std::cout << "불일치: " << *diff.first << " vs " << *diff.second << std::endl;
}

1.5 all_of, any_of, none_of

범위의 요소가 조건을 충족하는지 확인합니다.

std::vector<int> values = {4, 8, 12, 16};
bool all_positive = std::all_of(values.begin(), values.end(), [](int n) { 
    return n > 0; 
}); // true
bool any_negative = std::any_of(values.begin(), values.end(), [](int n) { 
    return n < 0; 
}); // false
bool none_zero = std::none_of(values.begin(), values.end(), [](int n) { 
    return n == 0; 
}); // true

2. 수정 시퀀스 알고리즘

이 알고리즘들은 컨테이너의 요소를 직접 수정합니다.

2.1 copy 및 copy_if

• copy(begin, end, dest): 요소를 대상 위치로 복사합니다.
• copy_if(begin, end, dest, predicate): 조건자를 만족하는 요소만 복사합니다.

std::vector<int> source = {2, 4, 6, 8, 10};
std::vector<int> destination(5);

// 전체 복사
std::copy(source.begin(), source.end(), destination.begin());  // destination: [2,4,6,8,10]

// 짝수만 복사
std::vector<int> even_numbers;
std::copy_if(source.begin(), source.end(), std::back_inserter(even_numbers), [](int n) {
    return n % 2 == 0;
});  // even_numbers: [2,4,6,8,10]

2.2 transform

각 요소에 함수를 적용하고 결과를 다른 범위에 저장합니다.

std::vector<int> input = {5, 6, 7};
std::vector<int> cube_result(3);

// 큐브 계산 (단일 인자 변환)
std::transform(input.begin(), input.end(), cube_result.begin(), [](int n) {
    return n * n * n;
});  // cube_result: [125, 216, 343]

// 두 컨테이너 연산 (이중 인자 변환)
std::vector<int> left = {1, 2, 3};
std::vector<int> right = {10, 20, 30};
std::vector<int> combined(3);
std::transform(left.begin(), left.end(), right.begin(), combined.begin(), [](int x, int y) {
    return x * y;
});  // combined: [10, 40, 90]

2.3 replace, replace_if, replace_copy

• replace(begin, end, old_val, new_val): 모든 old_val을 new_val로 교체합니다.
• replace_if(begin, end, predicate, new_val): 조건자를 만족하는 요소를 교체합니다.
• replace_copy(begin, end, dest, old_val, new_val): 복사 시 교체합니다 (원본 불변).

std::vector<int> array = {5, 10, 15, 10, 20};

// 모든 10을 100으로 교체
std::replace(array.begin(), array.end(), 10, 100);  // array: [5,100,15,100,20]

// 50보다 큰 요소를 0으로 교체
std::replace_if(array.begin(), array.end(), [](int n) {
    return n > 50;
}, 0);  // array: [5,0,15,0,20]

// 복사 시 15를 150으로 교체 (원본 불변)
std::vector<int> copied;
std::replace_copy(array.begin(), array.end(), std::back_inserter(copied), 15, 150);  
// copied: [5,0,150,0,20]

2.4 remove, remove_if, erase

• remove(begin, end, value): 값을 "이동"시키고 논리적 끝 반복자를 반환합니다 (실제 삭제 아님).
• remove_if(begin, end, predicate): 조건자를 만족하는 요소를末尾로 이동시킵니다.

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

// 논리적 제거 (末尾로 이동)
auto new_end = std::remove(collection.begin(), collection.end(), 2);  
// collection: [1,3,4,2,2]

// 물리적 제거
collection.erase(new_end, collection.end());  // collection: [1,3,4]

// lambda와 결합하여 홀수 제거
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: [2,4,6]

2.5 unique

연속된 중복 요소를 제거하고 새로운 논리적 끝을 반환합니다.

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

2.6 reverse

요소 순서를 반전시킵니다.

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

2.7 rotate

중간 요소를 새로운 첫 번째 요소로 회전시킵니다.

std::vector<int> seq = {1, 2, 3, 4, 5, 6};
std::rotate(seq.begin(), seq.begin() + 3, seq.end()); 
// 4를 시작점으로 회전, seq: {4, 5, 6, 1, 2, 3}

2.8 shuffle

요소를 무작위로 재배열합니다 (C++11 이상).

#include <random>
#include <algorithm>

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

3. 정렬及相关 알고리즘

3.1 sort, stable_sort, partial_sort

• sort(begin, end): 퀵 정렬 기반 (비안정, O(n log n)).
• stable_sort(begin, end): 병합 정렬 기반 (안정 정렬).
• partial_sort(begin, mid, end): 부분 정렬로 최소 요소들을前面에 배치합니다.

std::vector<int> unsorted = {50, 30, 10, 40, 20};
std::sort(unsorted.begin(), unsorted.end()); // 오름차순: {10, 20, 30, 40, 50}
std::sort(unsorted.begin(), unsorted.end(), std::greater<int>()); // 내림차순
std::sort(unsorted.begin(), unsorted.end(), [](int a, int b) { 
    return a > b; 
}); // 사용자 정의 비교

std::vector> pairs = {{3, 1}, {1, 3}, {3, 2}, {1, 2}};
std::stable_sort(pairs.begin(), pairs.end(), [](const auto& p1, const auto& p2) {
    return p1.first < p2.first; // 첫 번째 값으로 정렬, 동일 시 상대 순서 유지
});

std::vector<int> partial = {60, 10, 50, 30, 20, 40};
std::partial_sort(partial.begin(), partial.begin() + 3, partial.end());
// 앞 3개 요소: 10, 20, 30 (정렬됨), 나머지는 미정렬 상태

3.2 nth_element

지정된 위치의 요소를 정렬 후 위치에 배치합니다.

std::vector<int> data = {5, 3, 8, 1, 9, 2, 7, 4};
std::nth_element(data.begin(), data.begin() + 4, data.end());
// 인덱스 4의 요소는 정렬 시 해당 위치(5번째 작음)
// 왼쪽 요소들 ≤ 해당 요소 ≤ 오른쪽 요소들

3.3 binary_search, lower_bound, upper_bound

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

• binary_search(begin, end, value): 값 존재 여부 반환 (bool).
• lower_bound(begin, end, value): value 이상 첫 번째 반복자.
• upper_bound(begin, end, value): value 초과 첫 번째 반복자.

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

// 5 존재 여부
bool has_five = std::binary_search(sorted.begin(), sorted.end(), 5);  // true

// 첫 ≥ 5
auto lower = std::lower_bound(sorted.begin(), sorted.end(), 5);
std::cout << "lower_bound 위치: " << lower - sorted.begin() << std::endl;  // 출력: 2

// 첫 > 5
auto upper = std::upper_bound(sorted.begin(), sorted.end(), 5);
std::cout << "upper_bound 위치: " << upper - sorted.begin() << std::endl;  // 출력: 4

3.4 merge

두 개의 정렬된 범위를 합병합니다.

std::vector<int> left = {1, 3, 5, 7};
std::vector<int> right = {2, 4, 6, 8};
std::vector<int> result(left.size() + right.size());

std::merge(left.begin(), left.end(), right.begin(), right.end(), result.begin());  
// result: [1,2,3,4,5,6,7,8]

4. 힙 알고리즘

STL은 힙으로 조작하는 알고리즘들을 제공합니다: make_heap, push_heap, pop_heap, sort_heap.

std::vector<int> heap_data = {9, 5, 8, 3, 7};
std::make_heap(heap_data.begin(), heap_data.end()); // 최대 힙: {9,7,8,3,5}

heap_data.push_back(12);
std::push_heap(heap_data.begin(), heap_data.end()); // 힙에 추가: {12,7,9,3,5,8}

std::pop_heap(heap_data.begin(), heap_data.end()); // 최대값末尾로 이동: {9,7,8,3,5,12}
int max_value = heap_data.back(); // 12 획득
heap_data.pop_back(); // 최대값 제거

std::sort_heap(heap_data.begin(), heap_data.end()); // 힙을 오름차순 정렬: {3,5,7,8,9}

5. 최소/최대 알고리즘

5.1 min 및 max

int x = 100, y = 200;
int minimum = std::min(x, y); // 100
int maximum = std::max(x, y); // 200

auto min_from_list = std::min({7, 3, 9, 1, 5}); // 1
auto max_from_list = std::max({7, 3, 9, 1, 5}); // 9

5.2 min_element 및 max_element

std::vector<int> values = {8, 3, 10, 2, 15};
auto min_pos = std::min_element(values.begin(), values.end()); // 2 가리킴
auto max_pos = std::max_element(values.begin(), values.end()); // 15 가리킴

5.3 minmax_element (C++11)

최소와 최대를 동시에 반환합니다.

std::vector<int> nums = {8, 3, 10, 2, 15};
auto range = std::minmax_element(nums.begin(), nums.end());
// range.first는 최소값(2), range.second는 최대값(15)을 가리킴

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

6.1 accumulate

#include <numeric>

std::vector<int> arr = {2, 4, 6, 8, 10};
int total = std::accumulate(arr.begin(), arr.end(), 0); // 합계: 30
int product = std::accumulate(arr.begin(), arr.end(), 1, std::multiplies<int>()); // 곱: 3840

6.2 inner_product

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

6.3 iota

연속적인 증가 값으로 범위를 채웁니다.

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

6.4 partial_sum

누적 합을 계산합니다.

std::vector<int> source = {1, 2, 3, 4, 5};
std::vector<int> cumulative(source.size());
std::partial_sum(source.begin(), source.end(), cumulative.begin());  
// cumulative: {1, 3, 6, 10, 15}

6.5 adjacent_difference

인접 요소 간 차이를 계산합니다.

std::vector<int> original = {10, 15, 20, 25, 30};
std::vector<int> diff(original.size());
std::adjacent_difference(original.begin(), original.end(), diff.begin());  
// diff: {10, 5, 5, 5, 5}

7. 기타 알고리즘

7.1 generate

생성 함수로 범위를 채웁니다.

std::vector<int> generated(5);
int counter = 100;
std::generate(generated.begin(), generated.end(), [&counter]() { 
    return counter++; 
}); // 100, 101, 102, 103, 104

7.2 generate_n

시작부터 n개 요소를 생성 함수로 채웁니다.

std::vector<int> partial(5);
int start = 50;
std::generate_n(partial.begin(), 3, [&start]() { 
    return start++; 
}); // 앞 3개: 50, 51, 52

7.3 includes

정렬된 범위가 다른 정렬된 범위의 모든 요소를 포함하는지 확인합니다.

std::vector<int> superset = {1, 2, 3, 4, 5, 6};
std::vector<int> subset = {2, 4, 6};
bool contains_all = std::includes(superset.begin(), superset.end(), 
                                   subset.begin(), subset.end()); // true

7.4 집합 연산

합집합, 교집합, 차집합, 대칭 차집합을 수행합니다.

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

// 합집합
std::set_union(set_a.begin(), set_a.end(), set_b.begin(), set_b.end(), 
               std::back_inserter(result_set));
// result_set: {1, 2, 3, 4, 5, 6, 7}

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

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

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

8. 자주 묻는 질문

Q1: sort와 stable_sort의 차이점은?

• sort: 인트로소트 알고리즘 사용, 비안정 (동일 요소 순서 변경 가능), 평균 O(n log n).
• stable_sort: 병합 정렬 사용, 안정 (동일 요소 순서 불변), O(n log n), 약간의 추가 메모리 필요.

Q2: remove 알고리즘에为何 erase가 필요한가?

remove는 "덮어쓰기" 방식으로 작동합니다. 삭제할 요소를 유지할 요소로 덮어쓰고, 논리적 끝 반복자만 반환합니다. 실제 컨테이너 크기는 변경되지 않습니다. erase가 실제로 요소를 삭제하고 크기를 줄입니다. 따라서 container.erase(remove(...), container.end()) 패턴이 필요합니다.

Q3: 정렬된 컨테이너가 필요한 알고리즘은?

이진 탐색 계열 (binary_search, lower_bound, upper_bound), 집합 연산 (set_union, set_intersection 등), merge 등이 있습니다. 이러한 알고리즘들은 정렬된 특성을 활용하여 효율적인 O(log n) 작업을 보장합니다.