우주수첩의 우주먼지

Bit-Parallel Algorithm | 비트 병렬 알고리즘 반복문 등을 비트연산자를 이용항 연산으로 변형하여 수행하는 기법 비트연산은 다른 연산들에 비해 매우 빠르지만, 사용할 수 있는 범위에 한계가 있으므로 반드시 입력범위 확인이 필요하다 Complete Search나 DP 등에서 비트연산을 사용하지 않는 경우 간혹 timeout이 발생할 때가 있다. == 모든 subject에 대한 값을 구해야 하는 경우 # 예시 1. Hamming Distance 길이가 같은 두 bit string a,b가 있을 때, a와 b 사이의 hamming distance( hamming(a,b) )는 a와 b의 symbol이 일치하지 않는 위치의 개수이다. (같은 위치에 있는 symbol끼리 비교) ex) String..

Complete Search 탐색 공간의 전체 혹은 일부를 살펴봄으로써 원하는 답을 찾는 방법 # 사용 경우 더 나은 해결방법이 존재하지 않을때 입력 크기가 작아서 complete search만으로 충분히 제한시간 안에 답을 낼 수 있을 때 문제 풀이 예시) - [UVa] 750 : 8 Queens Chess Problem | C++

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