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 = {1, 3, 5, 7, 9};

// 값이 5인 요소 찾기
auto pos = std::find(data.begin(), data.end(), 5);
if (pos != data.end()) {
    std::cout << "발견: " << *pos << std::endl;  // 출력: 5
}

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

// 부분 시퀀스 찾기
std::vector<int> pattern = {3, 5};
auto pos3 = std::find_end(data.begin(), data.end(), pattern.begin(), pattern.end());
if (pos3 != data.end()) {
    std::cout << "부분 시퀀스 시작 인덱스: " << pos3 - data.begin() << std::endl;  // 출력: 1
}

1.2 count와 count_if

• count(begin, end, value): value와 동일한 요소 개수 세기
• count_if(begin, end, predicate): 조건자를 만족하는 요소 개수 세기

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

1.3 for_each

범위의 각 요소에 함수 적용

std::vector<int> values = {1, 2, 3, 4, 5};
std::for_each(values.begin(), values.end(), [](int& x) { 
    x *= 2; // 각 요소를 2배로
});
// 이제 values는 {2, 4, 6, 8, 10}

1.4 equal과 mismatch

• equal(b1, e1, b2): 두 범위 [b1,e1)와 [b2, b2+(e1-b1))가 동일한지 비교
• mismatch(b1, e1, b2): 두 범위에서 첫 번째로 서로 다른 요소의 반복자 쌍 반환

std::vector<int> arr1 = {1, 2, 3};
std::vector<int> arr2 = {1, 2, 4};
std::vector<int> arr3 = {1, 2, 3, 4};

// arr1과 arr2의 첫 3개 요소 비교
bool is_same = std::equal(arr1.begin(), arr1.end(), arr2.begin());
std::cout << "arr1 == arr2? " << std::boolalpha << is_same << std::endl;  // 출력: false

// arr1과 arr3의 첫 불일치 요소 찾기
auto result = std::mismatch(arr1.begin(), arr1.end(), arr3.begin());
if (result.first != arr1.end()) {
    std::cout << "불일치: " << *result.first << " vs " << *result.second << std::endl;
}

1.5 all_of, any_of, none_of

범위 내 요소가 모두, 일부, 또는 하나도 조건을 만족하지 않는지 확인

std::vector<int> items = {2, 4, 6, 8};
bool all_even = std::all_of(items.begin(), items.end(), [](int n) { 
    return n % 2 == 0; 
}); // true
bool any_odd = std::any_of(items.begin(), items.end(), [](int n) { 
    return n % 2 != 0; 
}); // false
bool none_negative = std::none_of(items.begin(), items.end(), [](int n) { 
    return n < 0; 
}); // true

2、수정 시퀀스 알고리즘

이 알고리즘들은 연산 대상 컨테이너의 요소를 수정합니다.

2.1 copy와 copy_if

• copy(begin, end, dest): [begin, end)의 요소를 dest 위치부터 복사
• copy_if(begin, end, dest, predicate): 조건자를 만족하는 요소만 dest에 복사

std::vector<int> source = {1, 2, 3, 4, 5};
std::vector<int> destination(5);  // 사전에 충분한 공간 확보

// 모든 요소 복사
std::copy(source.begin(), source.end(), destination.begin());  // destination: [1,2,3,4,5]

// 짝수 요소만 새 컨테이너에 복사
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]

주의: back_inserter(dest)는 자동으로 push_back을 호출하므로 사전 공간 할당이 필요 없습니다.

2.2 transform

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

std::vector<int> numbers = {1, 2, 3};
std::vector<int> squares(3);

// 제곱 계산 (단일 인자 변환)
std::transform(numbers.begin(), numbers.end(), squares.begin(), [](int n) {
    return n * n;
});  // squares: [1,4,9]

// 두 컨테이너 요소 더하기 (이중 인자 변환)
std::vector<int> left = {1, 2, 3};
std::vector<int> right = {4, 5, 6};
std::vector<int> result(3);
std::transform(left.begin(), left.end(), right.begin(), result.begin(), [](int x, int y) {
    return x + y;
});  // result: [5,7,9]

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> data = {1, 2, 3, 2, 5};

// 모든 2를 20으로 대체
std::replace(data.begin(), data.end(), 2, 20);  // data: [1,20,3,20,5]

// 10보다 큰 요소를 0으로 대체
std::replace_if(data.begin(), data.end(), [](int n) {
    return n > 10;
}, 0);  // data: [1,0,3,0,5]

// 복사 시 3을 300으로 대체 (원본 불변)
std::vector<int> output;
std::replace_copy(data.begin(), data.end(), std::back_inserter(output), 3, 300);  // output: [1,0,300,0,5]

2.4 remove, remove_if와 erase

• remove(begin, end, value): value와 같은 요소를 컨테이너 끝으로 "이동", 새로운 논리적 끝 반복자 반환 (실제 요소 삭제 아님, erase와 함께 사용 필요)
• remove_if(begin, end, predicate): 조건자를 만족하는 요소를 끝으로 이동

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

// 논리적 삭제: 모든 2를 끝으로 이동
auto new_end = std::remove(items.begin(), items.end(), 2);  // items: [1,3,4,2,2]

// 물리적 삭제 (실제 요소 제거)
items.erase(new_end, items.end());  // items: [1,3,4]

// lambda와 결합하여 짝수 삭제
items = {1, 2, 3, 4, 5};
items.erase(std::remove_if(items.begin(), items.end(), [](int n) {
    return n % 2 == 0;
}), items.end());  // items: [1,3,5]

2.5 unique

연속된 중복 요소를 제거하고 새로운 논리적 끝 반복자 반환. 보통 erase와 결합 사용.

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

2.6 reverse

범위 내 요소 순서 뒤집기

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

2.7 rotate

범위 내 요소를 회전시켜 가운데 요소가新的 첫 번째 요소가 되도록 함

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

2.8 shuffle

범위 내 요소를 무작위로 재배열 (C++11 이상 필요)

#include <random>
#include <algorithm>

std::vector<int> sequence = {1, 2, 3, 4, 5};
std::random_device rng;
std::mt19937 gen(rng());
std::shuffle(sequence.begin(), sequence.end(), gen); // sequence 무작위 섞임

3、정렬 및 관련 알고리즘

3.1 sort, stable_sort와 partial_sort

• sort(begin, end): 퀵 정렬 수행 (비안정, 평균 시간 복잡도 O(n log n))
• stable_sort(begin, end): 안정 정렬 (동일 요소 상대 위치 불변)
• partial_sort(begin, mid, end): 부분 정렬로 [begin, mid)에 전체 범위中最小 요소 정렬

std::vector<int> numbers = {5, 3, 1, 4, 2};
std::sort(numbers.begin(), numbers.end()); // 기본 오름차순, numbers: {1, 2, 3, 4, 5}
std::sort(numbers.begin(), numbers.end(), std::greater<int>()); // 내림차순, numbers: {5, 4, 3, 2, 1}
std::sort(numbers.begin(), numbers.end(), [](int a, int b) { 
    return a < b; 
}); // 오름차순, 사용자 정의 비교

std::vector<std::pair<int, int>> pairs = {{1, 2}, {2, 1}, {1, 1}, {2, 2}};
std::stable_sort(pairs.begin(), pairs.end(), [](const auto& a, const auto& b) {
    return a.first < b.first; // first 기준 정렬, 동일 요소 상대 순서 유지
});

std::vector<int> numbers = {5, 3, 1, 4, 2, 6};
// 가장 작은 3개 요소를 앞에 배치하고 정렬
std::partial_sort(numbers.begin(), numbers.begin() + 3, numbers.end());
// numbers 앞 세 요소는 1, 2, 3, 나머지는 미정렬 4, 5, 6

3.2 nth_element

범위를 재배열하여 지정 위치의 요소가 정렬 후 해당 위치 값이 되도록 하고, 왼쪽 요소는 모두 이하, 오른쪽 요소는 모두 이상

std::vector<int> numbers = {5, 3, 1, 4, 2, 6};
// 세 번째로 작은 요소 찾기 (인덱스 2)
std::nth_element(numbers.begin(), numbers.begin() + 2, numbers.end());
// 이제 numbers[2]는 3, 왼쪽 요소 ≤ 3, 오른쪽 ≥ 3

3.3 binary_search, lower_bound, upper_bound

정렬된 컨테이너에서 사용해야 함

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

std::vector<int> sorted = {1, 3, 3, 5, 7};  // 먼저 정렬 필요

// 3 존재 여부 확인
bool exists = std::binary_search(sorted.begin(), sorted.end(), 3);  // true

// 첫 번째 ≥3 요소 찾기
auto lower = std::lower_bound(sorted.begin(), sorted.end(), 3);
std::cout << "lower_bound 인덱스: " << lower - sorted.begin() << std::endl;  // 출력: 1

// 첫 번째 >3 요소 찾기
auto upper = std::upper_bound(sorted.begin(), sorted.end(), 3);
std::cout << "upper_bound 인덱스: " << upper - sorted.begin() << std::endl;  // 출력: 3

3.4 merge

두 정렬된 범위를 새 컨테이너로 합병 (정렬 상태 유지)

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

// left와 right 합병 (모두 정렬 필요)
std::merge(left.begin(), left.end(), right.begin(), right.end(), merged.begin());  // merged: [1,2,3,4,5,6]

4、힙 알고리즘

STL은 범위를 힙으로操作하는 알고리즘을 제공하며, make_heap, push_heap, pop_heap, sort_heap 등이 포함됩니다.

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

heap_data.push_back(6);
std::push_heap(heap_data.begin(), heap_data.end()); // 새 요소를 힙에 추가, heap_data: {6, 4, 5, 2, 1, 3}

std::pop_heap(heap_data.begin(), heap_data.end()); // 최대 요소를 끝으로 이동, heap_data: {5, 4, 3, 2, 1, 6}
int max_element = heap_data.back(); // 최대 요소 6 획득
heap_data.pop_back(); // 최대 요소 제거

std::sort_heap(heap_data.begin(), heap_data.end()); // 힙을 오름차순으로 정렬, heap_data: {1, 2, 3, 4, 5}

5、최소/최대 알고리즘

5.1 min과 max

두 값 또는 초기화 목록에서 최소/최대 값 반환

int x = 5, y = 3;
int minimum = std::min(x, y); // 3
int maximum = std::max(x, y); // 5

auto min_from_list = std::min({4, 2, 8, 5, 1}); // 1
auto max_from_list = std::max({4, 2, 8, 5, 1}); // 8

5.2 min_element와 max_element

범위 내 최소/최대 요소의 반복자 반환

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

5.3 minmax_element (C++11)

범위 내 최소와 최대 요소를 동시에 반환

std::vector<int> values = {3, 1, 4, 2, 5};
auto result = std::minmax_element(values.begin(), values.end());
// result.first는 1 가리킴, result.second는 5 가리킴

6、数치 알고리즘 (에 있음)

6.1 accumulate

범위 내 요소의 누적 합계 (또는 사용자 정의 연산) 계산

#include <numeric>

std::vector<int> values = {1, 2, 3, 4, 5};
int sum = std::accumulate(values.begin(), values.end(), 0); // 합계, 초기값 0, 결과 15
int product = std::accumulate(values.begin(), values.end(), 1, std::multiplies<int>()); // 곱, 초기값 1, 결과 120

6.2 inner_product

두 범위의 내적 (또는 사용자 정의 연산) 계산

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

6.3 iota

연속적으로 증가하는 값으로 범위 채우기

std::vector<int> sequence(5);
std::iota(sequence.begin(), sequence.end(), 10); // 10, 11, 12, 13, 14로 채움

6.4 partial_sum

부분 합을 계산하여 결과的目标 범위에 저장

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

6.5 adjacent_difference

인접 요소의 차이를 계산하여 결과的目标 범위에 저장

std::vector<int> source = {1, 2, 3, 4, 5};
std::vector<int> destination(source.size());
std::adjacent_difference(source.begin(), source.end(), destination.begin()); // destination: {1, 1, 1, 1, 1}

7、기타

7.1 generate

생성 함수로 범위 채우기

std::vector<int> sequence(5);
int counter = 0;
std::generate(sequence.begin(), sequence.end(), [&counter]() { 
    return counter++; 
}); // 0, 1, 2, 3, 4로 채움

7.2 generate_n

생성 함수로 범위 시작 부분 n개 요소 채우기

std::vector<int> sequence(5);
int start = 10;
std::generate_n(sequence.begin(), 3, [&start]() { 
    return start++; 
}); // 처음 세 요소는 10, 11, 12, 나머지 두 요소는 변경 없음

7.3 includes

정렬된 범위가另一个 정렬된 범위의 모든 요소를 포함하는지 확인

std::vector<int> set1 = {1, 2, 3, 4, 5};
std::vector<int> set2 = {2, 4};
bool has_all = std::includes(set1.begin(), set1.end(), set2.begin(), set2.end()); // true

7.4 set_union, set_intersection, set_difference, set_symmetric_difference

집합 연산 수행: 합집합, 교집합, 차집합, 대칭 차집합

std::vector<int> v1 = {1, 2, 3, 4, 5};
std::vector<int> v2 = {3, 4, 5, 6, 7};
std::vector<int> result;

// 합집합
std::set_union(v1.begin(), v1.end(), v2.begin(), v2.end(), std::back_inserter(result));
// result: {1, 2, 3, 4, 5, 6, 7}

// 교집합
result.clear();
std::set_intersection(v1.begin(), v1.end(), v2.begin(), v2.end(), std::back_inserter(result));
// result: {3, 4, 5}

// 차집합 (v1 - v2)
result.clear();
std::set_difference(v1.begin(), v1.end(), v2.begin(), v2.end(), std::back_inserter(result));
// result: {1, 2}

// 대칭 차집합 (v1 ∪ v2 - v1 ∩ v2)
result.clear();
std::set_symmetric_difference(v1.begin(), v1.end(), v2.begin(), v2.end(), std::back_inserter(result));
// result: {1, 2, 6, 7}

8、자주 묻는 질문

1. sort와 stable_sort의 차이점은?

• sort는 퀵 정렬 (실제로는 introsort 알고리즘) 사용, 비안정 (동일 요소 상대 위치 변경 가능), 평균 시간 복잡도 O(n log n)
• stable_sort는 병합 정렬 사용, 안정 (동일 요소 상대 위치 불변), 시간 복잡도 O(n log n), 하지만 약간의 공간 오버헤드 존재

2. 왜 remove 알고리즘은 erase와 함께 사용해야 하는가? remove 알고리즘의 원리는 삭제할 요소를 "덮어쓰는" 방식으로, 유지할 요소를前面으로 이동하고 새로운 논리적 끝 반복자를 반환하지만, 컨테이너의 실제 크기를 수정하지 않음. erase는 반복자 범위로 실제 요소를 삭제하고 컨테이너 크기를 수정함. 따라서 결합 사용 필요: container.erase(std::remove(...), container.end())

3. 어떤 알고리즘이 컨테이너가 정렬되어 있어야 하는가? 이분 탐색 系列 (binary_search, lower_bound, upper_bound), 집합 알고리즘 (set_intersection, set_union 등), merge 등은 정렬된 상태에 의존하여高效적인 操作 (이분 탐색 O(log n))을 구현함