푼지 몇달 된 것도 있고 얼마 전에 푼것도 있다. ONTAK2010. Garden https://www.acmicpc.net/problem/8468 쉽게 생각할 수 있는 아이디어는 N^2개의 행을 잡고, 행 각각에서 교집합을 잡아서 O(N) 루프를 돌리는 것이다. N^3의 끔찍한 시간 복잡도를 가지기에 여기서 포기하기 쉽지만, 놀랍게도 sqrt decomposition을 통해서 큰 차이 없이 N^1.5 정도에 풀 수 있다. 행 R에 대해서, Xi == R을 만족하는 i의 개수가 N^0.5 이상일 경우 heavy row라 하고, 아닐 경우 light row라고 하자. 두가지 방법으로 문제를 해결한다. * 두 행 쌍 중 하나라도 light row일 때를 세주자. light row를 하나 잡고, 고를 수 있는..
다음과 같은 참고 자료들이 있으니 같이 보자. http://web.stanford.edu/class/cs97si/suffix-array.pdf http://web.stanford.edu/class/cs97si/10-string-algorithms.pdf http://blog.myungwoo.kr/57 http://m.blog.naver.com/dark\_\_nebula/220419358547 Suffix Array는 문자열과 부분문자열을 가지고 놀 수 있는 자료구조이다. 이름만 보면 도대체 어디에 쓰는 것인지 잘 이해도 안 가고 왜 배우는 지도 알 수 없을 것이다. 일단, Suffix Array를 통해서 쉽게 풀 수 있는 문제 몇가지를 나열하자면 : * 길이 |S|의 스트링 하나와, Q개의 길이 Ti의 ..
- Total
- Today
- Yesterday