구사과

트리에서 정점 두개를 잡고, 거리를 재본다.n^2 쌍의 개수만큼 거리들이 나올텐데...이 중 가장 거리가 긴 놈을 트리의 지름이라 부른다. dfs 2번 돌려서 O(n)에 해결할 수 있다.알고리즘 문제 해결 전략을 학교에 두고와서 (...) 인터넷에서 직접 찾아봤는데, 책에 있는 것보다 훨씬 우아하고 간결한 알고리즘이 존재했다!! 1. 아무 점이나 잡고(루트), 이 점에서 가장 거리가 먼 점 t를 잡는다.2. t에서 가장 거리가 먼 점 u을 찾는다.3. t - u가 트리의 지름. 끗 여기까지는 좋은데 이를 어떻게 증명하는지가 문제다.인터넷에서 대강 주워들은 걸로 혼자 증명해 보려고 한다. 막가는 증명이니까 믿거나 말거나... 일단 루트에서 가장 거리가 먼 점 t가 만약 지름 안에 있다면, 그 점에서 가장 ..

http://www.jungol.co.kr/prog/Hanal/hanalView.php?qs_code=2796 에서 채점할 수 있다. (File IO를 사용하니 입출력에 유의하라) 3달 전 본선에서 풀려 했을 때는 m^2를 짜고 최적화를 하면 될 줄 알았는데전혀... 그런 풀이가 아니었다 ㅋㅋㅋ나온 다음에, 정렬 하는거 까지는 눈치챘지만 그 이후 아이디어는 잘못 생각했었음.. 얼마 전에 다시 생각해봤는데 풀이는 간단하다.먼저 버스의 시작점 순으로 소트한 다음에, 시작점이 전 원소보다 큰데 끝 점이 전 원소보다 작은 경우는 존재하지 않는다는 것을 알면 된다.결과적으로 실제 버스의 집합은 시작점과 끝 점 모두가 증가하는 형태일 것이다.그렇기때문에 시작점 순으로 버스를 쭉 넣은 다음에... 만약에 현재 버스 ..

http://blog.daum.net/irepublic/7887584 가끔 보면 괴상한 주제 예를 들어 일본 만화영화에 대해 매니아적인 오타쿠적인 사람들이 있습니다. 그사람들이 모여서 이런 저런 정보를 모으는데 보통 사람들이 한번 들어보면 기가질릴정도입니다. 영화의 장면장면을 모두 이야기하고 감독과 성우등 여러가지에 대해 그야말로 모르는 것이 없습니다. 그 런데 여기에 누군가가 끼어들어 니가 오타쿠의 세계를 하느냐며 최고 오타쿠를 자기 맘대로 뽑고 감투도 씌워주고 계급도 만들고 그럽니다. 이럼 다 망하는 겁니다. 오타쿠 본래의 관심사는 사라지고 이젠 자기들을 선발해줄 선발기준이나 감투나 먹고 사는 문제가 주문제가 됩니다. 제일 나쁜 것은 오타쿠도 아닌 사람들이 그거 하면 돈 잘번다면서 끼어드는 겁니다. ..

모든 nlgn들의 영웅(?) 같은 priority_queue존재 그 자체로 멋지지만 정말 멋지게 쓰기 위해서는 제대로 활용할 줄 알아야 할 것이다. 1. Colored By Color Scripter™123456789101112131415161718#include #include using namespace std; priority_queue pq; int main(){ pq.push(3); pq.push(1); pq.push(4); pq.push(1); pq.push(5); pq.push(9); while (!pq.empty()) { printf("%d",pq.top()); pq.pop(); }}출력 결과는 954311 이다. 2.Colored By Color Scripter™12345678910111..

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

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]를 구하고 * 선분..

(koistudy.net / acmicpc.net (Small / Large)) koistudy.net에 N0) 이때. 상태의 에너지는 그 상태가 가지는 값을 뜻합니다. 쉽게 말해 우리가 구하고자 하는 답이죠. 이 문제에서는 뒷면인 동전의 수가 상태의 에너지가 되겠습니다. 담금질 방법은 다음과 같이 작동합니다. (rand()는 0~1 사이의 임의의 난수입니다.) while ( k > 임계 온도 ){E1 = 현재 상태의 에너지 E2 = 랜덤하게 생성한 새로운 상태의 에너지p = exp((E1-E2)/(k*T));if(p > rand()) 현재 상태를 새로운 상태로 바꿈k *= 온도 감률 (보통 0.95 ~ 0.9999 정도) }과연 이런 식으로 해를 구하는 것이 왜 유효한지 case를 나눠서 살펴보도록 하..