1. 변경하지 않는 순차 알고리즘

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

1.1 find 및 find_if

• find(시작, 끝, 값): 값과 같은 첫 번째 요소를 찾아 반복자를 반환 (찾지 못하면 끝 반환)
• find_if(시작, 끝, 술어): 술어(predicate)를 만족하는 첫 번째 요소를 찾음
• find_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
}

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

// 하위 시퀀스 찾기
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(시작, 끝, 값): 값과 같은 요소의 개수를 세기
• count_if(시작, 끝, 술어): 술어를 만족하는 요소의 개수를 세기

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

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> 첫번째 = {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> 숫자들 = {4, 8, 12, 16};
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(시작, 끝, 대상): [시작, 끝)의 요소를 대상 시작 위치로 복사
• copy_if(시작, 끝, 대상, 술어): 술어를 만족하는 요소를 대상으로 복사

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> 첫번째 = {10, 20, 30};
vector<int> 두번째 = {1, 2, 3};
vector<int> 합계(3);
transform(첫번째.begin(), 첫번째.end(), 두번째.begin(), 합계.begin(), [](int x, int y) {
    return x + y;
});  // 합계: [11,22,33]

2.3 replace, replace_if 및 replace_copy

• replace(시작, 끝, 기존값, 새값): 모든 기존값을 새값으로 교체
• replace_if(시작, 끝, 술어, 새값): 술어를 만족하는 요소를 교체
• replace_copy(시작, 끝, 대상, 기존값, 새값): 복사 시 요소 교체 (원본 컨테이너 변경 안 함)

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(시작, 끝, 값): 값과 같은 요소를 컨테이너 끝으로 "이동", 새로운 논리적 끝 반복자 반환 (실제로 요소 삭제하지 않음, erase와 함께 사용 필요)
• remove_if(시작, 끝, 술어): 술어를 만족하는 요소를 끝으로 이동

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(시작, 끝): 요소를 빠르게 정렬 (불안정, 평균 시간 복잡도 O(n log n))
• stable_sort(시작, 끝): 안정적 정렬 (동일 요소의 상대적 위치 변경 안 됨)
• partial_sort(시작, 중간, 끝): 부분 정렬, [시작, 중간)이 전체 범위에서 가장 작은 요소가 되도록 정렬

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(시작, 끝, 값): 값이 존재하는지 확인 (bool 반환)
• lower_bound(시작, 끝, 값): 값보다 작지 않은 첫 번째 요소의 반복자 반환
• upper_bound(시작, 끝, 값): 값보다 큰 첫 번째 요소의 반복자 반환

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 = 7, b = 4;
int 최소값 = min(a, b); // 4
int 최대값 = max(a, b); // 7

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> 첫번째 = {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, 2, 3, 4, 5};
vector<int> 두번째 = {2, 4};
bool 포함 = includes(첫번째.begin(), 첫번째.end(), 두번째.begin(), 두번째.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))을 위해 정렬된 상태를 필요로 합니다.