구사과

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