본문 바로가기
GD's IT Lectures : 기초부터 시리즈/C, C++ 기초부터 ~

[C/C++ 프로그래밍 : 중급] 10. STL 알고리즘

by GDNGY 2023. 6. 9.

Chapter 10. STL 알고리즘

C++ 표준 템플릿 라이브러리 (STL)의 핵심 부분인 알고리즘을 배웁니다. 알고리즘의 개념, 특징, 분류부터 다양한 알고리즘 함수들의 사용법까지 자세하게 다룹니다. 알고리즘 종류에 따라 예제코드와 함께 사용법을 설명하며, 수치, 집합, 힙, 최소/최대 알고리즘 등 다양한 주제를 다룹니다. 각 섹션에서는 STL 알고리즘을 어떻게 활용하는지 이해하도록 하고, 실제 코드에서 어떻게 적용할 수 있는지 보여줍니다.

 

반응형

 

[Chapter 10. STL 알고리즘]

 

10.1. STL 알고리즘 이해하기

10.1.1. STL 알고리즘이란 무엇인가

10.1.2. STL 알고리즘의 특징

10.1.3. STL 알고리즘의 분류

 

10.2. 비 수정 시퀀스 알고리즘

10.2.1. for_each의 사용

10.2.2. find, find_if, find_if_not의 사용

10.2.3. count, count_if의 사용

 

10.3. 수정 시퀀스 알고리즘

10.3.1. copy, copy_if, copy_n의 사용

10.3.2. move의 사용

10.3.3. swap, swap_ranges의 사용

 

10.4. 정렬 알고리즘

10.4.1. sort의 사용

10.4.2. stable_sort의 사용

10.4.3. partial_sort의 사용

10.4.4. nth_element의 사용

 

10.5. 이진 검색 알고리즘

10.5.1. lower_bound, upper_bound의 사용

10.5.2. equal_range의 사용

10.5.3. binary_search의 사용

 

10.6. 수치 알고리즘

10.6.1. iota의 사용

10.6.2. accumulate의 사용

10.6.3. inner_product의 사용

10.6.4. adjacent_difference, partial_sum의 사용

 

10.7. 집합 알고리즘

10.7.1. merge의 사용

10.7.2. includes의 사용

10.7.3. set_union, set_intersection, set_difference, set_symmetric_difference의 사용

 

10.8. 힙 알고리즘

10.8.1. make_heap, push_heap, pop_heap의 사용

10.8.2. sort_heap의 사용

10.8.3. is_heap, is_heap_until의 사용

 

10.9. 최소/최대 알고리즘

10.9.1. min, max의 사용

10.9.2. minmax의 사용

10.9.3. min_element, max_element, minmax_element의 사용

10.1. STL 알고리즘 이해하기

C++ STL 알고리즘은 일련의 공통 작업에 대한 템플릿 함수의 컬렉션입니다. 이 섹션에서는 STL 알고리즘이 무엇인지, 그 특징과 분류에 대해 배우게 됩니다. STL 알고리즘은 여러분의 코드를 더 간결하고 가독성 있게 만들며, 효율적인 프로그래밍을 가능하게 합니다. 이를 통해 우리는 코드의 재사용성을 높이고, 유지보수를 간편하게 할 수 있습니다.

10.1.1. STL 알고리즘이란 무엇인가

STL 알고리즘(Standard Template Library algorithm)은 C++의 핵심 부분으로, 재사용 가능한 컴포넌트의 라이브러리입니다. 이 컴포넌트들은 데이터 구조와 알고리즘을 다루며, 이들은 템플릿을 통해 제공됩니다. STL 알고리즘은 크게 네 가지 구성요소로 이루어져 있습니다: 컨테이너, 알고리즘, 함수자, 반복자입니다.

  • 컨테이너는 객체를 보관하는데 사용되는 클래스를 의미합니다. 예를 들면, vector, list, deque, set, map 등이 있습니다.
  • 알고리즘은 정렬, 검색, 조작 등의 연산을 수행합니다.
  • 함수자는 일반 함수처럼 동작하는 객체를 말합니다. 이는 STL의 알고리즘에서 콜백함수처럼 사용됩니다.
  • 반복자는 컨테이너의 요소에 접근하는 방법을 제공합니다. 이는 포인터와 유사하게 동작하며, STL 컨테이너의 인터페이스 역할을 합니다.

STL 알고리즘의 이런 구성요소들은 함께 작동하여 풍부한 기능을 제공합니다. 이제, 이러한 구성요소들이 어떻게 작동하는지 간단한 예제를 통해 살펴보겠습니다.

 

[예제] 

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

int main() {
    // 컨테이너
    std::vector<int> vec = {1, 2, 3, 4, 5};

    // 알고리즘
    std::reverse(vec.begin(), vec.end());

    // 결과 출력
    for (int num : vec) {
        std::cout << num << " ";
    }
    
    return 0;
}

 

이 예제코드는 C++ STL의 벡터 컨테이너를 사용하여 숫자 배열을 생성하고, STL 알고리즘의 reverse 함수를 사용하여 배열의 순서를 뒤집는 간단한 작업을 수행합니다. 그리고 각 숫자를 출력하여 결과를 확인합니다. 이와 같이 STL 알고리즘은 우리가 작성한 코드를 효율적으로 만들어주며, 코드의 재사용성과 가독성을 높여줍니다. 그리고 코드를 간결하게 만들어줌으로써 프로그래밍이 더 쉽고 즐겁게 느껴질 것입니다.

 

10.1.2. STL 알고리즘의 특징

STL(Standard Template Library) 알고리즘의 특징은 다음과 같습니다.

  • 일반성: STL 알고리즘은 템플릿 기반으로 제작되어 있어서, 다양한 자료형에 대해 동작할 수 있습니다. 이는 다형성(polymorphism)을 템플릿을 통해 구현하여 가능합니다. 즉, 우리는 이 알고리즘들을 우리가 원하는 어떠한 데이터 타입에 대해서도 사용할 수 있습니다.
  • 효율성: STL 알고리즘은 고성능을 목표로 설계되었습니다. 컴파일러는 템플릿을 통해 인라인 함수를 생성하고, 이를 통해 알고리즘의 성능을 최적화합니다.
  • 재사용성: STL은 코드 재사용을 적극적으로 지원합니다. 간단한 코드 조각을 이용해 복잡한 알고리즘을 만들 수 있습니다.
  • 모듈성: STL은 컨테이너, 알고리즘, 반복자 등 다양한 구성요소로 나눠져 있습니다. 이를 통해 다양한 조합을 통해 다양한 기능을 만들 수 있습니다.
  • 성장성: STL은 확장 가능한 구조로 설계되었습니다. 새로운 컨테이너, 알고리즘, 반복자 등을 쉽게 추가할 수 있습니다.

 

[예제]

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

bool is_odd(int i) { return i%2==1; }

int main() {
    std::vector<int> vec = {1, 2, 3, 4, 5, 6, 7, 8, 9};
    int num_odds = std::count_if(vec.begin(), vec.end(), is_odd);

    std::cout << "The number of odd numbers is " << num_odds << std::endl;

    return 0;
}


이 예제에서는 STL의 특징 중 일반성, 효율성, 재사용성을 볼 수 있습니다. 우리는 일반적인 count_if 알고리즘을 사용하여 벡터 안의 홀수의 개수를 세고 있습니다. 여기서 함수 is_odd는 벡터의 각 요소에 대해 적용되며, 이를 통해 우리는 벡터의 요소가 홀수인지 판별할 수 있습니다. 이런 방식으로 STL 알고리즘은 다양한 상황에서 유용하게 쓰일 수 있습니다.

10.1.3. STL 알고리즘의 분류

STL 알고리즘은 크게 비수정 시퀀스 알고리즘, 수정 시퀀스 알고리즘, 정렬 알고리즘, 이진 검색 알고리즘, 수치 알고리즘, 집합 알고리즘, 힙 알고리즘, 최소/최대 알고리즘으로 분류할 수 있습니다. 이 중에서 몇 가지 주요 알고리즘에 대해서 간략하게 설명하고 예제 코드를 제시하겠습니다.

 

비수정 시퀀스 알고리즘: 이런 알고리즘들은 컨테이너의 원소들을 바꾸지 않습니다. count, find, for_each 등이 이에 해당합니다.

 

[예제]

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

int main() {
    std::vector<int> v = {1, 2, 3, 4, 5, 6, 7, 8, 9};

    // count 함수는 주어진 범위 내에서 특정 값을 가진 원소의 개수를 세는 함수입니다.
    int num_fives = std::count(v.begin(), v.end(), 5);
    std::cout << "Number of fives: " << num_fives << std::endl;

    // find 함수는 주어진 범위 내에서 특정 값을 가진 첫 번째 원소의 위치를 반환하는 함수입니다.
    auto it = std::find(v.begin(), v.end(), 5);
    if (it != v.end())
        std::cout << "Found a five!" << std::endl;

    // for_each 함수는 주어진 범위의 모든 원소에 대해 함수를 실행하는 함수입니다.
    std::for_each(v.begin(), v.end(), [](int n) { std::cout << n << ' '; });
    std::cout << std::endl;

    return 0;
}

 

수정 시퀀스 알고리즘: 이 알고리즘들은 컨테이너의 원소들을 실제로 변경합니다. copy, move, fill, replace 등이 이에 해당합니다.

 

[예제]

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

int main() {
    std::vector<int> v = {1, 2, 3, 4, 5, 6, 7, 8, 9};
    std::vector<int> v_copy(v.size());

    // copy 함수는 원본 범위의 원소들을 대상 범위로 복사하는 함수입니다.
    std::copy(v.begin(), v.end(), v_copy.begin());

    for (int n : v_copy)
        std::cout << n << ' ';
    std::cout << std::endl;

    // fill 함수는 주어진 범위의 모든 원소를 특정 값으로 채우는 함수입니다.
    std::fill(v.begin(), v.end(), 0);

    for (int n : v)
        std::cout << n << ' ';
    std::cout << std::endl;

    return 0;
}

 

이처럼 STL 알고리즘은 컨테이너와 원소들에 대한 다양한 연산을 제공하며, 그들의 동작 방식은 대체로 직관적입니다. 더 복잡한 알고리즘들도 있지만, 그들은 대부분 이들 기본 알고리즘들을 조합한 것입니다.

10.2. 비 수정 시퀀스 알고리즘

"비 수정 시퀀스 알고리즘"은 STL 알고리즘의 하위 카테고리로, 이 알고리즘들은 컨테이너의 원소들을 수정하지 않고 순회, 검색, 세기 등의 작업을 수행합니다. 이번 섹션에서는 이러한 알고리즘들 중에서 for_each, find, find_if, find_if_not, count, count_if 등의 사용법에 대해 알아보겠습니다.

10.2.1. for_each의 사용

STL 알고리즘 중 하나인 for_each는 컨테이너의 모든 요소에 함수를 적용하는 역할을 합니다. 이 함수는 세 개의 인자를 받습니다. 시작 반복자, 종료 반복자, 그리고 적용할 함수입니다.

 

이제 for_each의 간단한 사용 예제를 살펴봅시다.

[예제]

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

void print(int i) {
    std::cout << i << ' ';
}

int main() {
    std::vector<int> v = {1, 2, 3, 4, 5};
    std::for_each(v.begin(), v.end(), print);
    return 0;
}

 

이 코드는 print 함수를 벡터 v의 모든 요소에 적용합니다. for_each 함수를 호출하면 벡터의 모든 요소가 출력되어 결과는 "1 2 3 4 5"가 됩니다.

 

이처럼 for_each 함수는 컨테이너의 모든 요소에 일괄적으로 연산을 적용할 때 유용합니다. 이는 C++에서 '함수형 프로그래밍'이라는 개념과 연결되는데, 이는 함수를 일급 시민으로 취급하여 함수를 변수로 사용하고, 인수로 전달하거나, 결과로 반환하는 것을 의미합니다.

 

그런데, C++11 이후로는 람다 함수라는 새로운 기능이 도입되어, 함수를 별도로 정의하지 않고도 바로 for_each 함수에 전달할 수 있게 되었습니다.

 

[예제]

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

int main() {
    std::vector<int> v = {1, 2, 3, 4, 5};
    std::for_each(v.begin(), v.end(), [](int i){
        std::cout << i << ' ';
    });
    return 0;
}

 

이 코드는 앞서 설명한 코드와 동일한 동작을 수행하지만, 별도의 print 함수를 정의하지 않고 람다 함수를 직접 for_each 함수에 전달합니다.

 

이처럼, STL 알고리즘의 for_each 함수는 함수를 인자로 받아서 컨테이너의 각 요소에 적용하는 유용한 도구입니다. 간단하면서도 강력한 이 도구를 잘 활용하여 더 효과적인 코드를 작성하시길 바랍니다.

 

10.2.2. find, find_if, find_if_not의 사용

STL의 비수정 시퀀스 알고리즘에는 find, find_if, find_if_not 등이 있습니다. 이들은 컨테이너 안에서 특정 조건에 맞는 요소를 찾는 데 사용됩니다.

 

먼저 find에 대해 알아봅시다. find는 컨테이너의 특정 범위에서 주어진 값과 같은 첫 번째 요소를 찾아 그 위치를 반환합니다. 만약 찾는 값이 없다면 종료 반복자를 반환합니다.

 

다음은 find 함수를 사용한 예제입니다.

 

[예제]

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

int main() {
    std::vector<int> v = {1, 2, 3, 4, 5};
    auto it = std::find(v.begin(), v.end(), 3);
    if (it != v.end()) {
        std::cout << "Found: " << *it << '\n';
    } else {
        std::cout << "Not found.\n";
    }
    return 0;
}

 

이 코드에서는 벡터 v에서 값이 3인 요소를 찾습니다. 찾은 요소의 위치를 반복자 it에 저장하고, 이 반복자를 사용해 찾은 요소를 출력합니다. 만약 값을 찾지 못하면 "Not found"를 출력합니다.

 

그다음은 find_if 함수입니다. find_if 함수는 find 함수와 비슷하지만, 특정 조건을 만족하는 첫 번째 요소를 찾습니다. 조건은 함수나 함수 객체를 인자로 받아서 결정합니다.

 

다음은 find_if 함수를 사용한 예제입니다.

 

[예제]

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

bool is_even(int i) {
    return i % 2 == 0;
}

int main() {
    std::vector<int> v = {1, 2, 3, 4, 5};
    auto it = std::find_if(v.begin(), v.end(), is_even);
    if (it != v.end()) {
        std::cout << "Found even number: " << *it << '\n';
    } else {
        std::cout << "Not found.\n";
    }
    return 0;
}

 

이 코드는 is_even 함수를 조건으로 사용해 벡터에서 첫 번째로 발견되는 짝수를 찾습니다.

 

마지막으로 find_if_not 함수는 find_if와 반대로 주어진 조건을 만족하지 않는 첫 번째 요소를 찾습니다.

 

다음은 find_if_not 함수를 사용한 예제입니다.

[예제]

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

bool is_odd(int i) {
    return i % 2 != 0;
}

int main() {
    std::vector<int> v = {1, 2, 3, 4, 5};
    auto it = std::find_if_not(v.begin(), v.end(), is_odd);
    if (it != v.end()) {
        std::cout << "Found not odd number: " << *it << '\n';
    } else {
        std::cout << "Not found.\n";
    }
    return 0;
}

 

이 코드는 is_odd 함수를 조건으로 사용해 벡터에서 첫 번째로 발견되는 홀수가 아닌 수, 즉 짝수를 찾습니다.

 

이처럼 find, find_if, find_if_not는 컨테이너에서 조건에 맞는 요소를 찾는 유용한 알고리즘입니다. 이를 통해 다양한 검색 작업을 효율적으로 수행할 수 있습니다.

 

10.2.3. count, count_if의 사용

STL에서 제공하는 비수정 시퀀스 알고리즘에는 count와 count_if가 포함되며, 이들은 컨테이너의 특정 범위에서 주어진 값 또는 조건에 해당하는 요소의 개수를 찾는 데 사용됩니다.

 

count 알고리즘은 컨테이너의 특정 범위에서 주어진 값과 일치하는 요소의 개수를 찾습니다. 이 함수는 찾고자 하는 값을 인자로 받아서 그 개수를 반환합니다.

 

다음은 count 함수를 사용한 예제입니다:

[예제]

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

int main() {
    std::vector<int> v = {1, 2, 3, 2, 1, 2, 3, 2, 1};
    int count = std::count(v.begin(), v.end(), 2);
    std::cout << "Number of 2s: " << count << '\n';
    return 0;
}

 

이 코드는 벡터 v에서 2의 개수를 세어서 출력합니다.

 

count_if 함수는 조건을 만족하는 요소의 개수를 세는 데 사용됩니다. 이 함수는 함수 또는 함수 객체를 인자로 받아서 그 조건에 맞는 요소의 개수를 반환합니다.

 

다음은 count_if 함수를 사용한 예제입니다:

[예제]

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

bool is_even(int i) {
    return i % 2 == 0;
}

int main() {
    std::vector<int> v = {1, 2, 3, 4, 5, 6, 7, 8, 9};
    int count = std::count_if(v.begin(), v.end(), is_even);
    std::cout << "Number of even numbers: " << count << '\n';
    return 0;
}

 

이 코드는 is_even 함수를 조건으로 사용해 벡터에서 짝수의 개수를 세어서 출력합니다.

 

count와 count_if는 컨테이너에서 특정 값 또는 조건에 해당하는 요소의 개수를 쉽게 찾을 수 있도록 도와주는 유용한 함수들입니다. 이들을 이용하면 반복문을 직접 작성하여 요소를 세는 수고를 덜 수 있습니다. 이런 방식으로 코드의 가독성을 향상하고 프로그램의 효율성을 높일 수 있습니다.

10.3. 수정 시퀀스 알고리즘

"수정 시퀀스 알고리즘"에서는 데이터 구조의 원소들을 변경하는 STL 알고리즘이 주제입니다. 여기서는 'copy', 'move', 'swap'과 같은 기본적인 알고리즘을 중점으로 다룹니다. 이러한 알고리즘은 데이터의 조작과 이동을 용이하게 만들어, 더 효율적인 프로그래밍이 가능하도록 합니다. 이 섹션을 통해 개발자는 데이터를 조작하는 방법의 다양성을 이해하고 그 효과를 체험할 수 있습니다.

10.3.1. copy, copy_if, copy_n의 사용

"copy, copy_if, copy_n의 사용"은 STL(Standard Template Library)의 수정 시퀀스 알고리즘 중 하나입니다. 여기서는 STL의 copy, copy_if, copy_n 알고리즘을 살펴보고 이를 어떻게 사용하는지 학습합니다.

 

먼저, copy 알고리즘은 범위의 원소들을 다른 위치로 복사합니다. 아래는 copy를 사용하는 C++ 코드 예시입니다:

 

[예제]

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

int main() {
    std::vector<int> src{1, 2, 3, 4, 5};
    std::vector<int> dest(src.size());

    std::copy(src.begin(), src.end(), dest.begin());

    for(int i : dest) {
        std::cout << i << " ";
    }
    return 0;
}

 

위 코드는 src 벡터의 모든 원소를 dest 벡터로 복사합니다. 결과적으로 dest 벡터는 src 벡터와 같은 원소를 가지게 됩니다.

 

그 다음은 copy_if 알고리즘입니다. 이 함수는 첫 번째 인수와 두 번째 인수로 지정된 범위의 원소 중 세 번째 인수로 주어진 조건을 만족하는 원소만을 복사합니다. 다음은 copy_if를 사용하는 C++ 코드 예시입니다:

 

[예제]

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

int main() {
    std::vector<int> src{1, 2, 3, 4, 5};
    std::vector<int> dest;

    std::copy_if(src.begin(), src.end(), std::back_inserter(dest), [](int i){ return i%2 == 0; });

    for(int i : dest) {
        std::cout << i << " ";
    }
    return 0;
}

 

위 코드는 src 벡터에서 짝수 원소만 dest 벡터로 복사합니다.

 

마지막으로 copy_n은 첫 번째 인수에서 시작하는 원소를 두 번째 인수로 지정된 수만큼 복사합니다. 이 함수는 주어진 개수만큼의 원소를 복사하므로 원소 수를 제한할 수 있습니다.

 

이 세 가지 알고리즘 모두 데이터를 조작하거나 이동하는 데 있어 매우 유용합니다. 특히 컨테이너 간에 데이터를 손쉽게 이동하거나 특정 조건에 따라 데이터를 필터링할 때 유용합니다.

 

이 모든 것을 통해 우리는 데이터를 보다 효율적으로 처리하고, 복잡한 작업을 단순화하며, 코드의 가독성을 향상할 수 있음을 알 수 있습니다. 따라서 STL 알고리즘은 C++ 프로그래밍에 있어 필수적인 요소입니다.

 

10.3.2. move의 사용

"move의 사용"은 STL(Standard Template Library)의 수정 시퀀스 알고리즘 중 하나입니다. 여기서는 STL의 move 알고리즘에 대해 알아보고, 이를 어떻게 사용하는지 학습합니다.

 

std::move는 원본 객체로부터 값을 '이동'하는 방식을 제공하는 함수입니다. 이를 이해하기 위해서는 C++의 rvalue 참조와 move semantics에 대한 이해가 필요합니다. 기본적으로, move는 복사 대신 이동을 사용하여 객체의 값을 다른 객체로 옮깁니다. 이는 특히 큰 데이터 구조체를 처리할 때 효율적인 방법입니다.

 

아래는 std::move의 사용 예시입니다:

 

[예제]

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

int main() {
    std::vector<int> src{1, 2, 3, 4, 5};
    std::vector<int> dest(src.size());

    std::move(src.begin(), src.end(), dest.begin());

    for(int i : dest) {
        std::cout << i << " ";
    }
    return 0;
}

 

위 코드에서 std::move는 src 벡터의 원소를 dest 벡터로 이동시킵니다. 이는 src 벡터의 원소를 dest 벡터로 '복사'하는 것과 달리, 실제로는 원본 객체(src)에서 값이 '이동'되어 목적지 객체(dest)로 전달됩니다. 따라서 이동이 완료된 후에는 원본 객체(src)의 상태를 사용할 수 없게 됩니다.

 

이동 시맨틱스는 C++11 이후로 추가되었으며, 불필요한 복사 작업을 줄여 성능을 개선하는 데 매우 중요한 기능입니다. 큰 데이터 구조체를 이동할 때 특히 중요한데, 이는 복사하는 것보다 훨씬 효율적이기 때문입니다. 따라서 std::move는 C++ 프로그래밍에서 빈번하게 사용되는 중요한 기능 중 하나입니다.

 

여기서는 std::move의 기본적인 사용법을 소개했지만, 이 함수는 다양한 방식으로 사용될 수 있습니다. 예를 들어, 함수의 반환값을 이동시키거나, 자신의 데이터를 다른 객체로 이동시킬 때 std::move를 사용할 수 있습니다.

 

이처럼 STL 알고리즘은 C++ 프로그래밍에서 코드를 효율적으로 작성하고 복잡한 작업을 단순화하는 데 도움이 됩니다. std::move와 같은 함수는 특히 성능을 개선하는 데 중요한 역할을 하므로, 잘 알아두고 적절히 사용하는 것이 중요합니다.

 

10.3.3. swap, swap_ranges의 사용

"swap, swap_ranges의 사용"에서는 STL(Standard Template Library)의 수정 시퀀스 알고리즘 중 하나인 swap과 swap_ranges에 대해 배웁니다. 이 두 알고리즘은 변수나 컨테이너 범위의 값을 교환하는 데 사용됩니다. 

 

std::swap은 두 개의 변수의 값을 교환하는 데 사용됩니다. 이 함수는 간단히 말해서 두 변수를 매개변수로 받아 그들 사이의 값을 교환합니다.

 

아래에 std::swap의 사용 예시를 들어보겠습니다:

 

[예제]

#include <algorithm>
#include <iostream>

int main() {
    int a = 5;
    int b = 10;

    std::swap(a, b);

    std::cout << "a: " << a << ", b: " << b << std::endl;
    return 0;
}

 

위 코드에서 std::swap 함수를 사용해 a와 b의 값을 교환했습니다. 출력 결과는 "a: 10, b: 5"가 될 것입니다.

 

다음으로, std::swap_ranges는 두 시퀀스의 요소를 교환하는 데 사용됩니다. 이 함수는 두 범위를 매개변수로 받아 두 범위의 요소를 교환합니다.

 

아래에 std::swap_ranges의 사용 예시를 들어보겠습니다:

 

[예제]

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

int main() {
    std::vector<int> v1 = {1, 2, 3};
    std::vector<int> v2 = {4, 5, 6};

    std::swap_ranges(v1.begin(), v1.end(), v2.begin());

    for(int i : v1) {
        std::cout << i << " ";
    }

    std::cout << std::endl;

    for(int i : v2) {
        std::cout << i << " ";
    }

    return 0;
}

 

위 코드에서 std::swap_ranges 함수를 사용해 v1과 v2 벡터의 값을 교환했습니다. 출력 결과는 "4 5 6"과 "1 2 3"이 될 것입니다.

 

이처럼 std::swap과 std::swap_ranges는 STL 알고리즘의 수정 시퀀스 알고리즘 중에서 특히 값의 교환을 필요로 할 때 유용하게 사용됩니다. 이 두 함수를 잘 이해하고 사용하면 더 효율적이고 깔끔한 코드를 작성할 수 있습니다.

10.4. 정렬 알고리즘

C++의 STL(Standard Template Library)은 정렬 알고리즘을 통해 개발자가 자료의 순서를 조정할 수 있도록 도와줍니다. 이에는 sort, partial_sort, nth_element, inplace_merge 등 다양한 함수가 포함됩니다. 이러한 정렬 알고리즘은 강력하고 유연한 도구로서, 컨테이너의 요소들을 원하는 순서대로 배치하거나 특정 기준에 따라 요소를 정렬하는 데 사용됩니다. 알고리즘 선택은 정렬이 필요한 범위, 정렬 기준 등 요구사항에 따라 달라집니다.

10.4.1. sort의 사용

STL에는 훌륭한 정렬 함수인 sort()가 포함되어 있습니다. 이 함수는 컨테이너의 요소들을 오름차순으로 정렬하는데 사용됩니다. sort()는 템플릿 함수이므로, 서로 다른 유형의 컨테이너에 사용할 수 있습니다.

 

[예제]

#include <algorithm>  // STL 알고리즘 헤더
#include <vector>
#include <iostream>

int main() {
    std::vector<int> v = {4, 2, 5, 3, 5, 8, 3};
    std::sort(v.begin(), v.end());

    for(auto i : v)
        std::cout << i << ' ';
    return 0;
}

 

위의 코드를 실행하면 출력 결과는 2 3 3 4 5 5 8로, vector의 요소들이 오름차순으로 정렬된 것을 확인할 수 있습니다.

 

sort() 함수는 첫 번째 매개변수로 시작 인덱스, 두 번째 매개변수로 끝 인덱스를 받습니다. 이 함수는 이 범위 내의 요소를 정렬합니다.

 

[예제]

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

int main() {
    std::vector<int> v = {4, 2, 5, 3, 5, 8, 3};
    std::sort(v.begin(), v.begin()+3);

    for(auto i : v)
        std::cout << i << ' ';
    return 0;
}

 

이번에는 v.begin()+3을 sort()의 두 번째 매개변수로 전달했습니다. 따라서 이 코드는 벡터의 처음 세 개의 요소만 정렬하며 출력 결과는 2 4 5 3 5 8 3입니다.

 

또한, sort() 함수는 세 번째 매개변수로 사용자 정의 비교 함수를 받을 수 있습니다. 이를 이용하면 요소를 내림차순으로 정렬하거나 복잡한 정렬 기준을 설정할 수 있습니다.

 

[예제]

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

bool desc(int a, int b) {
    return a > b;
}

int main() {
    std::vector<int> v = {4, 2, 5, 3, 5, 8, 3};
    std::sort(v.begin(), v.end(), desc);

    for(auto i : v)
        std::cout << i << ' ';
    return 0;
}

 

이 코드는 desc()라는 사용자 정의 비교 함수를 사용하여 벡터의 요소를 내림차순으로 정렬합니다. 결과는 8 5 5 4 3 3 2입니다.

 

sort()는 정렬에 퀵정렬을 기반으로 한 알고리즘을 사용하며, 시간 복잡도는 일반적으로 O(n log n)입니다. 그러나 이미 정렬된 데이터나 거의 정렬된 데이터에 대해서는 효율적으로 동작하지 않을 수 있습니다. 이 경우 stable_sort()를 사용하는 것이 좋습니다.

 

10.4.2. stable_sort의 사용

STL에서 제공하는 stable_sort() 함수는 정렬 시 같은 값의 원소들이 원래의 순서를 유지하며 정렬되는 것을 보장하는 알고리즘입니다. 이는 '정렬의 안정성'을 보장한다는 개념에서 이름이 유래되었습니다. 이러한 특성은 데이터가 이미 어느 정도 정렬된 상태이거나, 데이터의 상대적인 순서가 중요할 때 유용합니다.

 

다음은 stable_sort() 함수의 사용 예시입니다.

 

[예제]

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

int main() {
    std::vector<int> v = {4, 2, 5, 3, 5, 8, 3};
    std::stable_sort(v.begin(), v.end());

    for(auto i : v)
        std::cout << i << ' ';
    return 0;
}

 

이 코드는 sort()를 사용했을 때와 동일하게 벡터의 요소들을 오름차순으로 정렬합니다. 하지만, 동일한 값의 원소들 사이의 상대적인 순서는 변하지 않습니다.

 

또한, stable_sort() 함수 역시 사용자 정의 비교 함수를 세 번째 인자로 받을 수 있습니다. 이를 통해 복잡한 정렬 기준을 설정하거나 원소를 내림차순으로 정렬하는 것도 가능합니다.

 

[예제]

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

bool desc(int a, int b) {
    return a > b;
}

int main() {
    std::vector<int> v = {4, 2, 5, 3, 5, 8, 3};
    std::stable_sort(v.begin(), v.end(), desc);

    for(auto i : v)
        std::cout << i << ' ';
    return 0;
}

 

위의 코드는 벡터의 요소들을 내림차순으로 정렬하되, 동일한 값의 원소들은 원래의 순서를 유지합니다.

 

이처럼 stable_sort()는 정렬의 안정성이 필요한 경우, 또는 데이터가 이미 어느 정도 정렬되어 있는 경우에 유용하게 사용할 수 있습니다. 시간 복잡도는 sort()와 같이 일반적으로 O(n log n)입니다.

 

10.4.3. partial_sort의 사용

partial_sort() 함수는 STL에서 제공하는 정렬 알고리즘 중 하나입니다. 이 함수의 특징은 이름에서도 알 수 있듯이 전체 시퀀스를 정렬하는 것이 아니라, 시퀀스의 일부를 정렬한다는 점입니다. 이 함수는 주어진 범위 내에서 가장 작은 n개의 원소를 정렬합니다.

 

다음은 partial_sort() 함수의 사용 예시입니다.

 

[예제]

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

int main() {
    std::vector<int> v = {5, 8, 2, 1, 6, 3, 7};
    std::partial_sort(v.begin(), v.begin() + 3, v.end());

    for(auto i : v)
        std::cout << i << ' ';
    return 0;
}

 

이 코드는 벡터의 첫 세 개 원소를 오름차순으로 정렬합니다. 첫 세 개의 원소 외의 원소들은 원래 순서를 유지합니다.

 

또한 partial_sort() 함수는 사용자 정의 비교 함수를 네 번째 인자로 받을 수 있습니다. 이를 통해 원소를 내림차순으로 정렬하거나 복잡한 정렬 기준을 설정할 수 있습니다.

 

[예제]

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

bool desc(int a, int b) {
    return a > b;
}

int main() {
    std::vector<int> v = {5, 8, 2, 1, 6, 3, 7};
    std::partial_sort(v.begin(), v.begin() + 3, v.end(), desc);

    for(auto i : v)
        std::cout << i << ' ';
    return 0;
}

 

위의 코드는 벡터의 첫 세 개 원소를 내림차순으로 정렬하고, 나머지 원소들은 원래 순서를 유지합니다.

 

partial_sort()는 상황에 따라 매우 유용할 수 있습니다. 특히, 전체 데이터에서 가장 크거나 작은 n개의 원소만이 필요할 때 이 함수를 사용하면 효율적입니다. 이 함수의 시간 복잡도는 O(n log m)입니다(n은 벡터의 전체 크기, m은 정렬하고자 하는 원소의 개수).

 

partial_sort()는 그 이름에서 알 수 있듯이, 특정 범위의 원소만 정렬하는 함수입니다. 이 함수는 또한 '최소 힙' 데이터 구조를 내부적으로 사용하므로, 정렬 범위 밖의 원소들도 일정한 순서를 유지합니다. 다시 말해, 이 함수는 주어진 범위 외의 원소들은 정렬되지 않지만, 그 순서는 무작위가 아닙니다. partial_sort() 후에는 범위 내 원소들이 다른 원소들보다 항상 작거나 같다는 것을 보장할 수 있습니다.

 

다음은 partial_sort()가 범위 외의 원소에 어떤 영향을 미치는지 보여주는 예제입니다:

 

[예제]

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

int main() {
    std::vector<int> v = {5, 8, 2, 1, 6, 3, 7};
    std::partial_sort(v.begin(), v.begin() + 3, v.end());

    for(auto i : v)
        std::cout << i << ' ';
    return 0;
}

 

이 코드를 실행하면 출력 결과는 '1 2 3 5 8 6 7'이 됩니다. 첫 세 개의 원소는 정렬되지만, 나머지 원소들은 원래 순서를 유지하진 않습니다. 그러나 그들은 첫 세 개의 원소보다 크거나 같다는 것을 알 수 있습니다.

 

이러한 특성은 partial_sort()가 특정 문제에 유용하게 사용될 수 있음을 의미합니다. 예를 들어, 원소 중 일부만 정렬하고 싶지만 그 외의 원소도 어느 정도 정렬된 상태를 유지하고 싶을 때, 이 함수는 매우 효과적입니다. 이러한 경우를 위해 STL은 partial_sort()를 제공합니다.

 

10.4.4. nth_element의 사용

'nth_element()'는 STL에서 제공하는 또 다른 유용한 정렬 함수입니다. 이 함수는 주어진 범위 내에서 n번째 위치의 원소가 있어야 할 위치에 놓고, 그 원소보다 작은 원소들은 모두 그 원소의 왼쪽에, 큰 원소들은 오른쪽에 위치시킵니다. 즉, nth_element()를 사용하면 배열이 완전히 정렬되지 않더라도 n번째 원소가 있어야 할 위치에 정확히 놓일 수 있습니다.

 

예제 코드를 보겠습니다.

 

[예제]

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

int main() {
    std::vector<int> v = {5, 8, 2, 1, 6, 3, 7};
    std::nth_element(v.begin(), v.begin() + 3, v.end());

    for(auto i : v)
        std::cout << i << ' ';
    return 0;
}

 

이 코드를 실행하면 출력 결과는 '2 1 3 5 8 6 7' 이 됩니다. nth_element(v.begin(), v.begin() + 3, v.end()) 라인에서, 벡터 v의 첫 번째 원소부터 시작하여 세 번째 원소 (인덱스 3) 이 있어야 할 위치에 정확히 놓아줍니다. 그래서 그 위치 (5) 앞에는 5보다 작은 원소들이, 그 위치 뒤에는 5보다 큰 원소들이 오게 됩니다.

 

이렇게 nth_element()를 이용하면, 배열의 특정 위치에 원소를 정확히 위치시키고 그 원소를 기준으로 나머지 원소들을 빠르게 분류할 수 있습니다. 이는 빠른 선택 알고리즘의 일종으로 볼 수 있습니다. 만약 배열 내에서 k번째로 작은 (또는 큰) 원소를 찾고 싶을 때, 배열 전체를 정렬하는 것보다 nth_element()를 사용하는 것이 효율적일 수 있습니다.

 

'nth_element()' 함수는 QuickSelect 알고리즘의 개념을 기반으로 하며, 이 함수의 시간 복잡도는 평균적으로 O(N)입니다. 이는 특정 상황에서 전체 데이터를 정렬하는 것보다 훨씬 빠르다는 것을 의미합니다.

 

하지만 이 함수는 안정적인 정렬 알고리즘(stable sort)이 아니라는 점에 유의해야 합니다. 즉, 동일한 값을 가진 원소들 사이의 상대적 순서가 유지되지 않을 수 있습니다.

 

더욱이, nth_element()는 n번째 원소를 기준으로 좌우를 분할하는 데에만 초점을 맞추고, 그 외의 원소들에 대해서는 정렬 상태를 보장하지 않습니다. 따라서 nth_element()를 사용한 후에는 특정 원소의 정확한 위치만 알 수 있을 뿐, 나머지 원소들의 순서는 예측할 수 없습니다.

 

'nth_element()'의 이런 특징은 때로는 문제 해결에 있어 매우 유용할 수 있습니다. 예를 들어, 상위 k개의 원소만 찾아야 하는 문제나, 중앙값을 찾아야 하는 문제 등에서는 전체를 정렬하는 것보다 nth_element()를 사용하는 것이 더 효율적일 수 있습니다.

 

이처럼 STL의 정렬 관련 함수들은 각기 다른 특징과 사용 케이스를 가지고 있으므로, 문제의 요구사항에 따라 적절한 함수를 선택하는 것이 중요합니다.

10.5. 이진 검색 알고리즘

'이진 검색 알고리즘'은 정렬된 시퀀스에서 특정 값을 효율적으로 찾는 방법을 제공합니다. 이진 검색은 가운데 항목을 확인하고, 찾으려는 값이 더 작거나 큰 경우 해당 절반을 검색하는 방식으로 작동합니다. STL은 이 알고리즘을 사용하는 몇 가지 함수를 제공합니다: lower_bound, upper_bound, equal_range와 binary_search가 있습니다. 이 모든 함수들은 빠른 검색을 위해 정렬된 컨테이너를 필요로 합니다.

10.5.1. lower_bound, upper_bound의 사용

이진 검색 알고리즘은 정렬된 컨테이너 내에서 값을 효과적으로 찾는데 사용되는데, lower_bound와 upper_bound는 이 중 중요한 두 가지 함수입니다.

 

lower_bound

lower_bound는 주어진 값 이상의 첫 번째 원소를 찾는데 사용됩니다. 이 함수는 정렬된 컨테이너에서 가장 먼저 나오는 해당 값이나 그보다 큰 값의 위치를 반환합니다. 만약 그러한 원소가 없다면, 이 함수는 컨테이너 끝을 가리키는 반복자를 반환합니다.

 

C++ 코드 예제는 다음과 같습니다.

 

[예제]

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

int main() {
    std::vector<int> v = {1, 2, 4, 4, 5, 6};
    auto lb = std::lower_bound(v.begin(), v.end(), 4);
    std::cout << "The lower bound of 4 is at position: " << (lb - v.begin()) << '\n';
    return 0;
}

 

이 예제에서, lower_bound는 값 4의 첫 번째 위치를 찾습니다. 결과적으로 출력은 "The lower bound of 4 is at position: 2"가 될 것입니다.

 

upper_bound

반면에, upper_bound는 주어진 값보다 큰 첫 번째 원소를 찾습니다. 즉, lower_bound가 주어진 값의 시작 위치를 찾는 것이라면, upper_bound는 그 끝 위치를 찾습니다.

 

C++ 코드 예제는 다음과 같습니다.

 

[예제]

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

int main() {
    std::vector<int> v = {1, 2, 4, 4, 5, 6};
    auto ub = std::upper_bound(v.begin(), v.end(), 4);
    std::cout << "The upper bound of 4 is at position: " << (ub - v.begin()) << '\n';
    return 0;
}

 

이 예제에서, upper_bound는 값 4를 초과하는 첫 번째 위치를 찾습니다. 결과적으로 출력은 "The upper bound of 4 is at position: 4"가 될 것입니다.

 

이 두 함수는 모두 로그 시간복잡도를 가지므로, 대용량 데이터에도 효율적입니다. 이는 이진 검색 알고리즘의 장점이며, 이를 통해 STL은 대용량 데이터를 다루는 데 매우 유용합니다.

 

10.5.2. equal_range의 사용

이번 섹션에서는 equal_range 함수에 대해 설명하겠습니다. 이 함수는 STL(Standard Template Library)에서 이진 검색 알고리즘의 일부로 제공되며, lower_bound와 upper_bound의 결합된 버전이라고 할 수 있습니다.

 

equal_range

equal_range 함수는 주어진 값과 일치하는 연속된 요소의 범위를 반환합니다. 이 함수는 pair 형태의 반복자를 반환하며, pair의 첫 번째 요소는 lower_bound를, 두 번째 요소는 upper_bound를 가리킵니다.

 

C++ 코드 예제를 보겠습니다.

 

[예제]

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

int main() {
    std::vector<int> v = {1, 2, 4, 4, 5, 6};
    auto er = std::equal_range(v.begin(), v.end(), 4);
    std::cout << "The equal range of 4 starts at position: " << (er.first - v.begin()) << '\n';
    std::cout << "The equal range of 4 ends at position: " << (er.second - v.begin()) << '\n';
    return 0;
}

 

이 예제에서 equal_range는 값 4의 시작과 끝 위치를 찾습니다. 결과적으로 출력은 "The equal range of 4 starts at position: 2"와 "The equal range of 4 ends at position: 4"가 될 것입니다.

 

C언어는 STL을 지원하지 않으므로, equal_range와 같은 함수를 직접 구현해야 합니다. 이는 상당히 복잡할 수 있으며, 일반적으로 C++의 STL이 제공하는 이러한 강력한 기능 때문에, 고급 알고리즘을 처리할 때는 C++를 선호하는 경향이 있습니다.

 

equal_range는 이진 검색 알고리즘이므로 실행 시간은 로그 시간 복잡도를 갖습니다. 따라서 이 함수는 대용량 데이터에서도 빠르게 원하는 요소의 범위를 찾는 데 매우 효과적입니다.

 

이처럼 equal_range는 특정 값의 시작과 끝 위치를 한 번에 찾고 싶을 때 매우 유용한 함수입니다. 이 함수를 이용하면 lower_bound와 upper_bound를 따로 호출하지 않아도 되므로 코드를 더 간결하고 효과적으로 작성할 수 있습니다. 이는 코드의 가독성을 높이고 버그를 줄이는 데 도움이 됩니다.

 

10.5.3. binary_search의 사용

이번 섹션에서는 STL의 이진 검색 알고리즘 중 하나인 binary_search에 대해 알아보겠습니다.

 

binary_search

binary_search는 정렬된 컨테이너에서 특정 원소가 존재하는지 판별할 때 사용하는 함수입니다. 이 함수는 bool 값을 반환하며, 찾는 원소가 존재하면 true를, 그렇지 않으면 false를 반환합니다.

 

C++에서의 예제 코드를 통해 설명하겠습니다.

 

[예제]

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

int main() {
    std::vector<int> v = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
    bool found = std::binary_search(v.begin(), v.end(), 5);
    std::cout << (found ? "Found" : "Not Found") << std::endl;
    return 0;
}

 

위의 코드는 1부터 10까지의 숫자가 저장된 벡터에서 5라는 숫자가 존재하는지 확인하는 예제입니다. binary_search 함수가 true를 반환하면 "Found", false를 반환하면 "Not Found"를 출력합니다.

 

이 함수는 이진 검색 알고리즘을 사용하기 때문에, 컨테이너는 반드시 사전에 정렬되어 있어야 합니다. 또한, 이진 검색 알고리즘의 시간 복잡도는 O(log n)이므로 대량의 데이터에서도 효과적으로 사용할 수 있습니다.

 

C언어는 STL을 지원하지 않기 때문에, 이진 검색을 위한 함수를 직접 구현해야 합니다. 하지만 이진 검색은 일반적인 선형 검색에 비해 복잡하므로, 처음부터 구현하기에는 어려울 수 있습니다. 따라서 대부분의 경우 C++의 STL을 활용하는 것이 좋습니다.

 

이처럼, binary_search 함수는 정렬된 컨테이너에서 특정 원소의 존재 여부를 빠르게 확인할 수 있어 매우 유용합니다. 이진 검색 알고리즘에 대한 이해와 함께 이 함수를 적절히 활용하면, 프로그램의 성능을 크게 향상할 수 있습니다.

10.6. 수치 알고리즘

'수치 알고리즘'은 C++의 STL에서 제공하는 다양한 수치 알고리즘들을 다룹니다. 이러한 알고리즘들은 수학적 연산을 쉽고 효율적으로 수행하는 데 도움이 됩니다. 이 섹션에서는 accumulate, inner_product, partial_sum, adjacent_difference와 같은 알고리즘들을 다룰 것입니다. 각각은 다양한 연산에 사용될 수 있으며, 개발자의 요구에 맞게 커스터마이즈 할 수 있습니다. 이러한 함수들은 알고리즘을 보다 직관적으로 표현하고 코드의 가독성을 향상합니다.

10.6.1. iota의 사용

'iota의 사용'에서는 STL의 중요한 알고리즘 중 하나인 iota에 대해 알아보겠습니다.

 

'iota'는 주어진 범위에 연속된 값을 채우는 함수입니다. 첫 번째 인자로 시작 위치를, 두 번째 인자로 끝 위치를, 세 번째 인자로 시작 값(기본값은 0)을 받습니다. 이 함수는 주어진 범위의 각 원소에 대해 지정된 값에서 시작하여 1씩 증가하는 값을 채웁니다.

 

C++의 코드 예제를 통해 iota의 사용법을 살펴보겠습니다.

 

[예제]

#include <iostream>
#include <vector>
#include <numeric> // iota를 사용하기 위해 필요

int main() {
    std::vector<int> v(10);

    std::iota(v.begin(), v.end(), 1); // 벡터 v를 1부터 시작하는 연속된 숫자로 채움

    for(auto i : v)
        std::cout << i << ' ';
    return 0;
}

 

이 예제 코드는 크기가 10인 벡터 v에 1부터 시작하여 1씩 증가하는 숫자를 채웁니다. 따라서 출력은 "1 2 3 4 5 6 7 8 9 10"이 될 것입니다.

 

'iota'는 STL에서 제공하는 다른 수치 알고리즘과 함께 사용되어 다양한 효과를 낼 수 있습니다. 예를 들어, 'iota'로 초기화한 벡터를 'accumulate' 알고리즘과 함께 사용하면 원소들의 합을 구할 수 있습니다.

 

[예제]

std::cout << "Sum: " << std::accumulate(v.begin(), v.end(), 0) << std::endl;


이 코드는 'iota'로 생성한 연속된 숫자들의 합을 계산하여 출력합니다.

 

이처럼 iota는 초기 연속된 값들을 설정하거나 특정 패턴을 만드는데 유용하게 사용될 수 있습니다. 이것은 반복자와 함께 사용되어 컨테이너의 특정 범위를 채울 수 있게 합니다. 이 알고리즘은 프로그래밍 문제를 해결하는 데 있어서 매우 중요한 도구가 될 수 있습니다.


10.6.2. accumulate의 사용

'accumulate의 사용'에서는 STL의 중요한 수치 알고리즘 중 하나인 accumulate에 대해 알아보겠습니다.

 

accumulate는 컨테이너에 있는 모든 원소들의 합을 계산하는 함수입니다. 첫 번째 인자로 시작 위치를, 두 번째 인자로 끝 위치를, 그리고 세 번째 인자로 초기 값(기본값은 0)을 받습니다. 이 함수는 주어진 범위의 모든 원소를 합한 결과를 반환합니다.

 

아래는 C++를 이용한 accumulate의 사용 예제입니다:

 

[예제]

#include <iostream>
#include <vector>
#include <numeric> // accumulate를 사용하기 위해 필요

int main() {
    std::vector<int> v(10, 2); // 10개의 원소를 모두 2로 초기화

    int sum = std::accumulate(v.begin(), v.end(), 0); // 벡터 v의 모든 원소의 합 계산

    std::cout << "Sum: " << sum;
    return 0;
}

 

이 예제 코드는 크기가 10인 벡터 v를 2로 초기화하고, accumulate를 이용해 모든 원소의 합을 계산합니다. 따라서 "Sum: 20"이라는 결과를 출력하게 됩니다.

 

더 나아가, accumulate는 더하기 외에도 다른 연산을 적용할 수 있습니다. 그 방법은 네 번째 인자로 이항 연산자(binary operator)를 전달하는 것입니다. 이는 주어진 범위의 모든 원소에 대해 연산을 적용하고, 그 결과를 반환합니다.

 

[예제]

int product = std::accumulate(v.begin(), v.end(), 1, std::multiplies<int>()); // 벡터 v의 모든 원소의 곱 계산

 

이 코드는 v의 모든 원소를 곱한 결과를 계산합니다. std::multiplies<int>는 이항 연산자로, 두 개의 int형 인자를 곱하는 함수입니다.

 

이처럼 accumulate 함수는 주어진 범위의 원소들에 대해 임의의 이항 연산을 적용하는 데 사용할 수 있습니다. 이 알고리즘은 프로그래밍 문제를 해결하는 데 있어서 매우 중요한 도구가 될 수 있습니다.

 

10.6.3. inner_product의 사용

'inner_product의 사용'에서는 STL의 중요한 수치 알고리즘 중 하나인 inner_product에 대해 알아보겠습니다.

 

inner_product는 두 벡터의 내적을 계산하는 함수입니다. 이 함수는 두 벡터의 원소를 순서대로 곱한 후 그 결과를 모두 더합니다. 이 함수는 두 개의 시작 위치를 인자로 받아 각 벡터의 원소를 곱하고 더한 결과를 반환합니다.

 

아래는 C++를 이용한 inner_product의 사용 예제입니다:

 

[예제]

#include <iostream>
#include <vector>
#include <numeric> // inner_product를 사용하기 위해 필요

int main() {
    std::vector<int> v1 = {1, 2, 3, 4, 5};
    std::vector<int> v2 = {10, 20, 30, 40, 50};

    int inner_product_result = std::inner_product(v1.begin(), v1.end(), v2.begin(), 0);

    std::cout << "Inner Product: " << inner_product_result;
    return 0;
}

 

이 예제에서 v1과 v2의 내적은 각 벡터의 동일한 위치에 있는 원소를 곱한 후 그 결과를 모두 더한 것입니다. 따라서 출력 결과는 "Inner Product: 550"이 됩니다.

 

inner_product 함수는 표준적인 내적 외에도 사용자 정의 연산을 적용할 수 있습니다. 사용자 정의 연산을 적용하려면 inner_product 함수에 추가 인자를 더 제공해야 합니다. 예를 들어, 원소를 곱하는 대신 더하고 싶다면 아래와 같이 작성할 수 있습니다:

 

[예제]

int sum_result = std::inner_product(v1.begin(), v1.end(), v2.begin(), 0, std::plus<int>(), std::minus<int>());

 

이 코드는 v1의 각 원소에서 v2의 동일한 위치의 원소를 빼고, 그 결과를 모두 더한 값을 반환합니다. std::plus<int>()는 결과를 더하는 이항 연산자고, std::minus<int>()는 각 벡터의 원소를 빼는 이항 연산자입니다.

 

이처럼 inner_product 함수는 벡터의 내적을 계산하는 데 사용할 수 있을 뿐만 아니라, 사용자 정의 연산을 적용하는 데도 유용합니다. 이 함수는 데이터 분석, 머신러닝 등 다양한 분야에서 사용되며, 프로그래밍 문제를 해결하는 데 있어 중요한 도구가 될 수 있습니다.

 

10.6.4. adjacent_difference, partial_sum의 사용

'adjacent_difference, partial_sum의 사용'에서는 STL의 두 수치 알고리즘인 adjacent_difference와 partial_sum에 대해 알아보겠습니다.

 

먼저 adjacent_difference 함수는 벡터나 배열과 같은 컨테이너의 연속하는 원소 간의 차이를 계산합니다. 이 함수는 두 개의 반복자(시작과 끝)와 결과를 저장할 위치를 인자로 받습니다. 이 함수는 원소 간의 차이를 결과 벡터에 저장하며, 반환값은 마지막 원소를 가리키는 반복자입니다.

 

다음은 adjacent_difference 함수를 사용하는 C++ 코드 예제입니다:

 

[예제]

#include <iostream>
#include <vector>
#include <numeric> // adjacent_difference를 사용하기 위해 필요

int main() {
    std::vector<int> v = {10, 20, 30, 40, 50};
    std::vector<int> diff(v.size());

    std::adjacent_difference(v.begin(), v.end(), diff.begin());

    for(int n : diff) {
        std::cout << n << ' ';
    }
    return 0;
}

 

이 예제에서 diff 벡터의 첫 번째 원소는 v의 첫 번째 원소와 같고, 나머지 원소는 v의 각 원소와 그 전 원소와의 차이입니다. 따라서 출력 결과는 "10 10 10 10 10 "이 됩니다.

 

다음으로 partial_sum 함수는 주어진 범위의 원소를 누적해서 더합니다. 이 함수는 두 개의 반복자(시작과 끝)와 결과를 저장할 위치를 인자로 받습니다. 이 함수는 원소를 누적해서 더한 결과를 결과 벡터에 저장하며, 반환값은 마지막 원소를 가리키는 반복자입니다.

 

다음은 partial_sum 함수를 사용하는 C++ 코드 예제입니다:

 

[예제]

#include <iostream>
#include <vector>
#include <numeric> // partial_sum을 사용하기 위해 필요

int main() {
    std::vector<int> v = {10, 20, 30, 40, 50};
    std::vector<int> sum(v.size());

    std::partial_sum(v.begin(), v.end(), sum.begin());

    for(int n : sum) {
        std::cout << n << ' ';
    }
    return 0;
}

 

이 예제에서 sum 벡터의 각 원소는 v의 해당 원소까지의 합입니다. 따라서 출력 결과는 "10 30 60 100 150 "이 됩니다.

 

이처럼 adjacent_difference와 partial_sum 함수는 컨테이너의 원소 간의 연산을 수행하는 데 유용합니다. 이 두 함수는 데이터 분석, 머신러닝 등 다양한 분야에서 사용되며, 프로그래밍 문제를 해결하는 데 있어 중요한 도구가 될 수 있습니다.

10.7. 집합 알고리즘

C/C++의 '집합 알고리즘'은 두 개 이상의 정렬된 컬렉션(집합)에 대한 연산을 제공하는 STL 알고리즘에 대해 설명합니다. 이러한 알고리즘에는 set_union, set_intersection, set_difference 및 set_symmetric_difference 등이 포함되며, 각각 합집합, 교집합, 차집합, 대칭 차집합 연산을 수행합니다. 이들 알고리즘은 알고리즘 헤더 파일에 포함되어 있으며, 중복 없는 정렬된 범위에 대한 입력을 필요로 합니다.

10.7.1. merge의 사용

STL의 merge는 두 개의 정렬된 컬렉션을 합칠 때 유용한 알고리즘입니다. merge 함수는 두 정렬된 범위를 합친 결과를 저장할 위치를 지정하는 세 번째 반복자를 사용합니다.

 

먼저 사용해 보기 전에 필요한 헤더 파일을 포함해야 합니다.

 

[예제]

#include <algorithm>
#include <vector>


merge 함수의 기본적인 사용 방법은 다음과 같습니다:

 

[예제]

std::vector<int> v1 = {1, 3, 5};
std::vector<int> v2 = {2, 4, 6};
std::vector<int> v3(6);  // 저장할 공간을 미리 할당합니다.

std::merge(v1.begin(), v1.end(), v2.begin(), v2.end(), v3.begin());

 

이 코드는 v1과 v2 벡터의 요소를 v3에 합칩니다. 결과적으로 v3는 {1, 2, 3, 4, 5, 6}이 됩니다.

 

이때, 주의할 점은 입력 범위가 이미 정렬된 상태여야 한다는 것입니다. 그렇지 않다면 예상치 못한 결과가 나올 수 있습니다. 그리고 merge는 각 입력 범위에 동일한 값이 여러 개 있을 때, 첫 번째 범위의 값들이 합친 결과에서 먼저 나타나게 합니다.

 

merge 함수를 사용하면 두 범위의 요소를 쉽고 빠르게 합칠 수 있습니다. 그러나 결과를 저장할 공간이 충분해야 한다는 점을 잊지 마세요. merge는 결과 범위의 크기를 자동으로 조정하지 않으므로, 충분한 공간이 확보되지 않은 상태에서 merge를 호출하면 런타임 에러가 발생할 수 있습니다.

 

프로그래밍을 배우는 데 있어 merge와 같은 STL 알고리즘을 이해하고 사용하는 것은 매우 중요합니다. 이는 코드를 더 간결하고 효율적으로 만드는 데 큰 도움이 됩니다. 이 기능을 활용하면 복잡한 알고리즘을 직접 구현할 필요 없이, 간단한 코드 몇 줄로 다양한 문제를 해결할 수 있습니다.

 

10.7.2. includes의 사용

includes 함수는 C++ STL(Standard Template Library)의 알고리즘 중 하나로, 한 범위가 다른 범위를 포함하는지를 판단하는 역할을 합니다. '범위 A가 범위 B를 포함하고 있는가?'를 쉽게 확인할 수 있습니다.

 

먼저 algorithm 헤더 파일을 포함해야 includes 함수를 사용할 수 있습니다.

 

[예제]

#include <algorithm>
#include <vector>

 

includes 함수는 두 개의 입력 범위와 각각의 시작과 끝을 가리키는 반복자를 매개변수로 받습니다. 이 함수는 첫 번째 범위가 두 번째 범위의 모든 원소를 포함하면 true를 반환하고, 그렇지 않으면 false를 반환합니다.

 

다음은 includes 함수의 사용 예시입니다:

 

[예제]

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

bool result = std::includes(v1.begin(), v1.end(), v2.begin(), v2.end());

 

위 코드에서 includes 함수는 벡터 v1이 v2를 포함하고 있는지를 판단합니다. 결과적으로 result는 true가 됩니다.

 

이때 주의해야 할 점은 includes 함수가 올바르게 작동하려면 입력 범위가 정렬된 상태여야 한다는 것입니다. 그렇지 않으면 예상하지 못한 결과가 나올 수 있습니다.

 

includes 함수는 데이터 구조에 어떤 원소가 포함되어 있는지 빠르게 판단하는 데 유용합니다. 이 함수를 통해 복잡한 포함 관계를 간결하게 표현할 수 있어, 코드를 더 읽기 쉽게 만들어 줍니다. 이런 편리함을 제공하는 STL 알고리즘을 잘 활용하면, 프로그래밍을 더 효율적으로 할 수 있습니다.

 

STL에 대한 이해를 높이고 그 힘을 누리려면, STL 알고리즘에 익숙해지는 것이 중요합니다. 이를 위해 merge, includes와 같은 알고리즘을 자주 사용해 보고, 어떻게 작동하는지 이해하려 노력하면 도움이 될 것입니다.

 

10.7.3. set_union, set_intersection, set_difference, set_symmetric_difference의 사용

C++ STL에서는 집합 연산을 위한 네 가지 기본 함수를 제공합니다: set_union, set_intersection, set_difference, set_symmetric_difference. 이들 함수는 모두 algorithm 헤더 파일에 정의되어 있습니다. 이들 함수를 사용하면 두 범위(집합) 간의 합집합, 교집합, 차집합, 대칭 차집합을 쉽게 구할 수 있습니다.

 

[예제]

#include <algorithm>
#include <vector>
#include <iterator>

 

각 함수는 두 개의 입력 범위와 출력 반복자를 매개변수로 받습니다. 출력 반복자는 연산 결과를 저장할 위치를 가리킵니다. 이를 위해 back_inserter를 사용해 벡터의 끝에 결과를 추가할 수 있습니다.

 

[예제]

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


set_union 함수는 두 범위의 합집합을 구합니다.

 

[예제]

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

 

set_intersection 함수는 두 범위의 교집합을 구합니다.

 

[예제]

std::set_intersection(v1.begin(), v1.end(), v2.begin(), v2.end(), std::back_inserter(v3)); // v3: {4, 5}

 

set_difference 함수는 첫 번째 범위에서 두 번째 범위를 뺀 차집합을 구합니다.

 

[예제]

std::set_difference(v1.begin(), v1.end(), v2.begin(), v2.end(), std::back_inserter(v3));// v3: {1, 2, 3}

 

set_symmetric_difference 함수는 두 범위의 대칭 차집합을 구합니다. 이는 한 범위에만 있는 원소들의 집합을 의미합니다.

 

[예제]

std::set_symmetric_difference(v1.begin(), v1.end(), v2.begin(), v2.end(), std::back_inserter(v3)); // v3: {1, 2, 3, 6, 7, 8}

 

이 함수들을 사용할 때는 입력 범위가 정렬되어 있어야 합니다. 또한, 이들 함수는 결과를 '출력 반복자'에 삽입하므로, 충분한 공간이 확보되어 있어야 합니다. 이를 위해 보통 back_inserter를 사용해 결과를 저장할 컨테이너의 끝에 추가합니다.

 

이들 집합 알고리즘은 매우 강력하고, 복잡한 집합 연산을 간결하게 표현할 수 있게 해줍니다. 이를 잘 활용하면 복잡한 문제를 쉽게 해결할 수 있습니다. 그러므로 이 알고리즘들에 익숙해지는 것이 중요합니다. 다양한 예제를 통해 연습하고, 각 함수가 어떻게 동작하는지 이해하는 것이 중요합니다.

10.8. 힙 알고리즘

힙 알고리즘은 우선순위 큐의 기반이 되는 데이터 구조인 '힙'을 다루는 STL 알고리즘입니다. STL에서 제공하는 힙 관련 함수는 make_heap, push_heap, pop_heap 그리고 sort_heap이 있습니다. 이들 함수는 모두 algorithm 헤더에 포함되어 있습니다. make_heap은 주어진 범위를 힙으로 만들고, push_heap과 pop_heap은 원소를 힙에 추가하거나 삭제합니다. 마지막으로 sort_heap은 힙을 이용해 범위를 정렬합니다.

10.8.1. make_heap, push_heap, pop_heap의 사용

C++의 표준 템플릿 라이브러리 (STL)은 '힙'과 관련된 알고리즘을 제공하며, 이들은 모두 <algorithm> 헤더에 포함되어 있습니다. 이번 섹션에서는 make_heap, push_heap, 그리고 pop_heap에 대해 다루도록 하겠습니다.

 

make_heap은 범위 내의 원소들을 재배열하여 힙을 만듭니다. 이 함수를 호출하면, 벡터의 첫 번째 원소가 항상 최대값을 가지게 됩니다. 이때 원소들의 순서는 이진 힙 트리의 속성을 만족하게 됩니다.

 

[예제]

std::vector<int> v = {3, 2, 4, 1, 5, 9};
std::make_heap(v.begin(), v.end());

push_heap은 힙에 원소를 추가하는 역할을 합니다. 이 함수를 호출하기 전에, 새로운 원소는 힙의 범위 바로 뒤에 추가되어야 합니다. 그런 다음 push_heap을 호출하여 이 원소를 적절한 위치로 이동시키게 됩니다.

 

[예제]

v.push_back(6);
std::push_heap(v.begin(), v.end());

반면에 pop_heap은 힙에서 가장 큰 원소를 제거하는 역할을 합니다. 이 함수를 호출하면, 힙의 첫 번째 원소(즉, 최대값)가 범위의 끝으로 이동되고, 힙의 나머지 원소들이 재배열됩니다. 이후 원소를 실제로 제거하려면 pop_back을 호출해야 합니다.

 

[예제]

std::pop_heap(v.begin(), v.end());
v.pop_back();

위의 세 함수는 모두 기본적으로 최대 힙을 구현합니다. 최소 힙을 만들려면, 비교 함수를 제공해야 합니다. 이는 모든 세 함수에 대해 동일하게 적용됩니다.

 

이런 식으로, STL의 힙 알고리즘은 효율적인 방식으로 데이터를 정렬하고, 가장 큰(또는 가장 작은) 원소에 빠르게 접근할 수 있도록 해줍니다. 따라서 이들 함수는 우선순위 큐와 같은 데이터 구조를 구현하는 데 유용하게 사용됩니다.

 

아래에 C++ 예제를 작성했습니다. 이 코드는 앞에서 설명한 힙 알고리즘의 사용을 보여줍니다.

 

[예제]

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

int main() {
    // 벡터 생성 및 초기화
    std::vector<int> v = {3, 2, 4, 1, 5, 9};

    // make_heap 호출
    std::make_heap(v.begin(), v.end());
    std::cout << "After make_heap, v: ";
    for (int i : v)
        std::cout << i << ' ';
    std::cout << '\n';

    // 새 원소를 벡터 끝에 추가하고 push_heap 호출
    v.push_back(6);
    std::push_heap(v.begin(), v.end());
    std::cout << "After push_heap, v: ";
    for (int i : v)
        std::cout << i << ' ';
    std::cout << '\n';

    // pop_heap 호출 후 원소 제거
    std::pop_heap(v.begin(), v.end());
    v.pop_back();
    std::cout << "After pop_heap, v: ";
    for (int i : v)
        std::cout << i << ' ';
    std::cout << '\n';

    return 0;
}

 

이 프로그램을 실행하면 다음과 같은 출력이 나타납니다. 

After make_heap, v: 9 5 4 1 2 3 
After push_heap, v: 9 6 4 1 2 3 5 
After pop_heap, v: 6 5 4 1 2 3

 

첫 번째 출력에서 볼 수 있듯이 make_heap이 호출된 후에는 벡터의 첫 원소가 최대값입니다. 그런 다음 새 원소를 추가하고 push_heap을 호출하면, 이 원소가 적절한 위치로 이동됩니다. 마지막으로 pop_heap을 호출하면, 가장 큰 원소가 범위의 끝으로 이동되고, 나머지 원소들이 재배열됩니다.

 

여기서 주목해야 할 점은, 이 알고리즘들이 힙을 유지하는 동안 원소들 사이의 상대적인 순서는 보장되지 않는다는 것입니다. 즉, 원소들은 힙 속성을 만족하도록 재배열되지만, 이외의 순서는 무작위일 수 있습니다.

 

이러한 힙 알고리즘들은 우선 순위 큐 구현 및 힙 자료구조와 관련된 다양한 문제를 해결하는 데 사용됩니다. 이 함수들을 이해하고 올바르게 사용하면, 효율적인 방식으로 복잡한 문제를 해결할 수 있게 됩니다.

 

10.8.2. sort_heap의 사용

C++ STL 알고리즘에서 std::sort_heap은 힙을 정렬하는 함수입니다. 즉, 이 함수는 힙으로 만든 뒤에 힙 구조를 무시하고 원소들을 오름차순으로 정렬합니다. 다음은 std::sort_heap 함수의 기본적인 사용법입니다.

 

[예제]

void sort_heap( RandomAccessIterator first, RandomAccessIterator last );

 

이 함수는 [first, last) 범위의 원소들을 정렬합니다. 이때, 범위 내의 모든 원소들이 유효한 힙을 형성해야 합니다. 그렇지 않으면 결과는 정의되지 않습니다.

 

이제 sort_heap을 사용하는 간단한 예제를 살펴보겠습니다.

 

[예제]

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

int main() {
    std::vector<int> v = {3, 2, 4, 1, 5, 9};

    // 먼저 벡터를 힙으로 만듭니다.
    std::make_heap(v.begin(), v.end());

    // 그런 다음 힙을 정렬합니다.
    std::sort_heap(v.begin(), v.end());

    std::cout << "v: ";
    for (int i : v)
        std::cout << i << ' ';
    std::cout << '\n';

    return 0;
}

 

이 코드를 실행하면 다음과 같은 출력이 나타납니다.

 

v: 1 2 3 4 5 9

 

이 예제에서는 먼저 std::make_heap을 사용하여 벡터를 힙으로 만든 뒤, std::sort_heap을 사용하여 힙을 정렬합니다. 힙을 정렬한 결과, 벡터의 원소들이 오름차순으로 정렬됩니다.

 

이와 같이 std::sort_heap은 힙 정렬 알고리즘을 구현하는 데 사용할 수 있습니다. 힙 정렬은 원소를 추가하거나 제거하는 데 O(log n)의 시간이 걸리는 힙의 속성을 이용한 정렬 알고리즘이며, 이를 통해 모든 원소를 효율적으로 정렬할 수 있습니다. 이러한 특성 때문에 힙 정렬은 빠르고 효율적인 정렬 알고리즘으로 널리 알려져 있습니다.

 

그러나 std::sort_heap을 사용할 때는 주의해야 할 점이 있습니다. 그것은 sort_heap 함수가 원래의 힙 구조를 무시한다는 것입니다. 따라서 이 함수를 호출한 후에는 원본 힙은 더 이상 힙이 아니며, 힙 연산을 사용하려면 다시 make_heap을 호출해야 합니다. 이 점을 염두에 두고 sort_heap을 사용하면, 효율적인 방식으로 데이터를 정렬하고 관리할 수 있습니다.

 

10.8.3. is_heap, is_heap_until의 사용

  • C++ STL 알고리즘에는 힙이 제대로 구성되어 있는지 확인하는 두 가지 함수가 있습니다: std::is_heap과 std::is_heap_until. 이 두 함수는 이름에서 알 수 있듯이, 힙에 관련된 조건을 확인합니다.
  • std::is_heap : 이 함수는 주어진 범위의 원소들이 힙을 형성하는지 확인합니다. 힙을 형성하면 true를 반환하고, 그렇지 않으면 false를 반환합니다.
  • std::is_heap_until : 이 함수는 주어진 범위에서 힙 조건을 만족하는 마지막 위치를 찾습니다. 이 위치는 범위 내에서 힙을 형성하는 마지막 원소를 가리킵니다.

두 함수 모두 다음과 같은 형식을 가집니다.

 

[예제]

bool is_heap( ForwardIterator first, ForwardIterator last );
ForwardIterator is_heap_until( ForwardIterator first, ForwardIterator last );


이제 이 두 함수를 사용하는 예제를 살펴보겠습니다.

 

[예제]

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

int main() {
    std::vector<int> v = {3, 2, 4, 1, 5, 9};

    // 먼저 벡터를 힙으로 만듭니다.
    std::make_heap(v.begin(), v.end());

    // is_heap을 사용하여 벡터가 힙인지 확인합니다.
    if (std::is_heap(v.begin(), v.end()))
        std::cout << "v is a heap.\n";
    else
        std::cout << "v is not a heap.\n";

    // is_heap_until을 사용하여 힙 조건을 만족하는 마지막 위치를 찾습니다.
    auto last_heap = std::is_heap_until(v.begin(), v.end());

    std::cout << "The last element of the heap is: " << *(last_heap - 1) << '\n';

    return 0;
}

 

이 예제에서는 먼저 std::make_heap을 사용하여 벡터를 힙으로 만든 뒤, std::is_heap을 사용하여 벡터가 힙인지 확인합니다. 그런 다음 std::is_heap_until을 사용하여 힙 조건을 만족하는 마지막 위치를 찾습니다.

 

이런 식으로 std::is_heap과 std::is_heap_until을 사용하면, 주어진 범위의 원소들이 힙을 형성하는지, 그리고 힙 조건을 만족하는 마지막 원소는 어디인지 확인할 수 있습니다. 이 두 함수는 힙의 속성을 확인하고 유효성을 검사하는 데 매우 유용합니다.

 

마지막으로, std::is_heap과 std::is_heap_until은 모두 C++11부터 사용 가능하므로, 이 함수들을 사용하려면 컴파일러가 C++11 이상을 지원하는지 확인해야 합니다.

10.9. 최소/최대 알고리즘

C++ STL 알고리즘은 데이터의 최소값과 최대값을 찾는 여러 방법을 제공합니다. 이를 위한 함수로는 min, max, minmax, min_element, max_element, minmax_element 등이 있습니다. 각 함수는 그 이름에서 알 수 있듯이 특정 작업을 수행합니다. 예를 들어, min과 max는 각각 최소값과 최대값을 반환하고, minmax는 한 번의 호출로 두 값을 모두 반환합니다. *_element 은 해당 값이 위치한 요소의 반복자를 반환합니다. 이런 알고리즘들을 사용하면 간단하게 데이터의 최소값과 최대값을 찾을 수 있습니다.

10.9.1. min, max의 사용

데이터의 최소와 최대를 찾는 것은 프로그래밍에서 매우 일반적인 작업입니다. STL은 이를 쉽게 처리할 수 있는 함수들을 제공하고 있습니다: std::min과 std::max입니다. 이 함수들은 이름에서 알 수 있듯이 주어진 두 값 중 최소값과 최대값을 반환합니다.

 

이제 한 번 이 함수들을 사용해 보도록 하겠습니다.

 

C++에서의 사용 예제:

 

[예제]

#include <algorithm>
#include <iostream>

int main() {
    int a = 5, b = 10;
    std::cout << "Min: " << std::min(a, b) << "\n";
    std::cout << "Max: " << std::max(a, b) << "\n";
    return 0;
}

 

이 코드를 실행하면 "Min: 5"와 "Max: 10"이라는 출력을 볼 수 있습니다. 이 예제에서는 두 정수 a와 b 중에서 최소값과 최대값을 찾기 위해 std::min과 std::max를 사용했습니다.

 

std::min과 std::max는 두 개 이상의 인자를 처리하는 버전도 제공합니다. 이 경우, 인자들은 모두 동일한 타입이어야 합니다. 이 함수들은 첫 번째 인자와 나머지 인자들을 비교하고 최소값 또는 최대값을 반환합니다. 다음은 그 예시입니다.

 

[예제]

#include <algorithm>
#include <iostream>

int main() {
    std::cout << "Min: " << std::min({1, 2, 3, 4, 5}) << "\n";
    std::cout << "Max: " << std::max({1, 2, 3, 4, 5}) << "\n";
    return 0;
}

 

이 코드를 실행하면 "Min: 1"와 "Max: 5"라는 출력을 볼 수 있습니다. 이 예제에서는 initializer list (중괄호 안에 콤마로 구분된 값의 리스트)를 이용해 std::min과 std::max에 여러 개의 인자를 전달했습니다. 이러한 방식은 C++11부터 지원하는 문법이며, 이를 통해 쉽게 여러 개의 값을 한 번에 처리할 수 있습니다.

 

이처럼, std::min과 std::max는 값을 비교하는 함수로서 매우 유용합니다. 이 함수들을 사용하면 복잡한 비교 로직을 작성하지 않고도 간단하게 최소값 또는 최대값을 찾을 수 있습니다. 그리고 이 함수들은 모든 타입의 값에 대해 동작하므로 매우 범용적으로 사용할 수 있습니다.

 

다음은 이들 함수의 확장된 버전인 std::min_element와 std::max_element에 대해 알아보겠습니다. 이 함수들은 주어진 범위 내에서 최소값 또는 최대값의 위치(반복자)를 찾아주는 기능을 가지고 있습니다.

 

10.9.2. minmax의 사용

우리는 STL에서 제공하는 std::min과 std::max 함수를 살펴봤습니다. 이들 함수를 사용하면 주어진 값들 중 최소값과 최대값을 각각 찾을 수 있습니다. 그런데, 때로는 주어진 값들 중에서 최소값과 최대값을 동시에 찾아야 할 때가 있습니다. 이럴 때 사용하는 함수가 std::minmax입니다.

 

std::minmax는 주어진 두 값이나 값의 범위에서 최소값과 최대값을 동시에 찾아서 pair 형태로 반환합니다. 이는 두 번의 검색 작업을 줄여 한 번에 최소와 최대를 찾아줍니다.

 

이제 C++에서 std::minmax 함수를 사용하는 방법을 살펴보겠습니다.

 

[예제]

#include <algorithm>
#include <iostream>

int main() {
    int a = 5, b = 10;
    auto result = std::minmax(a, b);
    std::cout << "Min: " << result.first << ", Max: " << result.second << "\n";
    return 0;
}

 

이 코드를 실행하면 "Min: 5, Max: 10"이라는 출력을 볼 수 있습니다. 이 예제에서는 두 정수 a와 b 중에서 최소값과 최대값을 동시에 찾기 위해 std::minmax를 사용했습니다.

 

마찬가지로, std::minmax는 두 개 이상의 인자를 처리하는 버전도 제공합니다. 이 경우, 인자들은 모두 동일한 타입이어야 합니다. 이 함수는 첫 번째 인자와 나머지 인자들을 비교하고 최소값과 최대값을 반환합니다. 다음은 그 예시입니다.

 

[예제]

#include <algorithm>
#include <iostream>

int main() {
    auto result = std::minmax({1, 2, 3, 4, 5});
    std::cout << "Min: " << result.first << ", Max: " << result.second << "\n";
    return 0;
}

 

이 코드를 실행하면 "Min: 1, Max: 5"라는 출력을 볼 수 있습니다. 이 예제에서는 initializer list를 이용해 std::minmax에 여러 개의 인자를 전달했습니다. std::minmax가 반환하는 값은 std::pair형태이며, 이를 통해 한 번에 최소값과 최대값을 찾을 수 있습니다.

 

std::minmax는 효율적인 최소/최대 값 검색을 위해 사용되며, 특히 한 번의 검색으로 최소 및 최대 값을 동시에 찾아야 하는 경우에 유용합니다. 이는 코드의 복잡성을 줄이고, 코드의 실행 시간을 단축하는 데 도움을 줍니다.

 

10.9.3. min_element, max_element, minmax_element의 사용

이번에는 컨테이너의 범위 내에서 최소값과 최대값, 그리고 동시에 최소값과 최대값을 찾는 또 다른 방법인 'min_element', 'max_element', 'minmax_element' 함수에 대해 알아보겠습니다.

 

첫 번째로 'min_element' 함수는 컨테이너에서 가장 작은 원소의 위치(반복자)를 반환합니다. 'max_element' 함수는 반대로 가장 큰 원소의 위치(반복자)를 반환합니다.

 

아래에 이를 사용하는 C++ 예제 코드를 보여드리겠습니다.

 

[예제]

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

int main() {
    std::vector<int> v = {5, 4, 2, 8, 7};
    auto minPos = std::min_element(v.begin(), v.end());
    auto maxPos = std::max_element(v.begin(), v.end());

    std::cout << "Min Element: " << *minPos << ", at index: " << std::distance(v.begin(), minPos) << "\n";
    std::cout << "Max Element: " << *maxPos << ", at index: " << std::distance(v.begin(), maxPos) << "\n";

    return 0;
}

 

이 코드를 실행하면, 벡터 v 내에서 가장 작은 원소와 가장 큰 원소의 값을 그리고 그 위치를 출력합니다.

 

마지막으로 'minmax_element' 함수는 범위 내에서 최소값과 최대값을 동시에 찾아 반환합니다. 이 함수는 pair로 최소값의 반복자와 최대값의 반복자를 반환하게 됩니다.

 

아래는 'minmax_element'를 사용하는 예제 코드입니다.

 

[예제]

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

int main() {
    std::vector<int> v = {5, 4, 2, 8, 7};
    auto [minPos, maxPos] = std::minmax_element(v.begin(), v.end());

    std::cout << "Min Element: " << *minPos << ", at index: " << std::distance(v.begin(), minPos) << "\n";
    std::cout << "Max Element: " << *maxPos << ", at index: " << std::distance(v.begin(), maxPos) << "\n";

    return 0;
}

 

이 코드를 실행하면, 벡터 v 내에서 가장 작은 원소와 가장 큰 원소의 값을 그리고 그 위치를 동시에 출력합니다. 또한, 이 코드에서는 C++17의 구조화된 바인딩(structured binding) 기능을 사용해 'minmax_element'가 반환하는 pair를 minPos와 maxPos라는 두 변수에 동시에 할당했습니다.

 

이런 방식으로, STL 알고리즘은 우리가 컨테이너에 있는 데이터를 효율적으로 다룰 수 있게 해줍니다. 이 세 함수는 매우 유용하므로 다양한 상황에서 사용해 보시기 바랍니다.

 

min_element, max_element, minmax_element 함수들은 기본적으로 이터레이터의 범위를 인자로 받아서 처리합니다. 그런데 이 함수들은 모두 두 가지 버전으로 제공됩니다. 첫 번째 버전은 원소들을 비교할 때 'operator<'를 사용하며, 두 번째 버전은 사용자가 지정한 비교 함수를 사용합니다.

 

이 사용자 정의 비교 함수를 이용하면, 커스텀 비교 로직을 적용할 수 있습니다. 예를 들어, 절대값 기준으로 최소값 혹은 최대값을 찾는 경우, 사용자 정의 비교 함수를 작성하고 이를 min_element, max_element, minmax_element 함수에 전달하면 됩니다.

 

다음은 C++로 작성된 예제 코드입니다.

 

[예제]

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

bool absCompare(int a, int b) {
    return (std::abs(a) < std::abs(b));
}

int main() {
    std::vector<int> v = {-5, 4, -2, 8, -7};
    auto minPos = std::min_element(v.begin(), v.end(), absCompare);
    auto maxPos = std::max_element(v.begin(), v.end(), absCompare);

    std::cout << "Min Element (by abs): " << *minPos << "\n";
    std::cout << "Max Element (by abs): " << *maxPos << "\n";

    return 0;
}

 

이 코드는 각 원소의 절대값을 비교하여, 절대값이 가장 작은 원소와 가장 큰 원소를 찾습니다. 비교 함수 absCompare를 작성하고, 이 함수를 min_element와 max_element에 전달함으로써 이를 구현하였습니다.

 

이처럼 STL 알고리즘은 우리가 원하는 로직을 유연하게 적용할 수 있게 해 주며, 코드의 재사용성을 높여줍니다. 

 

 

 

2023.06.07 - [GD's IT Lectures : 기초부터 시리즈/C, C++ 기초부터 ~] - [C/C++ 프로그래밍 : 중급] 9.STL 컨테이너

 

[C/C++ 프로그래밍 : 중급] 9.STL 컨테이너

Chapter 9. STL 컨테이너 STL(Standard Template Library) 컨테이너는 C++ 표준 라이브러리의 일부로, 다양한 데이터 구조를 제공합니다. 이 컨테이너들은 자료형에 대해 일반화된(generic) 프로그래밍을 가능하

gdngy.tistory.com

 

반응형

'GD's IT Lectures : 기초부터 시리즈 > C, C++ 기초부터 ~' 카테고리의 다른 글

[C/C++ 프로그래밍 : 중급] 12. 람다 표현식  (0) 2023.06.13
[C/C++ 프로그래밍 : 중급] 11. 스마트 포인터  (0) 2023.06.12
[C/C++ 프로그래밍 : 중급] 9.STL 컨테이너  (0) 2023.06.07
[C/C++ 프로그래밍 : 중급] 8. 예외 처리와 오류 처리  (0) 2023.06.03
[C/C++ 프로그래밍 : 중급] 7.가상 함수와 추상 클래스  (0) 2023.05.30

관련글

댓글

티스토리툴바