우주수첩의 우주먼지

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

https://onlinejudge.org/index.php?option=onlinejudge&Itemid=8&page=show_problem&problem=1659 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 N | M 의 계산 값이 최대가 되는 L과 U 사..

https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=113&page=show_problem&problem=1323 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 # problem ..

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(