1. 변경하지 않는 시퀀스 알고리즘

이러한 알고리즘들은 조작하는 컨테이너의 요소들을 변경하지 않습니다.

1.1 find와 find_if

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

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

using namespace std;

vector<int> 숫자들 = {1, 3, 5, 7, 9};

// 값 5를 찾기
auto 반복자 = find(숫자들.begin(), 숫자들.end(), 5);
if (반복자 != 숫자들.end()) {
    cout << "찾음: " << *반복자 << endl;  // 출력: 5
}

// 6보다 큰 첫 번째 요소 찾기
auto 반복자2 = find_if(숫자들.begin(), 숫자들.end(), [](int x) {
    return x > 6;
});
cout << "첫 번째 >6: " << *반복자2 << endl;  // 출력: 7

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

1.2 count와 count_if

• count(begin, end, value): value와 같은 요소의 개수를 세습니다.
• count_if(begin, end, predicate): 조건자를 만족하는 요소의 개수를 세습니다.

vector<int> 벡터 = {1, 2, 3, 2, 4, 2};
int 개수 = count(벡터.begin(), 벡터.end(), 2); // 2의 개수 세기, 결과는 3
int 짝수개수 = count_if(벡터.begin(), 벡터.end(), [](int x) { 
    return x % 2 == 0; 
}); // 짝수 개수, 결과는 3

1.3 for_each

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

vector<int> 데이터 = {1, 2, 3, 4, 5};
for_each(데이터.begin(), 데이터.end(), [](int& x) { 
    x *= 2; // 각 요소를 2배로 만듦
});
// 이제 데이터는 {2, 4, 6, 8, 10}이 됩니다

1.4 equal과 mismatch

• equal(b1, e1, b2): 두 범위 [b1,e1)와 [b2, b2+(e1-b1))가 같은지 판단합니다.
• mismatch(b1, e1, b2): 두 범위에서 처음으로 다른 요소의 반복자 쌍(pair)을 반환합니다.

vector<int> a = {1, 2, 3};
vector<int> b = {1, 2, 4};
vector<int> c = {1, 2, 3, 4};

// a와 b의 처음 3개 요소 비교
bool 동일 = equal(a.begin(), a.end(), b.begin());
cout << "a == b? " << boolalpha << 동일 << endl;  // 출력: false

// a와 c의 첫 번째 불일치 요소 찾기
auto 불일치 = mismatch(a.begin(), a.end(), c.begin());
if (불일치.first != a.end()) {
    cout << "불일치: " << *불일치.first << " vs " << *불일치.second << endl;  // 출력 없음 (a와 c의 처음 3 요소 동일)
}

1.5 all_of, any_of, none_of

범위 내 요소가 전부, 일부 또는 조건을 만족하지 않는지 확인합니다.

vector<int> 숫자들 = {2, 4, 6, 8};
bool 모두짝수 = all_of(숫자들.begin(), 숫자들.end(), [](int x) { 
    return x % 2 == 0; 
}); // true
bool 홀수존재 = any_of(숫자들.begin(), 숫자들.end(), [](int x) { 
    return x % 2 != 0; 
}); // false
bool 음수없음 = none_of(숫자들.begin(), 숫자들.end(), [](int x) { 
    return x < 0; 
}); // true

2. 변경하는 시퀀스 알고리즘

이러한 알고리즘들은 조작하는 컨테이너의 요소들을 변경합니다.

2.1 copy와 copy_if

• copy(begin, end, dest): [begin, end)의 요소들을 dest 시작 위치로 복사합니다.
• copy_if(begin, end, dest, predicate): 조건자를 만족하는 요소들을 dest로 복사합니다.

vector<int> 원본 = {1, 2, 3, 4, 5};
vector<int> 대상(5);  // 충분한 공간을 미리 할당해야 함

// 모든 요소 복사
copy(원본.begin(), 원본.end(), 대상.begin());  // 대상: [1,2,3,4,5]

// 짝수 요소를 새 컨테이너로 복사
vector<int> 짝수들;
copy_if(원본.begin(), 원본.end(), back_inserter(짝수들), [](int x) {
    return x % 2 == 0;
});  // 짝수들: [2,4]

주의: back_inserter(대상)는 자동으로 push_back을 호출하므로 미리 공간을 할당할 필요가 없습니다.

2.2 transform

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

vector<int> 숫자들 = {1, 2, 3};
vector<int> 제곱들(3);

// 제곱 계산 (단일 매개변수 변환)
transform(숫자들.begin(), 숫자들.end(), 제곱들.begin(), [](int x) {
    return x * x;
});  // 제곱들: [1,4,9]

// 두 컨테이너 요소 더하기 (이중 매개변수 변환)
vector<int> a = {1, 2, 3};
vector<int> b = {4, 5, 6};
vector<int> 합(3);
transform(a.begin(), a.end(), b.begin(), 합.begin(), [](int x, int y) {
    return x + y;
});  // 합: [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): 복사할 때 요소를 바꿉니다 (원본 컨테이너 변경 없음).

vector<int> 숫자들 = {1, 2, 3, 2, 5};

// 모든 2를 20으로 바꾸기
replace(숫자들.begin(), 숫자들.end(), 2, 20);  // 숫자들: [1,20,3,20,5]

// 10보다 큰 요소를 0으로 바꾸기
replace_if(숫자들.begin(), 숫자들.end(), [](int x) {
    return x > 10;
}, 0);  // 숫자들: [1,0,3,0,5]

// 복사 시 3을 300으로 바꾸기 (원본 컨테이너 변경 없음)
vector<int> 결과;
replace_copy(숫자들.begin(), 숫자들.end(), back_inserter(결과), 3, 300);  // 결과: [1,0,300,0,5]

2.4 remove, remove_if와 erase

• remove(begin, end, value): value와 같은 요소들을 컨테이너의 끝으로 "이동"시키고, 새로운 논리적 끝 반복자를 반환합니다 (실제로 요소를 삭제하지 않음, erase와 함께 사용해야 함).
• remove_if(begin, end, predicate): 조건자를 만족하는 요소들을 끝으로 이동시킵니다.

vector<int> 숫자들 = {1, 2, 3, 2, 4};

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

// 물리적으로 삭제 (실제로 요소 제거)
숫자들.erase(새끝, 숫자들.end());  // 숫자들: [1,3,4]

// 람다와 함께 짝수 삭제
숫자들 = {1, 2, 3, 4, 5};
숫자들.erase(remove_if(숫자들.begin(), 숫자들.end(), [](int x) {
    return x % 2 == 0;
}), 숫자들.end());  // 숫자들: [1,3,5]

2.5 unique

범위 내 연속된 중복 요소를 제거하고 새로운 논리적 끝 반복자를 반환합니다. 일반적으로 erase와 함께 사용합니다.

vector<int> 데이터 = {1, 1, 2, 2, 3, 3, 3, 4, 5};
auto 마지막 = unique(데이터.begin(), 데이터.end());
데이터.erase(마지막, 데이터.end()); // 데이터는 {1, 2, 3, 4, 5}가 됩니다

2.6 reverse

범위 내 요소들의 순서를 뒤집습니다.

vector<int> 데이터 = {1, 2, 3, 4, 5};
reverse(데이터.begin(), 데이터.end()); // 데이터는 {5, 4, 3, 2, 1}이 됩니다

2.7 rotate

범위 내 요소들을 회전시켜 중간 요소를 새로운 첫 번째 요소로 만듭니다.

vector<int> 데이터 = {1, 2, 3, 4, 5};
rotate(데이터.begin(), 데이터.begin() + 2, 데이터.end()); // 3을 시작점으로 회전, 데이터는 {3, 4, 5, 1, 2}가 됩니다

2.8 shuffle

범위 내 요소들을 무작위로 재배열합니다 (C++11 이상 필요).

#include <random>
#include <algorithm>

vector<int> 데이터 = {1, 2, 3, 4, 5};
random_device rd;
mt19937 g(rd());
shuffle(데이터.begin(), 데이터.end(), g); // 데이터의 요소들을 무작위로 섞음

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)가 전체 범위에서 가장 작은 요소들이 되도록 정렬합니다.

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

vector<pair<int, int>> 데이터 = {{1, 2}, {2, 1}, {1, 1}, {2, 2}};
stable_sort(데이터.begin(), 데이터.end(), [](const auto& a, const auto& b) {
    return a.first < b.first; // first 기준 정렬, 같은 요소들의 상대적 순서 유지
});

vector<int> 데이터 = {5, 3, 1, 4, 2, 6};
// 가장 작은 3개 요소를 앞에 놓고 정렬
partial_sort(데이터.begin(), 데이터.begin() + 3, 데이터.end());
// 이제 데이터의 처음 3 요소는 1, 2, 3이고, 나머지는 정렬되지 않은 4, 5, 6입니다

3.2 nth_element

범위를 재배열하여 지정된 위치의 요소가 정렬된 후의 요소가 되도록 하고, 왼쪽 요소들은 그 요소보다 작거나 같고, 오른쪽 요소들은 그 요소보다 크거나 같도록 만듭니다.

vector<int> 데이터 = {5, 3, 1, 4, 2, 6};
// 세 번째로 작은 요소(인덱스 2) 찾기
nth_element(데이터.begin(), 데이터.begin() + 2, 데이터.end());
// 이제 데이터[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보다 큰 첫 번째 요소의 반복자를 반환합니다.

vector<int> 정렬된 = {1, 3, 3, 5, 7};  // 먼저 정렬되어야 함

// 3이 존재하는지 확인
bool 존재 = binary_search(정렬된.begin(), 정렬된.end(), 3);  // true

// 첫 번째 >=3인 요소 찾기
auto lb = lower_bound(정렬된.begin(), 정렬된.end(), 3);
cout << "lower_bound 인덱스: " << lb - 정렬된.begin() << endl;  // 출력: 1

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

3.4 merge

두 개의 정렬된 범위를 새로운 컨테이너로 병합합니다 (정렬 상태 유지).

vector<int> a = {1, 3, 5};
vector<int> b = {2, 4, 6};
vector<int> 병합된(a.size() + b.size());

// a와 b 병합 (둘 다 정렬되어야 함)
merge(a.begin(), a.end(), b.begin(), b.end(), 병합된.begin());  // 병합된: [1,2,3,4,5,6]

4. 힙 알고리즘

STL은 범위를 힙으로 조작하는 알고리즘인 make_heap, push_heap, pop_heap, sort_heap 등을 제공합니다.

vector<int> 데이터 = {4, 1, 3, 2, 5};
make_heap(데이터.begin(), 데이터.end()); // 최대 힙 구성, 데이터는 {5, 4, 3, 2, 1}이 됨

데이터.push_back(6);
push_heap(데이터.begin(), 데이터.end()); // 새 요소를 힙에 추가, 데이터는 {6, 4, 5, 2, 1, 3}이 됨

pop_heap(데이터.begin(), 데이터.end()); // 최대 요소를 끝으로 이동, 데이터는 {5, 4, 3, 2, 1, 6}이 됨
int 최대값 = 데이터.back(); // 최대 요소 6 얻기
데이터.pop_back(); // 최대 요소 제거

sort_heap(데이터.begin(), 데이터.end()); // 힙을 오름차순 시퀀스로 정렬, 데이터는 {1, 2, 3, 4, 5}가 됨

5. 최소/최대값 알고리즘

5.1 min과 max

두 값 또는 초기화 목록에서 최소/최대값을 반환합니다.

int a = 5, b = 3;
int 최소값 = min(a, b); // 3
int 최대값 = max(a, b); // 5

auto 목록최소 = min({4, 2, 8, 5, 1}); // 1
auto 목록최대 = max({4, 2, 8, 5, 1}); // 8

5.2 min_element와 max_element

범위 내 최소/최대 요소의 반복자를 반환합니다.

vector<int> 데이터 = {3, 1, 4, 2, 5};
auto 최소반복자 = min_element(데이터.begin(), 데이터.end()); // 1을 가리킴
auto 최대반복자 = max_element(데이터.begin(), 데이터.end()); // 5를 가리킴

5.3 minmax_element (C++11)

범위 내 최소 및 최대 요소의 반복자를 동시에 반환합니다.

vector<int> 데이터 = {3, 1, 4, 2, 5};
auto 최소최대 = minmax_element(데이터.begin(), 데이터.end());
// 최소최대.first는 1을, 최소최대.second는 5를 가리킴

6. 수치 알고리즘 ( 헤더에 있음)

6.1 accumulate

범위 내 요소들의 누적 합을 계산합니다 (또는 사용자 정의 작업).

#include <numeric>

vector<int> 데이터 = {1, 2, 3, 4, 5};
int 합 = accumulate(데이터.begin(), 데이터.end(), 0); // 합, 초기값 0, 결과 15
int 곱 = accumulate(데이터.begin(), 데이터.end(), 1, multiplies<int>()); // 곱, 초기값 1, 결과 120

6.2 inner_product

두 범위의 내적을 계산합니다 (또는 사용자 정의 작업).

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

6.3 iota

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

vector<int> 데이터(5);
iota(데이터.begin(), 데이터.end(), 10); // 10, 11, 12, 13, 14로 채움

6.4 partial_sum

부분 합을 계산하고 결과를 목표 범위에 저장합니다.

vector<int> 원본 = {1, 2, 3, 4, 5};
vector<int> 목표(원본.size());
partial_sum(원본.begin(), 원본.end(), 목표.begin()); // 목표는 {1, 3, 6, 10, 15}가 됨

6.5 adjacent_difference

인접 요소들의 차이를 계산하고 결과를 목표 범위에 저장합니다.

vector<int> 원본 = {1, 2, 3, 4, 5};
vector<int> 목표(원본.size());
adjacent_difference(원본.begin(), 원본.end(), 목표.begin()); // 목표는 {1, 1, 1, 1, 1}이 됨

7. 기타 알고리즘

7.1 generate

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

vector<int> 데이터(5);
int n = 0;
generate(데이터.begin(), 데이터.end(), [&n]() { 
    return n++; 
}); // 0, 1, 2, 3, 4로 채움

7.2 generate_n

생성 함수로 범위의 처음 n개 요소를 채웁니다.

vector<int> 데이터(5);
int n = 10;
generate_n(데이터.begin(), 3, [&n]() { 
    return n++; 
}); // 처음 3 요소는 10, 11, 12이고, 나머지는 변경되지 않음

7.3 includes

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

vector<int> vec1 = {1, 2, 3, 4, 5};
vector<int> vec2 = {2, 4};
bool 포함 = includes(vec1.begin(), vec1.end(), vec2.begin(), vec2.end()); // true

7.4 set_union, set_intersection, set_difference, set_symmetric_difference

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

vector<int> v1 = {1, 2, 3, 4, 5};
vector<int> v2 = {3, 4, 5, 6, 7};
vector<int> 결과;

// 합집합
set_union(v1.begin(), v1.end(), v2.begin(), v2.end(), back_inserter(결과));
// 결과는 {1, 2, 3, 4, 5, 6, 7}이 됨

// 교집합
결과.clear();
set_intersection(v1.begin(), v1.end(), v2.begin(), v2.end(), back_inserter(결과));
// 결과는 {3, 4, 5}가 됨

// 차집합 (v1 - v2)
결과.clear();
set_difference(v1.begin(), v1.end(), v2.begin(), v2.end(), back_inserter(결과));
// 결과는 {1, 2}가 됨

// 대칭 차집합 (v1 ∪ v2 - v1 ∩ v2)
결과.clear();
set_symmetric_difference(v1.begin(), v1.end(), v2.begin(), v2.end(), back_inserter(결과));
// 결과는 {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(remove(...), container.end()).

3. 어떤 알고리즘들은 컨테이너가 정렬되어 있어야 하나요?

이진 검색 시리즈(binary_search, lower_bound, upper_bound), 집합 알고리즘(set_intersection, set_union 등), merge 등은 정렬된 컨테이너에서 사용해야 합니다. 이러한 알고리즘들은 효율적인 작업(예: 이진 검색 O(log n))을 위해 정렬된 상태에 의존합니다.