STL 유용한 함수 모음

이진탐색 원소탐색

⚠️이진탐색이므로 오름차순 정렬되어 있어야 함

#include <algorithm>

lower_bound(arr.begin(), arr.end(), 특정값) //찾는 값보다 같거나 큰 숫자가 처음 등장하는 위치 반환
upper_bound(arr.begin(), arr.end(), 특정값) //찾는 값보다 큰 숫자가 처음 등장하는 위치 반환

map

• value 기준으로 정렬
  map 값 vector에 저장 ➡️특정 기준에 의해 vector 정렬
  ⚠️compare 함수 작성할 때 인자로 주소값 넘겨주기 !

map<int, int> m;
vector<pair<int, int>> v(m.begin(), m.end());
sort(v.begin(), v.end(), compare);

bool compare(pair<int, int> &a, pair<int, int> &b) {
    return a.second > b.second; //이 경우는 내림차순 정렬
}

문자열

• 문자열 삽입/삭제

str.insert(2, "abcde");
str.erase(인덱스, 크기)

• 문자열 뒤집기

#include <algorithm>
reverse(str.begin(), str.end());

• 문자열에 특정 문자열이 있는지
  🛑 strstr이 find()보다 시간 효율👍🏻

#include <string.h>
strstr(s.c_str(), p.c_str()) //있으면 해당 위치의 포인터(char*) 반환, 없으면 NULL return

s.c_str() //string -> char*

• 문자열에서 특정 문자 찾기

str.find(array[i]); //str에서 array[i] 찾기
					//있으면 index, 없으면 string::npos를 return

• 문자열 분리
  방법 1 : stringstream 사용 ➡️공백으로 문자열 분리해서 자동으로 자료형에 맞게 추출

#include <sstream>
    
char c;
int num;
stringstream ss("a 123");

ss >> c >> num;

  (참고) stringstream 사용하면서 구분자로 문자열 분리하는 방법
  ⚠️tmp가 string이어야 하고, 리턴 타입 역시 string이라 형 변환은 직접 해야 함 !

string str = "abc,123";
stringstream ss(str);
string tmp;

while (getline(ss, tmp, ',')) {
		cout << tmp << endl;
}

  방법 2 : find( ), substr( ) 사용

vector<string> split(string s, string target) {
	vector<string> v;
	int start = 0;
	int t = s.find(target);
	
    while (t != string::npos) {
		v.push_back(s.substr(start, t-start)); //첫번째 문자 위치, 부분 문자열 길이
		start = t+1;
		t = s.find(target, start);
	} 
	v.push_back(s.substr(start, s.size()-start));

	return v;
}

int main() {
	vector<string> v = split(s, ",");
    
	return 0;
}

• 대소문자 변환

str[i] = toupper(str[i]); //대문자로
str[i] = tolower(str[i]); //소문자로

• 부분 문자열 비교

str.substr(start, length); //시작 위치, 문자열 길이

vector

⭐find, erase 함수 사용해서 인덱스 팍팍 접근하기

• 특정 원소 찾기

// vector
#include <algorithm>
if(find(v.begin(), v.end(), 특정값) != v.end()) {
	cout << "exist!";
}
int index = find(v.begin(), v.end(), 특정값) - v.begin()


// 배열
#include <algorithm>
if(find(arr, arr + 배열크기, 특정값) != arr + 배열크기) {
	cout << "exist!";
}
int index = find(arr, arr + 배열크기, 특정값) - arr

• 특정 원소 삽입/삭제
  ⚠️ erase는 원소 삭제해도 iterator가 그대로 있어서 for문에서 역순으로 접근하기

v.insert(v.begin() + i, val);
v.erase(v.begin() + i);

• 원소의 합
  ⚠️ 인자인 first Iterator는 이상이고, last Iterator 미만 ➡️last에는 마지막 요소의 다음 위치를 가르키는 iterator

#include <numeric>
accumulate(v.begin(), v.end(), 0) //시작, 끝, 초기화 값

• 초기화
  ⚠️v.empty()는 비어있는지 확인하는 함수

v.clear();

memset은 0으로 초기화할 때만 써야 함. 이외의 값은 fill 사용하던지, 직접 초기화

#include <string.h>
memset(arr, 0, sizeof(arr)) //이름, 초기화 값, 크기

• 최댓값 / 최댓값 인덱스 찾기

#include <algorithm>

///vector
int max = *max_element(v.begin(), v.end());
int max_index = max_element(v.begin(), v.end()) - v.begin(); //"*" 없음에 주의

///배열
int max = *max_element(arr, arr + 배열크기);
int max_index = max_element(arr, arr + 배열크기) - arr; //"*" 없음에 주의

• vector 이어붙이기

vec1.insert(vec1.end(), vec2.begin(), vec2.end());

• 중복 제거
  오름차순 정렬 후, 사용

#include <algorithm>
sort(vec.begin(), vec.end());
vec.erase(unique(vec.begin(),vec.end()), vec.end());

정렬

#include <algorithm>
sort(v.bigin(), v.end());

sort ( )

• 첫 번째 원소가 같을 경우, 두 번째 원소의 입력 순서대로 출력한다는 보장이 없다.
• 동일한 값에 대해 기존 순서가 뒤바뀔 수 있다.
• 예측이 불가능한 불안정 정렬

stable_sort ( )

• 첫 번째 원소가 같을 경우, 두 번째 원소의 입력 순서대로 출력을 보장한다.
• 동일한 값에 대해 기존 순서가 보장된다.
• 예측 가능한 안정적 정렬

• 내림차순 정렬
  sort(v.bigin(), v.end(), greater<>());

• 정렬 기준 만들기

bool compare(const pair<int, string>& a, const pair<int, string>& b) {
	return a.first < b.first;
}
                             
sort(v.bigin(), v.end(), compare);

• 정렬 기준 여러개 일 때 : 구조체 선언하고, compare 함수 작성

배열 자리 바꾸기

#include <algorithm>
swap(a[i], a[i+1]);

순열과 조합 : 브루트포스, 완전탐색

• nPn
  오름차순 정렬 후, 사용 : 앞에는 탐색하지 않기 때문에 모든 경우 탐색하려면 정렬해야 함
  do-while문 이용

#include <algorithm>
sort(str.begin(), str.end());

do {
	cout << str << endl;
} while(next_permutation(str.begin(), str.end()));

• nPr (순서 다른 걸 각각의 경우로)
  r개 뽑고, 뒷부분 reverse 해주기

  12345➡️ 12354➡️ 12435➡️ ⋯ ➡️ 12543➡️ 13245
  
  12345에서 두 개만 뽑으면 (12)345-> (12)354-> (12)435 이런 식으로 되는데
  12-> 13 이렇게 되도록 하려면 뒷 부분을 reverse 해서 12543으로 만들고, 바로 다음인 (13)245가 나오도록 해야 함
  
  ☑️ next_permutation이 작은 수는 탐색하지 않는다는 성질 이용 !

do {
		for (int i = 0; i < r; i++) {
			cout << v[i] << " ";
		}
		cout << '\n';
		reverse(v.begin() + r, v.end());
	} while (next_permutation(v.begin(), v.end()));

• nCr (순서 고려 안 함)
  보조순열 이용
  5C2면 1 1 0 0 0 이런 식으로
  보조순열로 next_permutation하면서 출력만 원래 배열로 하는 것

for (int i = 0; i < r; i++) {
	tmp.push_back(1);
}
for (int i = 0; i < n-r; i++) {
	tmp.push_back(0);
}

sort(tmp.begin(), tmp.end());
do {
	for (int i = 0; i < tmp.size(); i++) {
		if (tmp[i] == 1)
			cout << v[i] << ' ';
	}
	cout << '\n';
} while (next_permutation(tmp.begin(), tmp.end()));

math

#include <cmath>

• 반올림

round(num);

• 거듭제곱
  ⚠️return값 double형 !
  2의 거듭제곱은 간단하게 비트 시프트 연산으로도 가능 !

double result = pow(2, 10); //2의 10승