기본STL정리

시간복잡도 - 보통 반복문이 결정, Big-O 표기법 사용

컴퓨터는 1초에 약 1억번(10^8) 연산 가능

tip!) 입력이 커질 때 사용 => ios_base::sync_with_stdio(false); cin.tie(NULL);

       c++에서는 개행문자로 endl사용 but 너무 느림 ∴ 대신 '\n' 사용

 

STL(Standard Template Library)

PS에서 C++을 쓰는 이유

PS에서 자주 쓰이는 여러 자료구조, 알고리즘등이 구현되어 있음

-vector, stack, queue, set, map, string등의 자료구조

-최댓값, 최솟값, 이분탐색, 엄청 빠른 정렬등의 알고리즘

 

Sort 

기본적으로 오름차순 정렬, 퀵 정렬을 기반으로 함, 최악의 경우에도 O(NlogN)보장

#include<Algorithm> 헤더에 존재, O(NlogN)정렬

ex) sort(first_num, last_num(first_num+n)) or sort(num, num+n, greater<int>()); // greater<int>() => compare comp

• 선택 정렬
• 버블 정렬
• 삽입 정렬
• 퀵 정렬
• 병합 정렬
• 힙 정렬

 

Pair

#include<Algorithm>

pair<data type, data type> ex) pair<int, int> p; 

두 가지 값을 묶어서 관리 => ex) p.first = a; p.second = b;

 

String

#include<string>

ex) string s; s.length();

 

Vector

#include<vector>

크기가 가변적으로 변하는 배열

ex) vector<int> v; //크기가 0인 int벡터

vector<int> v(n); //크기가 n인 int벡터 0으로 초기화

vector<int> v(n,-1); //크기가 n인 int벡터 -1로 초기화

n*m 이차원 벡터 => vector<vector<int> > v(n, vector<int>(m)); 

v.size(), v.resize(n), v.emplace_back(a), v.pop_back(), v.begin(), v.end()