1. 수정되지 않는 시퀀스 알고리즘

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

1.1 찾기 알고리즘: find와 find_if

• find(start, end, value): value와 동일한 첫 번째 요소를 찾아 반복자를 반환 (없으면 end 반환)
• find_if(start, end, 조건자): 조건을 만족하는 첫 번째 요소를 찾습니다
• find_end(start, end, sub_start, sub_end): 부분 시퀀스가 마지막으로 나타나는 위치를 찾습니다

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

using namespace std;

vector<int> 데이터 = {2, 4, 6, 8, 10};

// 값 6을 찾기
auto 반복자 = find(데이터.begin(), 데이터.end(), 6);
if (반복자 != 데이터.end()) {
    cout << "찾음: " << *반복자 << endl;  // 출력: 6
}

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

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

1.2 개수 세기 알고리즘: count와 count_if

• count(start, end, value): value와 동일한 요소의 개수를 셉니다
• count_if(start, end, 조건자): 조건을 만족하는 요소의 개수를 셉니다

vector<int> 숫자들 = {3, 1, 4, 1, 5, 9, 2, 6};
int 개수 = count(숫자들.begin(), 숫자들.end(), 1); // 값 1의 개수, 결과는 2
int 짝수개수 = count_if(숫자들.begin(), 숫자들.end(), [](int x) { 
    return x % 2 == 0; 
}); // 짝수 개수, 결과는 4

1.3 각 요소에 함수 적용: for_each

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

vector<int> 값들 = {10, 20, 30, 40, 50};
for_each(값들.begin(), 값들.end(), [](int& x) { 
    x /= 10; // 각 요소를 10으로 나눔
});
// 이제 값들은 {1, 2, 3, 4, 5}

1.4 비교 알고리즘: equal과 mismatch

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

vector<int> 첫번째 = {5, 10, 15};
vector<int> 두번째 = {5, 10, 20};
vector<int> 세번째 = {5, 10, 15, 20};

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

// 첫번째와 세번째의 첫 번째 불일치 요소 찾기
auto 불일치 = mismatch(첫번째.begin(), 첫번째.end(), 세번째.begin());
if (불일치.first != 첫번째.end()) {
    cout << "불일치: " << *불일치.first << " vs " << *불일치.second << endl;  // 출력 없음 (첫 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(start, end, 목적지): [start, end)의 요소들을 목적지 시작 위치로 복사합니다
• copy_if(start, end, 목적지, 조건자): 조건을 만족하는 요소들을 목적지로 복사합니다

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> 첫번째 = {1, 2, 3};
vector<int> 두번째 = {4, 5, 6};
vector<int> 합계(3);
transform(첫번째.begin(), 첫번째.end(), 두번째.begin(), 합계.begin(), [](int x, int y) {
    return x + y;
});  // 합계: [5,7,9]

2.3 대체 알고리즘: replace, replace_if와 replace_copy

• replace(start, end, 이전값, 새값): 모든 이전값을 새값으로 대체합니다
• replace_if(start, end, 조건자, 새값): 조건을 만족하는 요소를 대체합니다
• replace_copy(start, end, 목적지, 이전값, 새값): 복사 시 요소를 대체합니다 (원본 컨테이너 변경 없음)

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(start, end, 값): 값과 같은 요소들을 "이동"하여 컨테이너 끝으로 보내고, 새로운 논리적 끝 반복자를 반환 (실제로 요소를 삭제하지 않음, erase와 함께 사용해야 함)
• remove_if(start, end, 조건자): 조건을 만족하는 요소들을 끝으로 이동시킵니다

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(start, end): 요소들을 빠른 정렬(불안정)으로 정렬합니다 (평균 시간 복잡도 O(n log n))
• stable_sort(start, end): 안정적인 정렬을 수행합니다 (같은 요소들의 상대적 위치 변경 없음)
• partial_sort(start, mid, end): 부분 정렬을 수행하여 [start, 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(start, end, 값): 값이 존재하는지 판단합니다 (bool 반환)
• lower_bound(start, end, 값): 값보다 크거나 같은 첫 번째 요소의 반복자를 반환합니다
• upper_bound(start, end, 값): 값보다 큰 첫 번째 요소의 반복자를 반환합니다

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> 첫번째 = {1, 3, 5};
vector<int> 두번째 = {2, 4, 6};
vector<int> 병합된(첫번째.size() + 두번째.size());

// 첫번째와 두번째 병합 (둘 다 정렬되어 있어야 함)
merge(첫번째.begin(), 첫번째.end(), 두번째.begin(), 두번째.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 = 10, b = 20;
int 최소값 = min(a, b); // 10
int 최대값 = max(a, b); // 20

auto 목록최소 = min({7, 3, 9, 1, 5}); // 1
auto 목록최대 = max({7, 3, 9, 1, 5}); // 9

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> 첫번째 = {1, 2, 3};
vector<int> 두번째 = {4, 5, 6};
int 내적 = inner_product(첫번째.begin(), 첫번째.end(), 두번째.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> 벡터1 = {1, 2, 3, 4, 5};
vector<int> 벡터2 = {2, 4};
bool 포함 = includes(벡터1.begin(), 벡터1.end(), 벡터2.begin(), 벡터2.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는 반복자 범위를 사용하여 실제로 요소를 삭제하고 컨테이너 크기를 수정합니다. 따라서 함께 사용해야 합니다: 컨테이너.erase(remove(...), 컨테이너.end()).

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

이진 검색 시리즈(binary_search, lower_bound, upper_bound), 집합 알고리즘(set_intersection, set_union 등), merge 등은 정렬된 상태를 필요로 합니다. 이러한 알고리즘들은 정렬된 상태를 기반으로 효율적인 작업(예: 이진 검색 O(log n))을 수행합니다.