array
- 고정된 크기를 가진 자료구조
- 시간복잡도
탐색 : O(1)
삽입/삭제 : O(n)
array<int, 3> arr = {1,2,3,4,5};
set - 정의 및 시간복잡도
1. set
set<int> my_set = {1,2,3,4,5};- 중복을 허용하지 않는 자료구조
- red-black tree구조로 되어있어 정렬이 되어있다.
- 시간복잡도
탐색 : O(logN)
삽입/삭제 : O(logN)
2. hash set(unordered_set)
unordered_set<int> my_unordered_set = {1,2,3,4,5};- 중복을 허용하지 않고 해쉬를 이용하기 때문에 정렬이 되어있지 않지만 탐색, 삽입, 삭제가 O(1)인 자료구조
- 시간복잡도
탐색 : O(1)
삽입/삭제 : O(1)
3. multiset
multiset<int> my_unordered_set = {1,2,3,4,5};- 중복을 허용하는 자료구조
- set의 특성을 가짐
- 시간복잡도
탐색 : O(logN)
삽입/삭제 : O(logN)
set - 문법
1. 삽입, 삭제
set<int> mset;
mset.insert(2);
mset.insert(3);
mset.insert(4);
mset.erase(3);
2. 순회
set<int> mset;
//전위순회
for (int i=0; i<mset.size(); i++) {
cout<<*next(mset.begin(),i)<<endl;
}
//후위순회
for (int i=1; i<=mset.size(); i++) {
cout<<*prev(mset.end(),i)<<endl;
}
map
1. map
map<int, int> my_map- set에서 key, value를 추가한 형태
- 시간복잡도
탐색 : O(logN)
삽입/삭제 : O(logN)
2. hash map
unordered_map<int, string> my_hash_map;- hash로 구성된 map. 시간복잡도가 1이다
- 시간복잡도
탐색 : O(1)
삽입/삭제 : O(1)
3. multi map
multimap<int, string> myMultimap = {{1,"One"}, {2,"Two"}, {3,"Three"}};- map과 유사하며 중복을 허용한다.
- 시간복잡도
탐색 : O(logN)
삽입/삭제 : O(logN)
list(liked list)
list<int> my_list;- 데이터를 저장할 때 다음 데이터의 위치도 같이 저장하는 리스트
- 시간복잡도
탐색 : O(n)
데이터 삽입/삭제 : O(1)
vector - 정의 및 시간복잡도
vector<int> v;- 동적 array
- 시간복잡도
탐색 : O(n)
데이터 삽입/삭제 : O(n) (* 단 끝에 삽입, 삭제시 O(1))
vector - 문법
1. 삽입,삭제
vector<int> v;
value=10
// i번째 index에 삽입
v.insert(v.begin()+i,value);
// 맨 끝에 삽입
v.push_back(value)
// i번째 인덱스 삭제
v.erase(v.begin()+i)
2. 순회
// [전위순회]
// 1. for문
for (int x : v) printf("%d ", x);
// 2. index
for (int i = 0; i < v.size(); i++) printf("%d ", v[i]);
// 3. iterator
for (auto it = v.begin(); it != v.end(); ++it) printf("%d ", *it);
// [후위순회]
// 1. index
for (int i = v.size() - 1; i >= 0; i--) printf("%d ", v[i]);
// 2. reverse it
for (auto it = v.rbegin(); it != v.rend(); ++it) printf("%d ", *it);
// 3. it
for (auto it = v.end(); it != v.begin(); --it) printf("%d ", *it);
priority queue - 정의 및 시간복잡도
priority_queue<int, vector<int>, greater<int>> max_pq;
// default이기 때문에 priority_queue<int> max_pq 만 써도 된다
priority_queue<int, vector<int>, greater<int>> min_pq;- 최댓값 or 최솟값을 root노드에 두어 즉시 접근할 수 있는 자료구조
- 시간복잡도
탐색 : O(n)
데이터 삽입/삭제 : O(logN) (* 단 끝에 삽입, 삭제시 O(1))
priority queue - 문법
1. 삽입/삭제
priority_queue<int> max_pq;
//삽입
max_pq.push(1);
max_pq.push(2);
max_pq.push(3);
//삭제
max_pq.top(); //루트노드 값 반환
max_pq.pop(); //루트노드 값 삭제