우주수첩의 우주먼지

https://cses.fi/problemset/task/1676/ CSES - Road Construction cses.fi #include #include using namespace std; const int N = 200001; class UFDS { private: vector p, rank, setSizes; int numSets; public: UFDS(int N) { numSets = N; rank.assign(N, 0); p.assign(N, 0); for (int i = 0; i < N; i++) p[i] = i; setSizes.assign(N, 1); } int findSet(int i) { return (p[i] == i) ? i : p[i] = findSet(p[i]); } bo..

Union-FInd 그래프 알고리즘 중 하나로 여러 노드가 존재할 때, 선택한 두 노드가 서로 같은 그래프에 속하하는지 판별하는 알고리즘. disjoint set들을 관리하기 위한 data structure makeset(x) : 단일 element x로 이루어진 set을 하나 생성한다. find(x) : x가 포함된 set을 return한다. union(x,y) : x가 포함된 set과 y가 포함된 set을 하나의 set으로 합친다. union-find는 각 set을 rooted tree로 관리하고, 각 tree의 root를 대표 element로 지정한다. 각 대표 element는 rank를 가지고 있다. rank는 해당 tree의 height로 정의하며, union 시 rank가 작아지는 쪽으로 un..

Priority Queue 들어간 순서에 상관없이 우선순위가 높은 데이터가 먼저 나오는 것 일반적인 큐(Queue)는 First in-First Out (어떤 부가적인 조건 없이 먼저 들어온 데이터가 먼저 나감) 구조이다. priority queue는 모든 연산을 O(log n)에 지원하는 binary heap으로 구현 insert : element 추가 find : priority가 가장 높은 element 반환 delete : priority가 가장 높은 element 제거 top : priority가 가장 높은 element를 반환 pop : priority가 가장 높은 element를 제거 # priority가 높다 priority가 integer일때 C++은 가장 큰 숫자(max-heap bas..

Map pair를 관리하기 위한 data structure set과 마찬가지로 c++에서는 red-black tree로 map library를 구현하기에 searching 과 update 모두 O(log n)시간 에 수행 가능하다. Map에서 각 key는 반드시 unique해야하며 C++에서는 중복된 key값을 허용하는 multimap library를 따로 지원한다. unordered_set과 마찬가지로 c++에서는 hash table로 구현 된 unordered_map library 또한 지원한다. # example map m; m["monkey"] =4; m["banana"] =3; cout

Set 집합을 관리하기 위한 data structure Set library는 중복을 허용하지 않는다. C++에서는 set library가 balanced binary search tree (== red-black tree)로 구현되어 있기 때문에 기본적인 searching과 update 모두 O(log n) 시간에 수행 가능하다. c++에서는 set의 element간에 순서가 정해지지 않은 경우 사용할 수 있는 unorderd_set_library를 지원한다. 이는 hash table로 구현되어 있으며 모든 연산을 average O(1)에 구현 가능하다 근데 이제 경진대회에서는 쓰지 않음을 곁들인... #include 헤더파일 include 진행 namespace 를 사용하면 더 효율적으로 사용 가능 ..

https://codeforces.com/problemset/problem/1092/B Problem - 1092B - Codeforces codeforces.com # JAVA import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.IOException; import java.io.InputStreamReader; import java.io.OutputStreamWriter; import java.util.*; public class Main { public static void main(String args[]) throws IOException{ BufferedReader br = new BufferedReader(n..

# Stack (FILO) push: 끝부분 (stack top)에 원소를 추가 pop : 끝부분의 원소를 제거 == Stack top의 원소 반환 모두 평균 O(1) stack s; s.push(2); // 2 s.push(5); // 2 5 cout

Deque 양 끝 부분에 원소를 추가, 삭제를 평균 O(1)시간에 할 수 있는 자료구조 push_back : 끝부분에 추가 pop_back : 끝부분 삭제 push_front : 처음 부분에 추가 pop_front : 처음부분 삭제 insert : 중간에 추가 O(n) Doubled linked list에 비해서 access가 빠르다는 장점이 있다. 근데 링크드 리스크 자체를 경진대회에서 거의 안쓴다는 왈ㄹ랄라가 있지. #include // 헤더 파일 스윽 써주께에 deque d; d.push_back(5); //5 d.push_back(2); //5 2 d.push_front(3); // 3 5 2 d.pop_back(); // 3 5 d.pop_front();// 5

Vector 일반적인 dynamic array와 비슷하게 사용 가능하다. push_back : 맨 마지막 위치에 원소를 삽입 pop_back : 맨 마지막 위치의 원소를 삭제 위의 두 연산을 평균 O(1)시간에 수행 가능. insert : 원하는 위치에 element를 삽입 O(n)시간 소모. #include // 헤더파일 스윽 써주께에 vector v; v.push_back(3); // v : [3] v.push_back(2); // v : [3, 2] v.push_back(5); // v : [3, 2, 5] vector a(8) // size : 8, initial value == 0 vector b(8,2) // size : 8, initial value == 2 # Vector 에 있는 모든 원..

사이즈가 n인 array A가 있다. 해당 array의 inversion의 개수를 출력하는 프로그램을 작성하여라. #그냥 구현하기 #include #include using namespace std; int main(void) { int arr[10] = { 4,5,6,2,3,10,8,1,9,7 }; int inversion_count = 0; for (int i = 0; i arr[j]) inversion_count++; } } cout arr[j + 1]) { temp = arr[j + 1]; arr[j + 1] = arr[j]; arr[j] = temp; inversion_count++; } } }..