정렬
15가지 정렬 알고리즘 시각화 : https://www.youtube.com/watch?v=kPRA0W1kECg&t=1s&ab_channel=TimoBingmann
*stl sort, stable_sort
stl sort는 O(nlogn)의 시간복잡도를 가지는 정렬이다. 하지만 입력 순서는 보장하지 않는다. 이를 보완하는 것이 stable_sort이다.
*stl sort로 내림차순 정렬하기
기본적으론 오름차순 정렬이다. 만약 내림차순 정렬을 하고 싶다면 다음의 4가지 방법이 있다.
1. greater<int>() [from functional]
sort(s.begin(), s.end(), greater<int>());
2. reverse() [from algorithm]
sort(s.begin(), s.end());
reverse(s.begin(), s.end());
3. bool operator
struct
{
bool operator()(int a, int b) const
{
return a < b;
}
} comp;
sort(s.begin(), s.end(), comp);
4. lambda expression
sort(s.begin(), s.end(), [](int a, int b) {
return a > b;
});
*완전 탐색
브루트 포스 : for + if로 모든 경우를 탐색
비트 마스크
순열
DFS/BFS
주로 재귀적 호출을 사용함
*이분 탐색
탐색하고자 하는 구역을 계속 둘로 쪼개가며 탐색하는 방법
굉장히 빠르지만 미리 정렬이 되어있어야 한다.
*binary_search
이분 탐색을 사용한다. 데이터의 유무를 확인할 수 있다. return값은 bool.
*upper_bound / lower/bound
upper_bound : value보다 작지 않은 첫 iterator
lower_bound : value보다 큰 첫 iterator
*next_permutation
말 그대로 다음 순열을 찾는 함수
*count
count(a.begin(), a.end(), 4); : a에 4가 몇 개 있는지 return
count_if(a.begin(), a.end(), [](int x) {return x%2==0;}); : 조건에 맞는 원소의 개수 return
엑셀의 count 함수와 닮아있다.
*find, find_if
해당 원소의 위치 / 해당 조건의 원소 위치 반환
못 찾으면 end return
*fill
fill(a.begin(), a.end(), 0); //a를 0으로 채움
container 초기화 시에 사용 가능
*swap
두 값을 바꾼다. 변수부터 구조체까지도 바꿀 수 있다.