• 5 min read

stl[2] - Algorithm 헤더 Part 1

알고리즘을 위한 STL

std::Vector를 사용해 iterator를 사용할 수 있게 되었기 때문에, 이제 이 iterator를 입력으로 받는 수많은 함수들을 사용할 수 있습니다.

어떤 알고리즘들이 미리 구현되어져있는지 확인하고, 사용해보도록 하겠습니다.

Reference

Algorithms library - cppreference.com
cppreference.com

Table Of Contents

  • swap()
  • fill()
  • sort()
  • unique()
  • vector::erase()
  • reverse()
  • max(), min(), minmax()
  • max/min_element()

Table Of Contents - Part 2

  • lower_bound()
  • upper_bound()
  • binary_search()
  • merge()
  • next_permutation()
  • prev_permutation()

함수들

swap()

두 원소의 위치를 교환하는 명령어입니다.

swap(a,b);
swap(V[0], V[i]);
swap(V.begin(), V.rbegin());

등의 사용법이 존재하며 이중 세 번째인 iterator를 사용한 swap 연산은 추후
Convex Hull + Rotating Calipers 알고리즘의 템플릿 구현에 사용되고는 합니다.

아래와 동일한 역할을 합니다

//swap(a,b)

int tmp = a;
a = b;
b = tmp;

fill()

값을 채워주는 연산입니다.

C 언어의 memset() 함수와 비슷한 역할을 하지만, 비트단위로 넣는 값이 아니기 때문에 아무런 값이나 넣을수 있습니다.
( memset()은 사실상 0과 -1 정도로만 초기화 가능합니다. )

대신 "조금" 느립니다. 시간복잡도는 O(N).

vector<int> V(10);
fill(V.begin(), V.end(), 10); // 10으로 초기화

배열 전체를 초기화할때 사용할 수 있습니다.

sort()

배열을 정렬합니다.

기본적으로 오름차순으로 정렬되며, greater<typename T1>() Functor 를 붙여 정렬할 경우 내림차순 정렬이 가능합니다.

bool cmp 함수를 직접 작성해서 넘겨줄 수도 있습니다.

bool cmp(int A, int B){
  return A>B;
}

vector<int> V;
sort(V.begin(), V.end());
sort(V.begin(), V.end(), greater<int>());
sort(V.begin(), V.end(), cmp);

unique()

배열에서 중복된 값을 분리해냅니다.
unique()를 사용하기 위해서는 배열이 미리 정렬되어 있어야 함에 주의해야 합니다.

Vector::erase() 와 함께 사용해서 좌표압축, 중복값 제거 등에 사용합니다.

시간복잡도는 O(N) 이며, unique 연산 후에는 중복된 N(N>=2) 번째 값들을 배열의 최후미로 보냅니다.

iterator를 반환하는데, 최후미로 밀려난 중복된 값들의 시작점입니다.

vector::erase()

배열에서 특정한 위치, 범위의 값을 삭제합니다.

앞선 unique와 함께 사용하여 중복된 값을 삭제하는데에 주로 사용합니다.
[start, end) 범위의 값을 삭제합니다.
시간복잡도는 O(N).

vector<int> V = {1,2,3,4,5,5,6,7,8,1,5};
V.erase(unique(V.begin(), V.end()), V.end());

이 중복 삭제와 lower_bound를 묶어서 사용할 경우, 플래티넘 이상의 알고리즘 문제에서 자주 사용하는 기법인 좌표 압축 문제를 해결할 수 있습니다.

18870번: 좌표 압축

reverse()

배열의 순서를 반대로 뒤집습니다.

내림차순 정렬을 하고 싶은데 greater<>() Functor가 기억나지 않는다면 사용할 법 합니다.

vector<int> V;
reverse(V.begin(), V.end());

min, max, minmax()

원소들 중에서 최댓값을 찾습니다,

minmax() 함수의 경우에는 최댓값과 최솟값을 동시에 반환하는데, 이때 자료형은 pair<> 에 담겨 나옵니다. [s,e] 구간에서 s와 e가 뒤바뀔수 있는데, 이때

if(e<s) swap(s,e);

// or

// using structured-bindings
auto [s2,e2] = minmax(s,e);

structured-bindings를 같이 사용한 minmax 구문을 사용하는것이 편리하고 직관적입니다.

또한, min/max/minmax를 아래와 같이 중첩하는 경우가 있는데,

int mx = max(a,max(b,max(c,d)));

아래와 같이 작성하는것이 훨씬 깔끔하게 처리됩니다
min/max/minmax의 경우 list 입력도 처리 가능합니다.

int mx = max({a,b,c,d});

min_element, max_element()

min, max와 기본적인 동작은 동일합니다만, "배열"에서 최댓값을 뽑아냅니다.
시간복잡도는 O(N)입니다.
반환형이 iterator 이므로 값에 접근하기 위해서는 * 연산자를 사용해야 함에 유의해야 합니다.

vector<int> V;
int mn = *min_element(V.begin(), V.end());

[s,e) 구간에서 최대/최소값을 찾아줍니다.

해결 가능한 문제들

거의 대부분의 문제들에서 이러한 개념들을 사용하고 있기 때문에, 정말 수많은 문제에 사용할 수 있습니다.
다음 Article인 Part 2의 내용들과 조합하시면 Silver I ~ Silver V 난이도 대의 이분탐색 및 원소를 찾는 유형의 문제들을 손쉽게 해결하실 수 있습니다.

추천 글

featured