목록hashing (1)

Doby's Lab

[자료구조] 백준 15829번: Hashing (C++), 해싱 개념, Mod 연산

이번 문제는 50점과 100점으로 나뉘어 채점을 하게 되며 계속해도 100점이 나오지를 않았다. 해싱의 개념과 Mod의 연산을 알아보며 풀어보자. 개념 해싱(Hashing)이란 데이터를 관리하는 비법으로 이분 탐색 혹은 다른 탐색보다 시간 복잡도를 O(1) 안에서 해결할 수 있다. 어떠한 데이터를 저장하려 할 때 그 데이터를 보관하는 곳을 해시 테이블(Hash Table)이라고 한다. 그리고 각 버킷(bucket, 각 행)이 고유한 주소를 가지게 되는데 데이터를 해시 함수(Hash Function)를 통해 데이터를 주소 값으로 바꾸어서 해시 테이블에 저장한다. 각 버킷에 얼마큼 저장할 수 있는 지를 알 수 있는 곳이 슬롯(slot, 각 열)이다. 한 슬롯에 계속 데이터가 들어오면 이를 충돌(Hash Co..
PS/BOJ 2021. 9. 28. 03:46
이전 Prev 1 Next 다음