해싱 썸네일형 리스트형 BOJ)14965 Lozinke 문제: icpc.me/14965 n개의 문자열이 주어질 때, 모든 문자열 s에 대해, s의 substring 중에 현재 보는 문자열을 제외한 나머지 문자열이 되는 개수를 전부합하여 출력하는 문제이다. 직접 비교하면 n^2으로 시간초과를 보게된다. 문자열의 길이가 10이하라는 사실을 이용하여 모든 문자열 s를 해싱해준 뒤 마찬가지로 모든 문자열의 substring을 전부 해싱하여 set과 map을 이용하여 개수를 계산해주면 n*10*10*logn의 시간에 문제를 해결할 수 있다. 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758#include #include #in.. 더보기 BOJ)14577 일기예보 문제:icpc.me/14577 4가지 종류의 질의가 들어오는 문제이다. 지역 수 가 N 질의의 수가 M일 때 N,M이 10만까지 들어오므로 적어도 질의 하나당 log 시간에 해결해줘야 한다. 결국 3,4번 질의를 로그시간에 답해줘야 하는데 구간에 대한 질의이므로 우선 세그먼트 트리를 생각해낼 수 있다. 하지만 좌표 자체에 업데이트를 할 경우 좌표의 범위부터가 감당이 안된다. 그렇기 때문에 우리는 한 지역에 쌓일 수 있는 눈의 양에 업데이트를 해야한다. 나올 수 있는 눈의 양은 3번 쿼리의 경우 2개 1,2번 쿼리의 경우 1개 일 뿐이니 최대 2*M개 뿐이기 때문이다. 말을 어렵게 표현했는데 우선 쿼리를 오프라인으로 처리할거다. 모든 쿼리를 받은 뒤에 해당 질의 때 마다 나올 수 있는 모든 눈의 양을 저장.. 더보기 이전 1 다음