[C++ STL] algorithm.h

원소를 수정하지 않는 작업들

 

for_each

Windows에서 이거 쓰지말라고 한다

짧게 쓰고 싶으면 이렇게 쓰라네 

 

vector<int> x(10);

for( int y : x ){ cout << x << "\n"; }

for( int &y : x){ y = 1; }

for( auto &y : x ){ y = 10; }

 

find O(N)

왜 O(logN)이 아닌지 물어보았다

find_if

count O(N)

---

순열

 

next_permutation

prev_permutation

---

원소를 수정하는 작업들

swap

transform O(N)

 

replace

fill

remove

reverse

rotate

---

파티션

특정 조건을 만족하는 원소들은 앞으로 보내고 나머지들은 뒤로 보내는 작업을 말합니다.

partition

---

정렬

1. sort  O(N*logN)

// 사용예시
sort(vec.begin(),vec.end(),compare);

 

true 일때 첫번째 인자를 우선이라 판단한다

즉 첫번째 인자를 두번째 인자보다 앞에 배치한다

 

bool compare(int a, int b) {
    return a > b;
}

ssort(myVector.begin(), myVector.end(), compare);

즉, 이거는 a가 더 크면 true 이고 앞에 배치하므로 

이건 내림차순 정렬인거다.

 

내부적으로는 퀵소트로 구현되어 있다

사실 퀵소트 최악의 경우가 O(N^2)인데

이걸 팀소트인가 뭐랑 합체해서 구현한거라 N*LOGN 으로나온다

---

이진탐색

 

lower_bound O(logN)

upper_bound O(N*logN)

binary_search O(logN)

이진탐색(이분탐색)

범위를 1/2 절반으로 줄여가며 탐색하는 O(logN) 의 탐색 방법

vector deque list set map 등 선형자료구조가 아닌 자료구조에도 적용가능하다

반드시 해당 자료구조가 정렬상태여야한다!

 

---

병합

merge

---

집합 관련 함수

includes

set_union

set_intersection

set_difference

---

HEAP 관련

push_heap

pop_heap

make_heap

sort_heap

is_heap

---

최대최소

min

max

min_element

max_element