블로그 옮겼습니다

(해싱에 대한 개념은 제 개인적인 생각이 많이 섞여있어서 틀린 내용이 있을 수도 있다는 것을 미리 밝힙니다.) 해싱은 어떤 큰 데이터(스트링, 트리 등)가 있을 때 이 것을 하나의 수로 나타내어 비교를 하기 쉽도록(그리고 빠르도록)할 때 유용하다. 기본적으로 컴퓨터에서 저장할 수 있는 수의 크기의 한계가 존재하기 때문에보통 해시값은 아무리 커도 long long 범위 내에 들어 와야 한다. 그래서 modular 연산을 사용하게 되는데그러면 문제가 생길 수 있는게 서로 다른 데이터 인데 해시값이 같은 경우가 생길 수가 있는 것이다. 그래서 원래의 해쉬테이블은해시값이 단순히 해쉬테이블의 인덱스를 나타내고 그 인덱스에 실제 데이터가 링크드 리스트와 같은 형태로 연결되어서결국 실제 데이터를 찾는 과정이 필요하기..

이 문제는 흔히 가로외 세로의 길이가 같은 격자판에서 각 칸이 검은색 또는 흰색으로 이루어져 있을때 자식이 4개이거나 0개인 트리로 격자를 표현하는 '쿼드 트리' 라는 개념의 변형 문제이다. 격자가 주어졌을때 이 격자를 가장작은 정사각형모양으로 키우고 새로생긴 격자를 흰색으로 채운 뒤 쿼드트리의 노드의 개수를 구하는 것이 첫번째 요구되어지는 것이고 그다음엔 압축된 쿼드트리의 노드 수를 구해야 하는데 압축을 하는 방법은 공통된 서브 트리들을 딱 하나만남겨서 공유하는 것이다. 이렇게 할때 최소한의 노드 수를 사용하도록 압축했을 때의 노드의 수를 구하는 것이 두번째 요구되어지는 답이다. 우선 복잡도 계산을 위해 총 노드 수의 상한을 계산해보자. 격자의 가로 세로 길이는 128이 최대이기 때문에 쿼드트리의 높이..