구사과

http://geniusainta.com/problems/view/APIO14_palindrome 이 문제의 정해는 Manacher's Algorithm + Suffix Array이다.난 전자는 알지만 후자는 모르기 때문에 (...) SA 대신 Hash를 사용해서 풀었다. 때문에 처음부터 해시를 사용했다는 가정 하에 설명한다. unordered_map을 기준으로 설명한다 (괜히 로그떼면 기분 좋으니까 (?)) 1. Naive - O(n^2)substring의 개수가 O(n^2)이며 해싱을 사용하면 팰린드롬 판별은 O(1)에 가능하다. 모든 팰린드롬을 map에 때려박고 개수를 세면 된다. 2. Hash + Manacher + Tree - O(n)일단 한 문자열의 서로 다른 팰린드롬의 개수는 n개임을 알고 ..

https://www.acmicpc.net/problem/5465 격자상에 어떠한 점도 Mecho가 일찍 도착하는 것이 무조건 이득이라는 점을 쉽게 관찰할 수 있다.이는 Mecho가 t만큼 꿀을 빨고 출발했을 때 도착할 수 있다면, t보다 작거나 같은 시간 u만큼 꿀을 빨고 출발해도 항상 도착할 수 있다는 것을 의미한다. 때문에 t의 정의역을 설정해 준 후 Parametric Search를 해주면 문제를 쉽게 풀 수 있다.이제 과제는 시간 t만큼 꿀을 빤 이후에 Mecho가 집에 도착할 수 있는지에 대한 문제로 귀결된다. 먼저, 벌들의 위치를 한꺼번에 Queue에 넣은 다음에 너비 우선 탐색을 할 경우, 한 격자에 도달하기까지 벌이 걸리는 시간을 쉽게 O(n^2) 에 precompute할 수 있다.벌이 ..

http://koistudy.net/?mid=prob_page&NO=593 1. Naive ( O(N^2lgN) ) 트리에 대한 기본적인 지식이 있으면 풀 수 있다. 서브트리의 경우의 수가 N개이니, N개의 각 경우에 대해서 내부에 있는 노드를 Greedy하게 더해서 경비병을 최대화 하면 된다.내부 노드에 있는 cost들을 그때 그때 sort해주면 N^2lgN이다. 2. Naive (...) ( O(Nlg^2N) ) 일단 그때 그때 sort해주기 보다는 priority_queue 등의 자료구조를 사용해서 서브트리에 있는 원소들을 재귀적으로 합쳐주자.이 역시 O(N^2lgN)이 걸린다. 이 때 합치는 대상이 되는 힙을 "가장 원소 개수가 많은 힙" 으로 설정해주자.약간의 커팅.... 은 무슨, 이걸로 시간..

(Homogenic, 1997)

그냥 이번에 코드포스에 나와서.버킷 등의 특별한 자료구조를 안 쓰고 O(Sqrt(N)) 의 시간복잡도를 보이는 테크닉을아는것만... 서술하겠다. 1. http://koistudy.net/?mid=prob_page&NO=1069 Naive하게 코딩했을때 O(QNlgN) 이 나온다. (사실 데이터 약해서 카운팅소트로 된대여... 비밀!)이때 쿼리를 다음과 같이 정렬해보자. (query 구조체는 s,e 값을 가진다) bool cmp(query x, query y){return x.s/SQRT == y.s/ SQRT ? (x.e < y.e) : (x.s < y.s)} start / SQRT 값이 일정할 때 end 값은 단조증가할 것이기 때문에 end의 기준에서는 1 ~ N까지의 원소를 N * SQRT 번 훑게 ..

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

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