유용한 내장 함수 추천(C++, 알고리즘, 백준)

vector와 관련해서 내장 함수들을 매우 많다. 일반적으로, sort 함수는 대부분 사용한다.

 

 

 

하지만, sort 함수이외에도 훌륭한 내장함수들이 많다.

 

 

 

- std::binary_search

- std::upper_bound

- std::lower_bound

- std:equal_range

 

 

 

위의 4가지 함수들은 매우 유용하게 사용될 것이다. 시간복잡도와 예제를 아래에서 설명하도록 하겠다.

 

 

 

---

 

 

1. std::binary_search

// binary_search example
#include <iostream>     // std::cout
#include <algorithm>    // std::binary_search, std::sort
#include <vector>       // std::vector
 
bool myfunction (int i,int j) { return (i<j); }
 
int main () {
  int myints[] = {1,2,3,4,5,4,3,2,1};
  std::vector<int> v(myints,myints+9);                         // 1 2 3 4 5 4 3 2 1
 
  // using default comparison:
  std::sort (v.begin(), v.end());
 
  std::cout << "looking for a 3... ";
  if (std::binary_search (v.begin(), v.end(), 3))
    std::cout << "found!\n"; else std::cout << "not found.\n";
 
  // using myfunction as comp:
  std::sort (v.begin(), v.end(), myfunction);
 
  std::cout << "looking for a 6... ";
  if (std::binary_search (v.begin(), v.end(), 6, myfunction))
    std::cout << "found!\n"; else std::cout << "not found.\n";
 
  return 0;
}

2, 3. std::upper_bound, std::lower_bound

// lower_bound/upper_bound example
#include <iostream>     // std::cout
#include <algorithm>    // std::lower_bound, std::upper_bound, std::sort
#include <vector>       // std::vector
 
int main () {
  int myints[] = {10,20,30,30,20,10,10,20};
  std::vector<int> v(myints,myints+8);           // 10 20 30 30 20 10 10 20
 
  std::sort (v.begin(), v.end());                // 10 10 10 20 20 20 30 30
 
  std::vector<int>::iterator low,up;
  low=std::lower_bound (v.begin(), v.end(), 20); //          ^
  up= std::upper_bound (v.begin(), v.end(), 20); //                   ^
 
  std::cout << "lower_bound at position " << (low- v.begin()) << '\n';
  std::cout << "upper_bound at position " << (up - v.begin()) << '\n';
 
  return 0;
}

// equal_range example
#include <iostream>     // std::cout
#include <algorithm>    // std::equal_range, std::sort
#include <vector>       // std::vector
 
bool mygreater (int i,int j) { return (i>j); }
 
int main () {
  int myints[] = {10,20,30,30,20,10,10,20};
  std::vector<int> v(myints,myints+8);                         // 10 20 30 30 20 10 10 20
  std::pair<std::vector<int>::iterator,std::vector<int>::iterator> bounds;
 
  // using default comparison:
  std::sort (v.begin(), v.end());                               // 10 10 10 20 20 20 30 30
  bounds=std::equal_range (v.begin(), v.end(), 20);            //          ^         ^
 
  // using "mygreater" as comp:
  std::sort (v.begin(), v.end(), mygreater);                   // 30 30 20 20 20 10 10 10
  bounds=std::equal_range (v.begin(), v.end(), 20, mygreater);  //        ^         ^
 
  std::cout << "bounds at positions " << (bounds.first - v.begin());
  std::cout << " and " << (bounds.second - v.begin()) << '\n';
 
  return 0;
}

이 함수는 upper_bound와 lower_bound의 혼합해서 만들어진 함수이다.

 

 

 

 

이 함수를 통해서, 만약에 찾는 값이 벡터의 원소로 존재한다면 구간(bounds.second, bounds.first)을 알 수 있다. 

 

 

 

 

시간복잡도는, 2 * log(v.size())다.

 

 

 

---

 

 

위의 함수들을 통해서 조금 더 나은 코드를 작성할 수 있을 것이다.