구사과

koistudy에서 채점할수 있다. 1. Naive (N^3 + QMlgM) 일단 플로이드로 모든 쌍 최단경로를 구하면 축제지로부터의 distance를 알 수가 있다.그리고, 전체 간선을 축제지로부터의 거리가 큰 순으로 정렬하고, 서로소 집합(union-find tree)를 사용해서 쿼리의 두 정점이 합쳐질때까지 거리 제한을 줄여가면 풀수 있다. 단지 복잡도가 O(N^3 + QMlgM) 이라는 기겁할만한 시간이라 문제지. 플로이드를 다익스트라 * K로 대체할 수 있는데 의미없으니 생략. 2. Dijkstra 한번 쓰기 (QMlgM) naive algorithm을 들여다 본 결과 모든 쌍 최단경로 알고리즘을 쓰라고 만든 문제가 아니라는 건 자명해졌다. 그런데 엄청 쉽게 한번의 다익스트라로 풀수가 있다.그냥..

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