[C++] <algorithm>

📌 1. 정렬

✔ sort()

• 배열 또는 벡터를 오름차순으로 정렬
• 기존 순서를 보장하지 않음

🔗 ex)

#include<iostream>
#include<algorithm>

using namespace std;

int main(){
    int arr[5] = {4,2,1,5,3};
    sort(arr, arr+5);
    for(int i=0; i<5; i++){
        cout<<arr[i]<<endl;
    }
}

• 기본은 오름차순으로 정렬된다
• sort함수 괄호 안에는 기본적으로 두 개의 인자가 전달된다
  • 첫 번째 인자 : 배열의 시작점
  • 두 번째 인자 : 마지막 주소 + 1
• 내림차순
  • 세번째 인자 전달

🔗 ex)

#include <iostream>
#include <algorithm>

using namespace std;
   
bool cmp(int a, int b){
	return a>b;
}
   
int main(){
	int arr[5]={4,1,5,2,3};
   	sort(arr, arr+5, cmp);
    for(int i=0; i<5; i++){
       	cout<<arr[i]<<endl;
    }
}

 

• 구조체 정렬
  • cmp() 비교함수를 이용
  • cmp 없이 그냥 sort 함수만 사용하면 에러남!

🔗 ex)

#include <iostream>
#include <algorithm>
  
using namespace std;
  
typedef struct game {
	int start;
    int end;
 } game;
  
 bool cmp(game a, game b) {
 	if (a.start == b.start) return a.end < b.end;
    return a.start < b.start;
 }
  
 int main() {
    game arr[5] = {
                    {3, 9},
                    {2, 5},
                    {1, 7},
                    {4, 5}, 
                    {5, 8}
                   };
    sort(arr, arr + 5, cmp);
    for(int i = 0; i < 5; i++) {
        cout << arr[i].start << " " << arr[i].end << endl;
    }
  }

 

 

 

✔ stable_sort()

• 일부분만 정렬하고 나머지는 정렬되지 않은 상태로 유지
  • 안정 정렬 알고리즘
• 정렬 후 같은 값이 있을 경우 원래의 순서를 유지함 (기존 순서 보장)
• merge sort 알고리즘 사용
  • 정렬이 된 부분 리스트를 병합할 때, 추가적인 메모리를 사용
• 사용법은 sort()와 같음

 

✔ nth_element()

• n번째 요소를 기준으로 분할 정렬을 수행
• 첫 번째 인자 : 정렬의 시작 위치를 가리키는 반복자
• 두 번째 인자 : n 번째로 작은 요소를 가리키는 반복자
• 세 번째 인자 : 정렬 끝 위치를 가리키는 반복자

 

🔗 ex)

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

using namespace std;
int main() {
    vector<int> vec = {9, 3, 2, 8, 5, 1, 6};

    nth_element(vec.begin(), vec.begin() + 2, vec.end());

    cout << "3번째로 작은 요소: " << vec[2] << endl;

    return 0;
}

 

📌 2. 검색

✔ find()

• 특정 값을 검색하여 첫 번째 일치하는 요소의 위치를 반환
• 첫 번째 인자(first) : 탐색 시작 위치를 가리키는 반복자
• 두 번째 인자(last) : 탐색 끝 위치를 가리키는 반복자
• 세 번째 인자(value) : 찾으려는 값을 나타내는 객체

-> first~last 범위에서 value와 일치하는 첫 번째 요소를 찾음

 

🔗 ex)

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

using namespace std;
int main() {
    vector<int> vec = {1, 3, 5, 7, 9};

    auto it = find(vec.begin(), vec.end(), 5);
    if (it != vec.end()) {
        cout << "Element found at index: " << distance(vec.begin(), it) << endl;
    } else {
        cout << "Element not found" << endl;
    }

    return 0;
}

 

✔ binary_search()

• 이진 검색을 수행하여 값이 컨테이너에 있는지 확인
• 첫 번째 인자(first) : 탐색 시작 위치를 가리키는 반복자
• 두 번째 인자(last) : 탐색 끝 위치를 가리키는 반복자
• 세 번째 인자(value) : 찾으려는 값을 나타내는 객체
  • first~last 범위에서 value와 일치하는 요소를 이진 탐색으로 찾음
  • 찾으면 true, 못찾으면 false 반환

 

🔗 ex)

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

using namespace std;
int main() {
    vector<int> vec = {1, 3, 5, 7, 9};

    bool found = binary_search(vec.begin(), vec.end(), 5);
    if (found) {
        cout << "요소 찾음" << endl;
    } else {
        cout << "요소 못찾음" << endl;
    }

    return 0;
}

⚡ find()와 binary_search()의 차이점

• 검색 알고리즘
  • find() : 선형 검색 알고리즘을 사용하여 값을 찾음
    • 컨테이너의 처음부터 끝까지 순차적으로 탐색하여 값을 비교(컨테이너가 정렬되어 있지 않아도 동작함)
  • binary_search() : 이진 검색 알고리즘을 사용하여 값을 찾음
    • 컨테이너가 정렬되어 있다고 가정하며 컨테이너를 반으로 나누어 값을 찾고자 하는 값과 비요함 (정렬된 컨태이너에서만 동작)

•  

 

✔ lower_bound()/upper_bound()

• 정렬된 컨테이너에서 이진 탐색을 수행하여 특정 값의 하한과 상한 위치를 찾음
• 첫 번째 요소(first) : 탐색 대상 요소들의 시작 위치를 가리키는 전진 반복자
• 두 번째 요소(last) : 탐색 대상 요소들의 끝 위치를 기리키는 전진 반복자
• 세 번째 요소(value) : 찾고자 하는 값

• first~last 범위에서 이진 탐색을 수행하여 value 이상인 첫 번째 요소의 위치를 반환
• 반환값 : ForwardIterator 형식의 반복자이며 value 이상인 첫 번째 요소의 위치를 가리킴
• lower_bound() :만약 value값보다 작거나 같은 값이 컨테이너에 존재하지 않을 경우 last 반환
• upper_bound() : 만약 value값보다 큰 값이 컨테이너에 존재하지 않는 경우 last 반환

 

 

📌 3. 복사

✔ copy()

• 한 컨테이너에서 다른 컨테이너로 요소를 복사
• 첫 번째 요소(first) : 복사할 요소들의 시작 위치를 가리키는 입력 반복자
• 두 번째 요소(last) : 복사할 요소들의 끝 위치를 가리키는 입력 반복자
• 세 번째 요소(result) : 복사한 요소들을 저장할 결과 컨테이너의 시작 위치를 가리키는 출력 반복자

• first~last 범위에서 요소들을 복사하여 result 컨테이너에 저장
• 복사된 요소들의 끝 위치를 나타내는 출력 반복자를 반환함

🔗 ex)

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int main() {
    vector<int> source = {1, 2, 3, 4, 5};
    vector<int> destination(source.size());

    copy(source.begin(), source.end(), destination.begin());

    cout << "복사된 요소: ";
    for (const auto& element : destination) {
        cout << element << " ";
    }
    cout << endl;

    return 0;
}

 

✔copy_if()

• 조건을 만족하는 요소만을 복사
• 첫 번째 요소(first) : 복사할 요소들의 시작 위치를 가리키는 입력 반복자
• 두 번째 요소(last) : 복사할 요소들의 끝 위치를 가리키는 입력 반복자
• 세 번째 요소(result) : 복사한 요소들을 저장할 결과 컨테이너의 시작 위치를 가리키는 출력 반복자
• 네 번째 요소(pred) : 복사할 요소를 선택하는 데 사용할 단항 조건자 함수나 함수 객체

• first~last 범위에서 조건 pred를 만족하는 요소들을 복사하여 result 컨테이너에 저장
• 복사된 요소들의 끝 위치를 나타내는 출력 반복자를 반환함

 

🔗 ex)

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

using namespace std;

bool isEven(int num) {
    return num % 2 == 0;
}

int main() {
    vector<int> source = {1, 2, 3, 4, 5};
    vector<int> destination;

    copy_if(source.begin(), source.end(), back_inserter(destination), isEven);

    cout << "복사된 요소 : ";
    for (const auto& element : destination) {
        cout << element << " ";
    }
    cout << endl;

    return 0;
}

 

📌 4. 변형

✔ transform()

• 한 컨테이너의 요소를 다른 컨태이너로 변경
• 첫 번째 요소(first) : 변환할 요소들의 시작 위치를 가리키는 입력 반복자
• 두 번째 요소(last) : 변환할 요소들의 끝 위치를 가리키는 입력 반복자
• 세 번째 요소(result) : 변환한 요소들을 저장할 결과 컨테이너의 시작 위치를 가리키는 출력 반복자
• 네 번째 요소(op) : 요소를 변환하는 데 사용할 단항 연산자 함수나 함수 객체

• first~last 범위에 있는 요소들을 op 함수나 함수 객체를 사용하여 변환하고, 변환된 요소들을 result 컨테이너에 저장
• 변환된 요소들의 끝 위치를 나타내는 출력반복자를 반환

🔗 ex)

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

using namespace std;

int square(int num) {
    return num * num;
}

int main() {
    vector<int> source = {1, 2, 3, 4, 5};
    vector<int> destination(source.size());

    transform(source.begin(), source.end(), destination.begin(), square);

    cout << "변환된 요소: ";
    for (const auto& element : destination) {
        cout << element << " ";
    }
    cout << endl;

    return 0;
}

 

✔ replace()

• 특정 값을 다른 값으로 교체
• 첫 번째 요소(first) : 교체할 요소들의 시작 위치를 가리키는 전진 반복자
• 두 번째 요소(last) : 교체할 요소들의 끝 위치를 가리키는 전진 반복자
• 세 번째 요소(old_value) : 교체할 대상 값
• 네 번째 요소(new_value) : 대체할 값

•  first~last 범위에 있는 요소들 중에서 old_value와 일치하는 값을 찾아서 new_value로 대체

🔗 ex)

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

using namespace std;

int main() {
    vector<int> numbers = {1, 2, 3, 2, 4, 2, 5};

    replace(numbers.begin(), numbers.end(), 2, 9);

    cout << "대체된 요소값 : ";
    for (const auto& element : numbers) {
        cout << element << " ";
    }
    cout << endl;

    return 0;
}

 

✔ reverse()

• 컨테이너의 요소 순서를 뒤집음
• 첫 번째 인자(first) : 역순으로 뒤집을 요소들의 시작 위치를 가리키는 양방향 반복자
• 두 번째 인자(last) : 역순으로 뒤집을 요소들의 끝 위치를 가리키는 양방향 반복자

• first~last 범위에 있는 요소들을 역순으로 뒤집음

 

🔗 ex)

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

using namespace std;

int main() {
    vector<int> numbers = {1, 2, 3, 4, 5};

    reverse(numbers.begin(), numbers.end());

    cout << "뒤집힌 요소들 : ";
    for (const auto& element : numbers) {
        cout << element << " ";
    }
    cout << endl;

    return 0;
}

 

 

📌 5. 순열

✔ next_permutation()/prev_permutation()

• 순열을 생성하고 다음/이전 순열로 이동
• 첫 번째 인자(first) : 순열을 생성할 요소들의 시작 위치를 가리키는 양방향 반복자
• 두 번째 인자(last) : 순열을 생성할 요소들의 끝 위치를 가리키는 양방향 반복자

• first~last 범위에 있는 요소들을 순서대로 재배열하여 다음 순열을 생성
• 다음/이전 순열이 존재하지 않는 경우 : 요소들의 순서를 가장 작은 순열로 재배열하고 false 반환
• 순열을 생성한 경우 : 요소들의 순서를 다음 순열로 변경하고 true 반환

 

🔗 ex) next_permutation() 사용한 예제

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

using namespace std;

int main() {
    vector<int> numbers = {1, 2, 3};

    cout << "순열들 : " << endl;
    do {
        for (const auto& element : numbers) {
            cout << element << " ";
        }
        cout << endl;
    } while (next_permutation(numbers.begin(), numbers.end()));

    return 0;
}

 

 

📌 6. 집합 연산

✔ set_union()

• 합집합

template<class InputIt1, class InputIt2, class OutputIt>
OutputIt set_union(InputIt1 first1, InputIt1 last1, InputIt2 first2, InputIt2 last2, OutputIt d_first);

• first1, last1: 첫 번째 집합의 요소들의 범위를 가리키는 입력 반복자
• first2, last2: 두 번째 집합의 요소들의 범위를 가리키는 입력 반복자
• d_first: 결과를 저장할 컨테이너의 시작 위치를 가리키는 출력 반복자

•  first1 ~ last1 사이의 첫 번째 집합과 first2 ~ last2 사이의 두 번째 집합을 합하여 결과를 d_first를 시작하는 컨테이너에 저장

 

🔗 ex)

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

using namespace std;

int main() {
    vector<int> set1 = {1, 3, 5, 7, 9};
    vector<int> set2 = {2, 4, 6, 8, 10};

    vector<int> result(set1.size() + set2.size());

    auto it = set_union(set1.begin(), set1.end(), set2.begin(), set2.end(), result.begin());

    cout << "Union set: ";
    for (auto i = result.begin(); i != it; ++i) {
        cout << *i << " ";
    }
    cout << endl;

    return 0;
}

 

✔ set_intersection()

• 교집합

template<class InputIt1, class InputIt2, class OutputIt>
OutputIt set_intersection(InputIt1 first1, InputIt1 last1, InputIt2 first2, InputIt2 last2, OutputIt d_first);

• first1, last1: 첫 번째 집합의 요소들의 범위를 가리키는 입력 반복자
• first2, last2: 두 번째 집합의 요소들의 범위를 가리키는 입력 반복자
• d_first: 결과를 저장할 컨테이너의 시작 위치를 가리키는 출력 반복자

•  first1 ~ last1 사이의 첫 번째 집합과 first2 ~ last2 사이의 두 번째 집합을 교집합하여 결과를 d_first를 시작하는 컨테이너에 저장

 

🔗 ex)

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

using namespace std;

int main() {
    vector<int> set1 = {1, 3, 5, 7, 9};
    vector<int> set2 = {3, 5, 7, 9, 11};

    vector<int> result(min(set1.size(), set2.size()));

    auto it = set_intersection(set1.begin(), set1.end(), set2.begin(), set2.end(), result.begin());

    cout << "Intersection set: ";
    for (auto i = result.begin(); i != it; ++i) {
        cout << *i << " ";
    }
    cout <<endl;

    return 0;
}

 

✔ set_difference()

• 차집합

template<class InputIt1, class InputIt2, class OutputIt>
OutputIt set_difference(InputIt1 first1, InputIt1

• first1, last1: 첫 번째 집합의 요소들의 범위를 가리키는 입력 반복자
• first2, last2: 두 번째 집합의 요소들의 범위를 가리키는 입력 반복자
• d_first: 결과를 저장할 컨테이너의 시작 위치를 가리키는 출력 반복자

•  first1 ~ last1 사이의 첫 번째 집합과 first2 ~ last2 사이의 두 번째 집합의 차집합 결과를 d_first를 시작하는 컨테이너에 저장

 

🔗 ex)

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

using namespace std;

int main() {
    vector<int> set1 = {1, 2, 3, 4, 5};
    vector<int> set2 = {3, 4, 5, 6, 7};

    vector<int> result(set1.size());

    auto it = set_difference(set1.begin(), set1.end(), set2.begin(), set2.end(), result.begin());

    cout << "Difference set: ";
    for (auto i = result.begin(); i != it; ++i) {
        cout << *i << " ";
    }
    cout << endl;

    return 0;
}

 

✔ set_symmetric_difference()

• 두 개의 정렬된 컨테이너의 대칭 차집합을 생성

template<class InputIt1, class InputIt2, class OutputIt>
OutputIt set_symmetric_difference(InputIt1 first1, InputIt1 last1, InputIt2 first2, InputIt2 last2, OutputIt d_first);

• first1, last1: 첫 번째 집합의 요소들의 범위를 가리키는 입력 반복자
• first2, last2: 두 번째 집합의 요소들의 범위를 가리키는 입력 반복자
• d_first: 결과를 저장할 컨테이너의 시작 위치를 가리키는 출력 반복자

•  first1 ~ last1 사이의 첫 번째 집합과 first2 ~ last2 사이의 두 번째 집합의 대칭 차집합을 생성하여 결과를 d_first를 시작하는 컨테이너에 저장

 

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

using namespace std;

int main() {
    vector<int> set1 = {1, 2, 3, 4, 5};
    vector<int> set2 = {3, 4, 5, 6, 7};

    vector<int> result(set1.size() + set2.size());

    auto it = set_symmetric_difference(set1.begin(), set1.end(), set2.begin(), set2.end(), result.begin());

    cout << "Symmetric Difference set: ";
    for (auto i = result.begin(); i != it; ++i) {
        cout << *i << " ";
    }
    cout << endl;

    return 0;
}

 

 

📌 7. 수치

✔ accumulate()

• 컨테이너의 요소들을 합산하는 기능

template<class InputIt, class T>
T accumulate(InputIt first, InputIt last, T init);

• first, last: 요소들의 범위를 가리키는 입력 반복자
• init: 초기값으로 사용될 값

•  first~last 사이의 요소들을 init 값과 누적하여 연산을 수행

 

✔ min()

• 최솟값

template<class T>
const T& min(const T& a, const T& b);

• a, b: 비교할 두 값
  • a, b 중에서 작은 값 선택
  • 만약 같다면 a값 반환

 

✔ max()

• 최댓값

template<class T>
const T& max(const T& a, const T& b);

• a, b: 비교할 두 값
• a, b 중에서 큰 값 선택
• 만약 같다면 a값 반환

 

✔ min_element()

• 최솟값의 위치

template<class ForwardIt>
ForwardIt min_element(ForwardIt first, ForwardIt last);

• first, last: 검색할 요소들의 범위를 가리키는 반복자
• first~last 요소들을 비교하여 최솟값을 가진 요소의 위치 반환
• 첫 번째 요소의 위치 반환

 

✔ max_element()

• 최댓값의 위치

template<class ForwardIt>
ForwardIt max_element(ForwardIt first, ForwardIt last);

• first, last: 검색할 요소들의 범위를 가리키는 반복자
• first~last 요소들을 비교하여 최댓값을 가진 요소의 위치 반환
• 첫 번째 요소의 위치 반환

 

✔ count()

• 특정 값의 개수 계산

template<class InputIt, class T>
typename iterator_traits<InputIt>::difference_type count(InputIt first, InputIt last, const T& value);

• first, last: 검색할 요소들의 범위를 가리키는 반복자
• value: 검색할 값을 나타내는 변수
• first~last 요소들을 순회하며 value와 일치하는 요소의 개수를 세어 반환

 

📌 8. 중복 제거

✔ unique()

• 연속된 범위에서 중복된 원소를 제거 후 범위의 끝 위치 반환

std::unique(first, last);

 

✔ unique_copy()

• 연속된 범위에서 중복된 원소를 제거하고, 제거된 원소를 새로운 컨테이너에 복사 -> 범위의 끝 위치 반환

std::unique_copy(first, last,result);

 

✔ remove()

• 연속된 범위에서 특정 값 제거
• 제거된 원소들은 뒤쪽으로 이동하며, 제거된 원소의 새로운 끝 위치를 반환

std::remove(first, last, value);

 

✔ remove_if()

• 연속된 범위에서 특정 조건을 만족하는 원소 제거
• 제거된 원소들은 뒤쪽으로 이동하며, 제거된 원소의 새로운 끝 위치를 반환

std::remove_if(first, last, predicate);

 

✔ remove_copy()

• 연속된 범위에서 특정 값 제거 후 제거된 원소를 새로운 컨테이너에 복사
• 제거된 원소의 새로운 끝 위치를 반환

std::remove_copy(first, last, result, value);

 

✔ remove_copy_if()

• 연속된 범위에서 특정 조건을 만족하는 원소 제거 후 제거된 원소를 새로운 컨테이너에 복사
• 제거된 원소의 새로운 끝 위치를 반환

std::remove_copy_if(first, last, result, predicate);