반응형
#####################################
algorithm library
#####################################
1. sort()
int data[10000]
std::sort(data, data+10, myfunction)
arg1 = start position
arg2 = finish position(using loop break)
arg3 = default 오름차순, 함수 지정가능
시간 복잡도 O(NlogN)
2. binary_search()
Bool bol = std::binary_search(v.begin(), v.end(), 3);
시간 복잡도 O(logN)
3. lower_bound() // binary_search 이용
처음 3이 나오는 곳의 위치
IntVector::iterator upperIter = std::lower_bound(v.begin(), v.end(), 3);
int idx = lower_bound(v.begin(), v.end(), 3) - v.begin();
1) len = 5인데 포함되는 값이 큰경우 => index = 5로 나온다
2) len = 0인 경우는 => index = 0이 나온다.
시간 복잡도 O(logN)
4. upper_bound() // binary_search 이용
처음 3이 나오지 않는 곳의 위치
IntVector::iterator lowerIter = std::upper_bound(v.begin(), v.end(), 3);
int idx = lower_bound(v.begin(), v.end(), 3) - v.begin();
시간 복잡도 ONlogN)
3.4) lower_bound(), upper_bound()
컨테이너에서 정렬된 것을 찾을려고 하는경우
1)) compare 함수 선언
bool cmp2(const point& a, const point& b){return a.x < b.x || (a.x == b.x && a.y < b.y);}
idxRight = upper_bound(points, points + N, point(points[mid].x + sqMin, points[mid].y + sqMin), cmp2) - points
2)) compare struct 선언
struct cmp2{ bool operator()(const point& a, const point& b) const{ return a.x < b.x || (a.x == b.x && a.y < b.y); } };
idxRight = upper_bound(points, points + N, point(points[mid].x + sqMin, points[mid].y + sqMin), cmp2()) - points
5. transform
c++ 11에서 lamda가 추가되어서 사용 가능하다. 컴파일러에 따라 사용 불가능
배열의 처음과 끝까지 함수가 정의된것으로 바꿔준다.
1) lamda를 이용
transform(myints, myints+8, myints, [](int i) { return ++i; } );
2) 함수 객체를 이용
int inc(int element){return ++element;}
transform(myints, myints+8, myints, inc );
시간 복잡도 O(N)
6. find 함수
string find와는 다른다는 것을 알아둠
iterator small = find(ball, ball + 4, 1)
int small = find(ball, ball + 4, 1) - ball
시간 복잡도 O(N)
7.reverse 함수
std::reverse(start, end(break));
std::reverse(arr, arr+N);
8. 정렬함수 정리
1. sort
stable 하지 않는 sort이다.
퀵정렬과 힙정렬을 이용하여 구현되어 있음
std::sort(data, data+10, myfunction)
2. stable_sort
stable 한 sort이다.
merge, insert sort를 이용하여 구현되어 있다.
std::stable_sort(v.begin(), v.end(), myfunction);
stable 한 것이 아닌 것보다 조금 느리다.
stable이라는 뜻은 같은 숫자가 존재할때 먼저 나온 index가 먼저 나오게끔 하는 것이다. 즉 ....(3, a) ... (3, b) .... (3, d) ... 정렬 후 a, b, d 순서로 나오는 것을 말한다. 1번은 순서가 그대로 나온다고 보장해 주지 않는다.
3. partial_sort
전체 배열에서 1 ~ K원소까지만 정렬한다.
std::partial_sort(v.begin(), v.begin() + 10, v.end());
4. nth_element
전체 배열에서 정렬이 되었을때의 K번째의 원소만 찾고 그 이전과 이후는 정렬을 보장하지 않는다.
quick_selection 을 이용하여 구현 되어있다.
Avg case : O(N)
Worst case : O(N^2)
std::nth_element(v.begin(), v.begin() + 10, v.end());
9.fill 함수
void fill(first iterator, last iterator, value);
단순히 loop를 도는 것으로 작동한다.
그러므로 memset보다는 느리다. 하지만 안전하다.
시간 복잡도 O(N)
10. equal(first1, last1, first2)
first1 부터 last1전 까지 first1와 first2를 같은지 여부를 확인한다.
11.unique
unique 알고리즘은 입력 시퀀스에서 모든 연속 중복 원소들을 모두 제거한다.
스퀀스 상에서 자신의 왼쪽에 위치한 원소와 값이 동일하면, 그원소는 중복 원소에 해당. remove알고리즘과 마찬가지로 컨테이너의 사이즈를 변경하지 않는다.
시간 복잡도 O(N)
#####################################
vector library
#####################################
1. insert
std::vector<int> myvector (3,100);
std::vector<int>::iterator it;
it = myvector.begin();
it = myvector.insert ( it , 200 ); // it 위치에 200 삽입 다음 iteration이 반환
myvector.insert (it,2,300);
// "it" no longer valid, get a new one:
it = myvector.begin();
std::vector<int> anothervector (2,400);
myvector.insert (it+2,anothervector.begin(),anothervector.end()); 위치에 벡터의 원소를 삽입
int myarray [] = { 501,502,503 };
myvector.insert (myvector.begin(), myarray, myarray+3);
시간 복잡도 O(N) : 자주 사용할 때 조심해라
- erase
iterator erase (const_iterator position);
iterator erase (const_iterator first, const_iterator last);
시간 복잡도 O(N) : 자주 사용할 때 조심해라
#####################################
list library
#####################################
1. erase
iterator erase (const_iterator position);
iterator erase (const_iterator first, const_iterator last);
반환 값 iterator는 삭제한 원소의 다음 것을 리턴한다.
시간 복잡도 O(1)
2. insert
iterator insert (const_iterator position, value);
iterator insert (const_iterator position, size_t, value);
해당 위치에 값을 삽입1), size_t만큼 삽입2)
반환 값은 삽입한 원소의 iterator를 반환한다.
예제) 1, 3, 5인경 iterator가 3을 가르키고 4를 삽입하면 1, 4, 3, 5가 됨
시간 복잡도 O(1)
#####################################
boost library : 그래프 알고리즘 c++
#####################################
나중에 꼭 사용해보자...
#####################################
queue library
#####################################
1. 전처리
#include<queue>
using namespace std;
2. 선언
queue<테이터형> Queue;
3. 삽입
Queue.push(데이터);
4. 참조
변수 = Queue.front();
5. 삭제
Queue.pop();
6. 갯수
변수 = Queue.size();
priority_queue
1.선언
priority_queue<T> max_heap;
priority_queue<T, vector<T>, greater<T>> max_heap;
priority_queue<T, vector<T>, cmp> max_heap;
bool cmp(T a, T b){return a < b;} 정렬과 반대로 만들어주면됨
#####################################
stack library
#####################################
queue 와 거의 동일
#####################################
map library
#####################################
1. 선언
std::map <key_type, data_type, [comparison_function]>
2.find
std::map <string, char> grade_list;
grade_list["John"] = 'A';
if(grade_list.find("Tim") == grade_list.end()){
std::cout<<"Tim is not in the map!"<<endl;
}
3. iterator
std::map <string, char> grade_list;
grade_list["John"] = 'A';
// Should be John
std::cout<<grade_list.begin()->first<<endl;
// Should be A
std::cout<<grade_list.begin()->second<<endl;
#####################################
set library
#####################################
set : 균형 이진 트리로 구현되었다.
#####################################
string library
#####################################
#####################################
iterator library
#####################################
1. std::advance
void advance(iterator &it, distance n)
n번째 원소의 iterator를 it에 집어 넣는다.
시간 복잡도 O(N) : 자주 사용할 때 조심해라
2. std::next
iterator next(iterator &it, distance n = 1)
it을 기준으로 n번째 것의 iterator를 반환한다.
시간 복잡도 O(N) : 자주 사용할 때 조심해라
반응형
