우주수첩의 우주먼지

https://onlinejudge.org/index.php?option=onlinejudge&Itemid=8&page=show_problem&problem=351 Online Judge Our Patreons Diamond Sponsors Steven & Felix Halim Reinardus Pradhitya Gold Sponsors --- YOUR NAME HERE ---- Silver Sponsors --- YOUR NAME HERE ---- Bronze Sponsors Christianto Handojo Krzysztof Adamek Fatima Broom Amal Augustine Contribute Bitcoin onlinejudge.org 1

Greedy 선택의 순간마다 당장 눈앞에 보이는 최적의 상황만을 쫓아 최종적인 해답에 도달하는 방법 순간마다 하는 선택은 그 순간에 대해 지역적으로는 최적이지만, 그 선택들을 계속 수집하여 최종적(전역적)인 해답을 만들었다고 해서, 그것이 최적이라는 보장은 없다. # 동작하기 위한 조건 Logical oprimum의 존재 greedy한 방법으로 global optimal solution에 도달 가능하다는 것을 증명 가능해야 함 탐욕적 선택 속성(Greedy Choice Property) : 앞의 선택이 이후의 선택에 영향을 주지 않는다. 최적 부분 구조(Optimal Substructure) : 문제에 대한 최종 해결 방법은 부분 문제에 대한 최적 문제 해결 방법으로 구성된다. # 문제 해결 방법 선택 ..

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..

Divide and Conquer 탐색공간의 전체 혹은 일부를 살펴 봄으로써 원하는 답을 찾는 방법 문제를 나눌 수 없을 때 까지 나누어서 각각을 풀면서 다시 합병하여 문제의 답을 얻는 알고리즘 설계 #Divide 주어진 문제를 작은 단위로 쪼갠다. 이때의 작은 단위는 본 문제와 같지만 입력 값이 작은 문제를 뜻한다 #Conquer 1번에서 나눈 작은 당위들을 recursivley 하게 해결한다 분할이 가능하면 다시 devide를 수행한다. 그렇지 않으면 문제 solve #Combine conquer한 문제들을 통합하여 단위들의 답을 적절하게 조합 해서 본 문제의 답을 제시한다. 경진대회에서 divide and conquer는 대부분 binary search를 이용하는 문제에 국한되어있다. : 탐색, 함..

8x8 체스판에 퀸 8개를 서로 공격할 수 없도록 하는 모든 배치를 구한다. 각 배치는 사전식 순서대로 출력 좌표(a,b) - a번째 row, b번재 column에는 반드시 queen이 위치해야한다. #input TC개수와 퀸을 반드시 배치해야하는 좌표 # SearchSpace를 줄이는 게 관건이므로 불필요한 search를 하지 않기 위해 신경써야 한다. 64개의 칸에 가능한 8개의 을 모두 배치 == ~40억개의 경우의수 하나의 퀸이 하나의 column에만 들어갈 수 있다는 사실을 이용하기. == 8**8~1700만 개의 경우의 수 같은 row에도 두개의 퀸이 존재할 수 없다는 사실을 이용 퀸이(j,i)에 있는 경우 row[i]=j라고 할 때, Row array는 permutation이 될 수 밖에 없..

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

#주된 접근 방법 complete search divide and conquer greedy DP... ex) Input : Size m(

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..