cgiosy.dev

처음으로 참가한 대학생 대회이자, 첫 팀 대회이자, 다른 PS러를 자의로(ㅋㅋ) 만난 첫 대회이다. 대회 직후에 바로 후기 써야지 했는데 힘들어서 다음 날로 미루고, 또 미루다가 이제서야 쓴다 ㅎㅎ; 기본적인 팀 설명 등은 지난 예선 후기에 작성했기 때문에 생략한다. 팀원인 주때의 후기도 함께 보면 좋을 듯. 팀노트 본선 대회를 하루 남겨둔 저녁, 위기감을 느낀 우리는 어떻게든 팀노트를 만들기 시작했다. 코드를 전부 우리가 다 짰으면 좋았겠지만, 팀노트는 한 페이지도 완성 안 돼있고 대회가 코앞인 상황에 그럴 시간은 없었다. 일단 예전에 짜둔 내 코드 30%, 주때의 작년 팀인 Longest path to WF의 팀노트, kactl에서 코드를 열심히 수혈받아왔다. 특히 출제자 목록을 보고 플로우는 꼭 넣..

아래에서 $N$은 테이블에 저장된 키 개수, $M$은 테이블 크기를 의미한다. $N$개의 키에 대한 해시값이 모두 $M$ 미만이고 distinct하다면, 즉 해시가 Perfect Hash Function이면 단순히 크기 $M$의 배열 각각에 키에 대한 값을 저장하면 된다. Perfect Hash Function을 사용하는 해시 테이블은 보통 FKS 해싱 기반인데, 이에 대해선 여기서 설명하지 않겠다. 그보단 대체로 xxHash나 wyhash처럼 매우 빠르며 충분히 랜덤함을 보장하는 해시 함수를 쓰게 된다. 문자열의 특정 부분만 뽑아 쓰는 해시도 있긴 한데, 이 글에선 해시 함수가 서로 다른 키에 대해 완전히 랜덤한 출력을 보장함을 가정한다. 생일 문제에 의해, $N = \sqrt{M}$ 정도만 돼도 테이..