구사과

흔히 비트 DP (Bit DP)라고 하는 거 같다.문제를 읽는데 n이 15~20 정도 되는, 작지만 n!은 아닌 범위가 주어지면 십중팔구 얘. 시간복잡도도 십중팔구 2^n * n or 2^n * n^2. 멀쩡한 dp문제를 기하로 변환해서 푸는 Convex Hull Trick과 함께 가장 변태적인 dp 테크닉 중 하나라고 자부한다.(그래도 얘가 Convex Hull Trick보다는 나은듯...)각설하고. 보통 dp하면 항상 예제로 자주 나오는게 피보나치 함수를 최적화하는 것이다.f(n){if(n == 0) return 0;if(n == 1) return 1; if(memoized) return memo;else return f(n-1) + f(n-2);} 이러한 최적화를 적용시킬 수 있는 이유는 자명하다...

https://www.acmicpc.net/problem/8986 문제 한줄요약 : 를 최소로 하는 x를 구하시오. x를 이진탐색 할 수 있다면 N * lg1e9에 구할 수 있다.그래서 아무 생각없이 이진탐색한다음에 내면 accept 먹일 수 있는데그러라고 낸 문제가 아닐테니, 제대로 해보자. 좌표평면에 저걸 쫙 그려보면 x축과 a[i]/i에서 만나는 직선들이 수두룩하게 쌓여 있을 것이다.저 직선들의 합의 극소값이 하나만 있다는 걸 보이면 된다. 직선들을 싹 더해보자.-inf 어딘가에서 직선의 기울기는 -N(N-1)/2 일 것이다.그런데 첫번째 a[i]/i를 지나고, 두번째 a[i]/i를 지나면서... 점점 기울기가 증가할 것이다.+inf 어딘가에서 직선의 기울기는 N(N-1)/2로 변해있을 것이다.기울..

엄~청 짜기 쉽고 유용한 트리. 유니온 파인드 트리라고만 부르고 있었는데, 서로소 집합이라는 말이 더 나은거 같다. 기본적으로 루트가 하나 있고, 이 루트를 parent로 가지는 노드가 주렁주렁 달린 트리이다. 두가지 연산을 지원하는데, 1. p의 루트를 부르는 find(p) 2. p와 q를 같은 집합에 넣는 union(p,q) 아무 생각없이 짜면int parent[1000], size[1000]; void init(){ for (int i=0; i 4 -> 3 -> 2 -> 1 이런 식으로 트리가 달려있다 치자. 그러면 find(5)를 부르면 4번 정도를 거쳐서 1이 나올 것이다. 이럴 바에 그냥 parent[5] = 1로 압축을 해주면 한번에 갈텐데.. 그래서, find(p)를 부를 때 압축까지 해줄..