우주수첩의 우주먼지

Dynamic Programing recursion + Memoization 단순 테이블 채우기가 아니라 memoization을 이용해서 recursion을 smart하게 하는 기법. # 문제해결 절차 문제를 정확하게 정의하기. 정의된 문제에 대한 subproblem을 생각한 뒤 이를 이용해 reccurence relation을 세운다. A(i)를 해결하기 위해서 이전단위의 subproblem의 solution으로 현재 해결하고자하는 식을 논리적으로 구한다. memoization을 이용하여 recurrence relation 계산 중간 결과물들을 저장할 data structure을 고른다. 대개 n차원 array 사용. Subproblem들간의 dependency를 확인한다. (보통 top-down | ..

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를 이용하는 문제에 국한되어있다. : 탐색, 함..

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

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

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 를 사용하면 더 효율적으로 사용 가능 ..