구사과

엄~청 짜기 쉽고 유용한 트리. 유니온 파인드 트리라고만 부르고 있었는데, 서로소 집합이라는 말이 더 나은거 같다. 기본적으로 루트가 하나 있고, 이 루트를 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)를 부를 때 압축까지 해줄..

http://koistudy.net/?mid=prob_page&NO=521 알고리즘 문제해결 전략에 나온거랑 되게 비슷한 문제다. 그래서 베끼다시피해서 제출했다 문제에 사족이 참 많은데 요약하자면 모든 단어을 사용해서 끝말잇기를 하라 라는 내용이다. 단, 한 단어는 00 ~ 99 낱말 5개 로 구성되었으며, 출력시 사전순으로 가장 앞서는 것을 출력해야 한다. 단어를 꼭지점 (vertex)로 두고 생각하면 백트래킹을 해야 하기 때문에 500000개는 택도 없다. 거기다 지금 이 글의 주제가 한붓그리기이므로, 단어를 방향이 있는 모서리 (edge) 로 두고 한붓그리기를 하는 것이 좋겠다. 즉 단어가 0001020304 이런 식이라면, 00 -> 04로 가는 간선인 것이다. 그러면 V = 100, E 2 ->..

일부 dp문제에서 시간복잡도를 획기적으로 줄여주는 걸로 유명한 테크닉입니다. 이번에 koi 2014 전국본선 3번으로 나왔으니 인지도가 더 올라갈 거 같네요. 개략적으로 설명하자면 문제를 풀다가 이런 형태의 점화식이 나올 때는 보통 n^2 말고는 희망이 없는데 이걸 이런 식으로 해석하면 기울기와 절편이 j에 따라 결정되는 형태의 일차함수들로 해석할수 있게 됩니다.이러면 저러한 dp식을 구할때(dp[0] = 0) 1. 0번 선분을 넣는다 (기울기 = b[0]. 절편 = dp[0]) 2. 현재 들어간 선분 중 최솟값을 찾는다 (dp[1])3. 1번 선분을 넣는다 (기울기 = b[1]. 절편 = dp[1])4. 현재 들어간 선분 중 최솟값을 찾는다 (dp[2])...... 즉, * dp[i]를 구하고 * 선분..