구사과

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)를 부를 때 압축까지 해줄..

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