본문 바로가기

백준일지14

[C++] STL 알고리즘: Sort 정렬 알고리즘  O(n^2)1. selection sort(선택 정렬) : [i, n] 범위를 훑으며 가장 작은 원소를 v[i]에 대입하는 걸 반복2. insertion sort(삽입 정렬) : [1, i) 범위가 정렬되어있을 때 v[i]를 앞의 i - 1개의 원소 사이에 끼워넣음3. bubble sort(버블 정렬) : v[i - 1] > v[i]인 경우 swap해주는 걸 n번 반복함 O(n^2) 정렬 알고리즘은 비교적 구현이 간단하고 n ​정렬 알고리즘 O(nlogn)1. merge sort(병합 정렬) : 최악의 경우도 O(nlogn)이라 STL 없이 구현할 때 좋음2. heap sort(힙 정렬) : 최악의 경우도 O(nlogn)이라 STL 없이 구현할 때 좋음3. quick sort(퀵 정렬) .. 2024. 9. 13.
[C++] STL 자료구조: bitset bool 자료형은 0 또는 1을 저장하지만, 1byte = 8bit의 저장공간을 사용한다. 이유는 cpu가 자료형을 할당할 때 바이트 단위로 주소를 지정하기 때문이다​bitset은 이렇게 낭비되는 7bit를 없애기 위해서 0, 1을 하나 당 1bit에 저장하는 자료형이다. bitset을 bool []이나 vector 대신 이용하면 메모리를 1/8만 사용하면서 여러 유용한 기능을 사용할 수 있다.​bitset은 연속된 메모리 공간을 잡아둔 뒤, 비트 연산을 통해 bit 단위로 값들을 저장하는 방식으로 구현되어있다.​메모리 공간의 각 칸들은 구현마다 다르겠지만 보통 32bit 또는 64bit로 이루어져있으며, 따라서 32 또는 64개의 bitset 칸들을 연산 하나로 한 번에 처리할 수 있다. 이런 이유로 .. 2024. 5. 10.
[C++] STL 자료구조: Pair, Tuple pair, tuple은 여러 개의 자료형을 묶어서 관리할 수 있게 해주는 편리한 자료형이다. 보통 2개의 자료형을 함께 다뤄야하면 pair를, 3개 이상을 다뤄야 하면 tuple을 사용한다. ##Pair 예시 1using pii = pair; //자주 사용하는 조합은 별칭으로 생성해도 된다.int main() { fastio; pii a; // a = { 0, 0 } pii b(1, 2); // b = { 1, 2 }; 2개가 쌍으로 pair c{ "HI", 3.14 }; // c = { "HI", 3.14 }  cout first second cout   vector v; v.push_back(a); v.push_back({ 3, 4 }); v.push_back(make_pair(5, 6));  fo.. 2024. 5. 9.
[C++] STL 자료구조: unordered_set, unordered_map - 이름에서 알 수 있듯이 내부 원소들이 정렬되어있지 않다는 점에서 unordered_set, unordered_map은 set, map과 차이점이 있다.- ​unordered_set, unordered_map은 내부적으로 hash table을 사용해 구현되어있다.hash table은 삽입, 삭제, 검색을 지원하며 hash table의 특징 상 연산의 시간복잡도는 평균 O(1), 최악의 경우 O(n)이다. 이는 BBST로 구현된 set, map의 연산이 O(logn)인 것과 비교했을 때 평균적으로 더 좋다.- 또한 unordered_set, unordered_map은 set, map과 마찬가지로 원소가 중복될 수 없다. 만약 중복된 원소를 사용하고 싶다면 unordered_multiset, unorder.. 2024. 5. 9.

티스토리툴바