구사과

Maximum Subarray Problem을 선형 시간에 푸는 방법은 다음과 같다.(원래 0 ~ n-1을 선호하지만, 이번에는 부분합을 써야 해서 1 ~ n으로 배열 인덱스를 설정하겠다.) Colored By Color Scripter™123456789101112131415#include #include using namespace std; int max_sum(int *a, int n){ int cmax = 0, res = 0, qmax = *max_element(a+1,a+n+1); if(qmax

트리에서 정점 두개를 잡고, 거리를 재본다.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를 짜고 최적화를 하면 될 줄 알았는데전혀... 그런 풀이가 아니었다 ㅋㅋㅋ나온 다음에, 정렬 하는거 까지는 눈치챘지만 그 이후 아이디어는 잘못 생각했었음.. 얼마 전에 다시 생각해봤는데 풀이는 간단하다.먼저 버스의 시작점 순으로 소트한 다음에, 시작점이 전 원소보다 큰데 끝 점이 전 원소보다 작은 경우는 존재하지 않는다는 것을 알면 된다.결과적으로 실제 버스의 집합은 시작점과 끝 점 모두가 증가하는 형태일 것이다.그렇기때문에 시작점 순으로 버스를 쭉 넣은 다음에... 만약에 현재 버스 ..