[C++] 최댓값과 최솟값을 한 번에 찾자 max_element / min_element

어떤 배열이나 container의 최댓값 및 최솟값이 필요한 경우는 무수히 많다고 해도 과언이 아니다. 하지만, 배열의 원소 하나씩 접근하고 비교하면서 최댓값 / 최솟값을 찾으면 이거만큼 코드의 가독성이 떨어지고 슬픈일이 아닐 수 없다.

 

특별한 함수를 사용하지 않고 for문을 통해 배열의 원소 하나씩 접근하며 도는 경우 다음과 같은 코드를 작성할 수 있다.

 

int max_num = min_num = nums[0];
 
for(int i = 0; i < (int)nums.size(); i++) {
    if (nums[i] > max_num) {
        max_num = nums[i]; // finding max number in nums
    }
 
    if (nums[i] < min_num) {
        min_num = nums[i]; // finding min number in nums
    }
}

 

배열 nums의 원소를 하나씩 돌면서 max_num과 min_num에 각각 최댓값과 최솟값이 담기는 모습을 확인할 수 있다. 그러나, 너무나도 귀찮고, 귀찮다. 하물며 최댓값 또는 최솟값의 index를 묻는다면 새로운 변수에 담아야 하거나, 다른 방법으로 구해야 한다.

 

이제, 이러한 길고 긴 for문을 탈출하고 함수 한 번에 모든 것을 처리하자.

 

1. max_element

(※ https://www.cplusplus.com/reference/algorithm/max_element/ 에서 함수에 대한 정보를 확인할 수 있다.)

 

C++의 알고리즘 관련 헤더 <algorithm.h>에는 max_element라는 함수는 다음과 같이 두 가지 구조를 가진다.

 

1] default - ForwardIterator max_element(ForwardIterator first, ForwardIterator last)

2] custom - ForwardIterator max_element(ForwardIterator first, ForwardIterator last, Compare comp)

 

max_element는 쓰임에 따라 2개 혹은 3개의 인자를 받는다.

 

• ForwardIterator first : 배열이나 어떤 container 자료형의 시작부 혹은 포인터
• ForwardIterator last : 배열이나 어떤 container 자료형의 끝부 혹은 포인터

 

만약, max_element가 우리가 생각하는 가장 큰 원소가 아닌, custom key를 통해 max를 추출하고 싶다면 마지막에 하나의 인자를 추가한다.

 

• Compare comp : 배열이나 어떤 container의 값 두개를 받아 bool로 반환이 가능한 함수, 이때 첫 번째 원소가 두 번째 원소보다 작은 것을 기본값으로 하여 두 개의 값을 비교하는 함수가 필요하다. 이때 함수는 원본의 값을 변형하거나 수정하지 않는다. 함수 포인터 혹은 함수 객체 모두 사용가능하다.

 

세 번째 인자 Compare comp 에는 어떤 방식으로 정렬을 하고, max를 선택할 지 직접 사용자가 지정할 수 있도록 가능하게 하는 함수이다.

---

이 함수의 return 값이 예상하는 return값과 조금 다른데, 이 함수가 return하는 자료형을 관찰하면 ForwardIterator, 즉 Iterator를 반환한다. 결국 주소값(포인터)를 반환한다는 의미이고, max인 곳의 주소값을 반환한다고 생각하면 된다.

 

바꾸어 말하면, 주소에 담긴값을 알려면 참조 연산자(*)를 사용하면 된다. 또한, 최댓값의 index를 알려면 max_element의 return값에서 배열의 처음 포인터를 빼주면 된다.

 

결국 정리하자면, 범위 [first, last)에서 3번째 인자가 없다면 C++ 상 가장 큰 수의 iterator를 반환하고, 3번쨰 인자가 있다면 사용자가 정해준 정렬 함수상 가장 큰 수의 iterator를 반환한다. 같은 역할을 하는 코드를 작성하면 다음과 같이 작성할 수 있다.

 

// 1. default
template <class ForwardIterator>
  ForwardIterator max_element ( ForwardIterator first, ForwardIterator last ) {
  if (first==last) return last;
 
  ForwardIterator largest = first;
 
  while (++first!=last)
    if (*largest<*first)    // max_comparison
      largest=first;
 
  return largest;
}
 
// 2. custom
template <class ForwardIterator>
  ForwardIterator max_element ( ForwardIterator first, ForwardIterator last ) {
  if (first==last) return last;
 
  ForwardIterator largest = first;
 
  while (++first!=last)
    if (comp(*largest,*first)) // custom comparison
      largest=first;
 
  return largest;
}

 

쉽게 말해, 가장 큰 놈의 주소값을 알려주는 함수라 생각하면 된다.

 

2. min_element

(※ https://www.cplusplus.com/reference/algorithm/min_element/ 에서 함수에 대한 정보를 확인할 수 있다.)

 

C++의 알고리즘 관련 헤더 <algorithm.h>에는 min_element라는 함수는 다음과 같이 두 가지 구조를 가진다.

 

1] default - ForwardIterator min_element(ForwardIterator first, ForwardIterator last)

2] custom - ForwardIterator min_element(ForwardIterator first, ForwardIterator last, Compare comp)

 

min_element는 쓰임에 따라 2개 혹은 3개의 인자를 받는다.

 

• ForwardIterator first : 배열이나 어떤 container 자료형의 시작부 혹은 포인터
• ForwardIterator last : 배열이나 어떤 container 자료형의 끝부 혹은 포인터

 

만약, min_element가 우리가 생각하는 가장 큰 원소가 아닌, custom key를 통해 min을 추출하고 싶다면 마지막에 하나의 인자를 추가한다.

 

• Compare comp : 배열이나 어떤 container의 값 두개를 받아 bool로 반환이 가능한 함수, 이때 첫 번째 원소가 두 번째 원소보다 작은 것을 기본값으로 하여 두 개의 값을 비교하는 함수가 필요하다. 이때 함수는 원본의 값을 변형하거나 수정하지 않는다. 함수 포인터 혹은 함수 객체 모두 사용가능하다.

 

세 번째 인자 Compare comp 에는 어떤 방식으로 정렬을 하고, min을 선택할 지 직접 사용자가 지정할 수 있도록 가능하게 하는 함수이다.

---

이 함수의 return 값은 함수 max_element와 마찬가지로 Iterator를 반환한다. 따라서, 주소에 담긴값을 알려면 참조 연산자(*)를 사용하면 된다. 또한, 최댓값의 index를 알려면 max_element의 return값에서 배열의 처음 포인터를 빼주면 된다.

 

정리하자면, 범위 [first, last)에서 3번째 인자가 없다면 C++ 상 가장 작은 수의 iterator를 반환하고, 3번쨰 인자가 있다면 사용자가 정해준 정렬 함수상 가장 작은 수의 iterator를 반환한다. 같은 역할을 하는 코드를 작성하면 다음과 같이 작성할 수 있다.

 

// 1. default
template <class ForwardIterator>
  ForwardIterator min_element ( ForwardIterator first, ForwardIterator last ) {
  if (first==last) return last;
 
  ForwardIterator smallest = first;
 
  while (++first!=last)
    if (*first<*smallest)    // min comparison
      smallest=first;
 
  return smallest;
}
 
// 2. custom
template <class ForwardIterator>
  ForwardIterator min_element ( ForwardIterator first, ForwardIterator last ) {
  if (first==last) return last;
 
  ForwardIterator smallest = first;
 
  while (++first!=last)
    if (comp(*first,*smallest)) // custom comparison
      smallest=first;
 
  return smallest;
}

 

쉽게 말해, 가장 작은 놈의 주소값을 알려주는 함수라 생각하면 된다.

 

3. 예시 코드

먼저, max_element / min_element - (1) default를 활용하는 예시를 들어보자.

 

다음 배열 vector<int> nums = {10, 8, 1, 2, 5, 6} 에서 최댓값, 최솟값 및 그 index를 찾는다고 가정하자.

 

max_element, min_element를 활용하면 다음과 같다.

 

#include <iostream>     // cout
#include <algorithm>    // min_element, max_element
#include <vector>         // vector
using namespace std;
 
int main() {
    vector<int> nums = {10, 8, 1, 2, 5, 6};
    
    auto max_it = max_element(nums.begin(), nums.end());
    auto min_it = min_element(nums.begin(), nums.end());
 
    cout << *max_it << endl; // print max element(10)
    cout << *min_it << endl; // print min element(1)
    cout << max_it - nums.begin() << endl; // print index of max element(0)
    cout << min_it - nums.begin() << endl; // print index of min element(2)    
}

 

max_element와 min_element를 사용하였을 때의 코드의 가독성과 길이가 사용하지 않았을 때보다 개선된 모습을 확인할 수 있다.

---

다음으로, max_element / min_element - (2) custom을 사용할 때를 알아보자.

 

만약, pair<int, int> 형과 같은 구조나 내가 정한 구조체에서 원하는 방식에서의 max와 min을 구하고 싶다면? 조금은 다른 방법이 필요하다.

 

C++에서 pair<int, int>를 정렬할 때는 첫 번째 원소를 바탕으로 먼저 정렬한 다음, 두 번째 원소를 비교하는 방식을 사용한다. 만약 두 번째 원소를 바탕으로 정렬한 다음, 첫 번째 원소를 비교하는 방식으로 정렬하고 싶다면, 이때 Compare comp 의 인자로 비교 함수를 넣어주는 것이다.

 

만약, vector<pair<int, int>> = {{2, 10}, {3, 7}, {4, 4}, {5, 1}}에서 두 번째 원소를 기준으로 max를 찾고 싶다면 다음과 같은 방법들을 활용하여 찾을 수 있다.

 

3-1) Using lambda function

람다 함수를 사용하여 임시로 필요한 비교함수를 생성한다면 custom max을 찾을 수 있다.

 

#include <iostream>     // cout
#include <algorithm>    // min_element, max_element
#include <vector>         // vector
using namespace std;
 
int main() {
    vector<pair<int, int>> = {{2, 10}, {3, 7}, {4, 4}, {5, 1}};
    
    auto max_it = max_element(nums.begin(), nums.end(), [](const pair<int, int>& a, const pair<int, int>& b) {
        return a.second < b.second;
    });
 
    cout << *max_it.first << ' ' << *max_it.second << endl; // print max pair(2, 10)
    cout << max_it - nums.begin() << endl; // print index of max pair(0)
}

 

실제 코드를 실행하면 2 10 이란 결과를 얻을 수 있고, index = 0, 즉 1번째 원소가 최댓값을 가진다고 할 수 있다. 

 

3-2) Using function call overloading

혹은 다음과 같이 함수를 따로 작성하거나 함수 객체 및 함수 호출 오버로딩을 활용하여도 같은 결과를 얻을 수 있다.

 

#include <iostream>     // cout
#include <algorithm>    // min_element, max_element
#include <vector>         // vector
using namespace std;
 
bool func(const pair<int, int>& a, const pair<int, int>& b) {
    return a.second < b.second;
}
 
struct myclass {
    bool operator() (pair<int, int> a, pair<int, int> b) {
        return a.second < b.second;
    }
} myobj;
 
int main() {
    vector<pair<int, int>> = {{2, 10}, {3, 7}, {4, 4}, {5, 1}};
    
    auto max_it = max_element(nums.begin(), nums.end(), func);
    auto max_it = max_element(nums.begin(), nums.end(), myobj); // same result
 
    cout << *max_it.first << ' ' << *max_it.second << endl; // print max pair(2, 10)
    cout << max_it - nums.begin() << endl; // print index of max pair(0)
}

 

혹은 accumulate 함수때 설명하였던 <functional.h>에서의 오버로딩을 사용하여도 원하는 방법으로 max와 min을 찾을 수 있다.

 

max_element 및 min_element 함수는 하나씩 배열에 접근하기에 시간복잡도는 배열의 길이인 O(n) 을 가지며, 만약 배열의 범위를 초과하여 index에 접근할 경우 undefined behavior 가 발생할 수 있다. 만약 custom 방법을 사용한다면, 시간복잡도는 O(n*K) (K는 custom 연산의 시간복잡도)라고 쓸 수 있다.

 

도움이 되었다면 지나가는 길에 하트 하나 눌러주세요, 양질의 글을 쓰는데 하나의 동기부여가 됩니다😍

지적이나 오타 수정 댓글 환영합니다!!