Certi Pro 취득을 위해 꼭 알아야 할 STL Algorithm

지난 포스팅에서는 Pro 취득을 위해 꼭 알아야 할 기본 문법을 알아보았다.

기본 문법 : Certi Pro 취득을 위해 꼭 알아야 할 CPP 기본 문법 (feat. STL)

이번 시간에는 Pro 시험에서 자주 쓰이는 STL Algorithm을 알아보자.

 

[STL Algorithm]

1) Algorithm Library란?

STL에 구현되어 있는 알고리즘은 주로 컨테이너 반복자(배열 주소 값)로 다양한 작업을 수행하도록 도와준다.

반복자 없이 값으로만 수행되는 함수도 있으며, function을 인자로 설정해주기도 한다.

기억에 두면 좋은 것은, range는 항상 [first, last)이라는 것이다. (last 미포함)

 

함수의 형태는 대부분 아래와 같다.

• func(iterator first, iterator last, T value) : find, count, lower_bound, upper_bound
• func(iterator first, iterator last) : sort, max_element, min_element
• func(iterator first, iterator last, function f) : for-each, find_if, count_if, sort
• func(T a, T b) : swap, max, min
• func({ initializer list }) : max, min

 

2) function f를 설정하는 방법

지난 포스팅 [기본 문법]의 마지막 section에서도 언급했듯이, function object를 사용하여 정렬을 하는 경우가 굉장히 많다.

ex) vector를 절댓값 기준으로 오름차순 정렬하는 경우

 

1. naive function

bool comp(int a, int b) {
	return abs(a) < abs(b);
}

2. function object

struct Compare {
	bool operator()(const int a, const int b) const {
    	return abs(a) < abs(b);
    }
} comp;

위와 같이 함수를 정의했다면, vector 자료구조를 가지는 vec에 대해서 sort(vec, vec+n, comp);를 통해 사용자가 지정한 comp 함수로 정렬을 수행할 수 있다.

 

3) Algorithm Library 주요 함수

• sort
• lower_bound, upper_bound
• swap
• max, min, minmax

 

1. sort()

template<class RandomIt>
void sort(RandomIt first, RandomIt last);

template<class RandomIt, class Compare>
void sort(RandomIt first, RandomIt last, Compare comp);

첫 번째 예시는 [first, last) 구간을 comp 기준에 맞게 정렬하는 메서드이다. comp를 명시하지 않으면 operator< 기준에 맞게 정렬된다.

 

vector<int> arr{ 5, 3, -2, 1, -4 };
sort(arr.begin(), arr.end()); // -4, -2, 1, 3, 5
sort(arr.begin(), arr.end(), greater<int>()); // 5, 3, 1, -2,-4

sort에 정렬 함수를 명시하지 않았을 때는 default인 less, 즉 오름차순으로 정렬이 되지만, greater<int>를 명시하면 내림차순으로 정렬되는 것을 확인할 수 있다.

 

2. lower_bound(), upper_bound()

template< class ForwardIt, class T >
ForwardIt lower_bound( ForwardIt first, ForwardIt last, const T& value );

template< class ForwardIt, class T, class Compare >
ForwardIt lower_bound( ForwardIt first, ForwardIt last, const T& value, Compare comp );

lower_bound는 [first, last) 구간에서 comp 기준으로 value보다 크거나 같은 첫 번째 element iterator를 반환한다.

auto it = lower_bound(arr.begin(), arr.end(), 5);라고 쓰면 arr의 처음부터 마지막 구간까지 5보다 크거나 같은 첫 번째 element iterator를 반환한다.

 

upper_bound는 [first, last) 구간에서 comp 기준으로 value보다 큰 첫 번째 element iterator를 반환한다.

auto it = upper_bound(arr.begin(), arr.end(), 5);라고 쓰면 arr의 처음부터 마지막 구간까지 5보다 큰 첫 번째 element iterator를 반환한다.

 

lower_bound와 upper_bound는 부등호가 반대인 것이 아니라 등호가 들어가냐 들어가지 않느냐의 차이이다.

 

추기로, comp가 명시되지 않았을 때는 operator<를 기준으로 동작하며, 정렬된 구간에서만 사용 가능하다.

주로  binary search 문제에서 자주 활용된다.

 

3. swap(), max(), min()

void swap(T a, T b) // a, b의 값을 바꾼다.

T max(T a, T b) // operator< 기준 큰 값
T max(T a, T b, Compare comp) // comp 기준

T min(T a, T b) // operator< 기준 작은 값
T min(T a, T b, Compare comp) // comp 기준

pair<T, T> minmax(T a, T b) // operator< 기준 (first : 작은 값, second : 큰 값)
pair<T, T> minmax(T a, T b, Compare comp) // comp 기준 (Compare requirement 만족)

swap, max, min은 굳이 라이브러리를 쓰지 않아도 구현할 수 있기 때문에 자주 쓰지는 않지만, 코드의 가독성을 높여준다는 점에서는 좋은 것 같다.

 

시험장에서 위의 메서드를 사용하려면, 어떤 헤더를 선언해야 하는지 기억해두어야 한다. 대표적인 헤더는 다음과 같다.

#include <string> // string keyword, string 관련 메서드
#include <algorithm> // max, min, sort, fill
#include <memory.h> // memset, memcpy
#include <cctype> // isdigit, isalpha

추가로, 이 외에도 max_element, min_element, minmax_element / for_each / find, find_if / count, count_if / remove, remove_if 등 다양한 알고리즘이 있지만, Pro 시험에서 자주 쓰이지는 않아 생략한다. 궁금하다면 개인적으로 찾아보는 것을 추천한다.

 

다음 글 : Certi Pro 취득을 위해 꼭 알아야 할 iterator