skeksk91   9년 전

아 이렇게 하는거구나라고 느끼고 딱 떨어지는 설명

개인적으로 정말 도움이 많이 됬습니다. ㅋㅋ

adream   9년 전

Good

h0ngjun7   9년 전

제가 해싱에 대해서 연재하고 있습니다! ㅋㅋㅋㅋ

august14   9년 전

음?

h0ngjun7   9년 전

@august14 전 올해 인터넷 예선 G번 해싱으로 푼 거, 나머지 연산 때문에 해싱값을 페어나 튜플로 들고다니면 TLE나던데 어떻게 그렇게 짧고 빠르게 해싱으로 짜셨죠?

h0ngjun7   9년 전

@august14 https://www.acmicpc.net/problem/3033 이 문제도 해싱으로 시도해봤는데... 해싱값을 튜플로 구해서 시간 안에 겨우 맞췄네요ㅠㅠ 해싱하는 법 공유해주세요!

august14   9년 전

나머지 연산을 하지말고 long long으로 그냥 연산하면 자연적으로 모듈러가되서 매우 빨라집니다.

august14   9년 전

그리고 set말고 unordered_set를 사용하면 찾는 속도가 더 빨라져요!

august14   9년 전

@hongjun7

그리고 저런식으로 해시를 하면 안됩니다. long long으로 하면 mod 2^64랑 같은데 4진법으로 하면 안되고 2^64와 서로소인 수의 진법으로 해야 최소한의 안전을 보장 할 수 있습니다 저는 257진법에 그냥 아스키코드를 사용했습니다.

1

100 100

GAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA

AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA

를 넣으면 0이 나와야 할텐데 collision이 발생해서 1이 나와요 데이터가 약했군요

h0ngjun7   9년 전

오! 좋은 지적 감사합니다 ㅎㅎ 곧 수정하겠습니다!

댓글을 작성하려면 로그인해야 합니다.