다음과 같은 참고 자료들이 있으니 같이 보자. 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의 ..
옛날부터 모아오던 문제집인데 이제서야 정리... 대부분 IOI 합숙교육때 봤던 문제들이다. koistudy 1534. 369 마스터http://koistudy.net/?mid=prob_page&NO=1534 수의 개수가 10^8개이다. 단순한 알고리즘으로는 10^8 * lg(10^8) / lg(10) 정도라 아마 TLE가 날 것이다. 하지만 루프가 단순하면 10^8 정도는 무난하게 돌릴 수 있을 테니, 각각의 숫자를 아주 빠르게 판별할 수 있으면 괜찮다.여기서 약간의 전처리를 통해서 판별을 아주 빠르게 할 수 있는데, 100000 미만의 i에 대해서, 해당 수가 369 수인지를 전처리 해두면, 10^10 크기의 수 X는, X / 10^5가 369 수거나 X % 10^5가 369 수이면 369 수이다. 이..
- Total
- Today
- Yesterday