구사과

http://geniusainta.com/problems/view/IOI12_scrivener IOI 2012 문제가 너무 신기하고 재밌어 보인다.이거 포함 3문제 풀고 겨학가자 (가능할라나) O(N^2) / 34점헷갈리긴 하지만 하라는 대로 하면 된다풀이 O(NlgN) / 60점 저걸 보면 prev 배열을 상당히 많이 부른다. 이걸 빠르게 해주는 방법이 있다. 처음에 노란 책(프로그래밍 콘테스트 챌린징)에서 봤을때는 응? 했었지만 이번에 직접 짜면서 감탄한 방법. 자료 구조라고 해야 하나... dp라고 해야 하나.. 아마 dp라고 하는게 맞을 거 같다.N^2 풀이에 보면 prev[x]가 있는데 얜 코드를 이해했다면 알겠듯이 "x 앞에 붙어 있는 문자" 이다. 이걸 일반화해보자. "prev[x][k] =..

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가 만약 지름 안에 있다면, 그 점에서 가장 ..