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

이번 문제는 50점과 100점으로 나뉘어 채점을 하게 되며 계속해도 100점이 나오지를 않았다.

해싱의 개념과 Mod의 연산을 알아보며 풀어보자.

---

개념

 해싱(Hashing)이란 데이터를 관리하는 비법으로 이분 탐색 혹은 다른 탐색보다 시간 복잡도를 O(1) 안에서 해결할 수 있다. 

어떠한 데이터를 저장하려 할 때 그 데이터를 보관하는 곳을 해시 테이블(Hash Table)이라고 한다.

그리고 각 버킷(bucket, 각 행)이 고유한 주소를 가지게 되는데 데이터를 해시 함수(Hash Function)를 통해 데이터를 주소 값으로 바꾸어서 해시 테이블에 저장한다.

각 버킷에 얼마큼 저장할 수 있는 지를 알 수 있는 곳이 슬롯(slot, 각 열)이다. 한 슬롯에 계속 데이터가 들어오면 이를 충돌(Hash Collision)이라고 한다. 충돌이 많이 일어나면 나중에 검출 속도가 느려지기 때문에 최대한 골고루 여러 버킷에 들어갈 수 있도록 해야 한다.

만약에 슬롯이 3이고 어떤 한 버킷의 슬롯에 데이터가 3만큼 차서 꽉 차있는데 여기에 데이터가 한 번 더 들어오면 어떻게 될까?

그것을 오버플로(overflow)라고 한다.

그래서 해싱에서 제일 중요한 건 여러 버킷에 데이터들이 골고루 들어가게 해주는 해시 함수(Hash Function)이다.

 

Mapping이나 정적 해싱 등 다른 관련 개념들도 있지만 문제를 이해하는 데에 있어 필요한 부분만 설명하고, 다음 해싱 관련 문제에서 알아보자.

---

해시 함수

이번 문제에서 해시함수는 문자열을 받으면 첫 문자부터 a는 1, b는 2로 취급하여 각 항을 가지고 1번째 항은 31의 0 제곱, 2번째 항은 31의 2 제곱으로 각 항을 곱해준다. 그리고 1234567891(소수)로 나눈 나머지 값을 인덱스(주소)로 가지게 된다.

+ 해시 함수에서 제산법(나누기)에 해당할 때, 소수로 나눠주는 것이 효율적이다.

 

그래서 처음에 코드를 짰을 때는 이랬다.

#include <iostream>
#include <vector>
#include <cmath>
#define ll long long
using namespace std;

int main() {
	int n;
	cin >> n;
	ll sum = 0;
	for (ll i = 0; i < n; i++) {
		char a;
		cin >> a;
		ll b = a - 96;
		ll cnt = i;
		while (cnt > 0) {
			b *= 31;
			cnt--;
		}
		//b *= pow(31, i);
		sum += b;
	}
	cout << sum % 1234567891;
	return 0;
}

이러면 50점이 나오게 되는데 문자열의 길이가 최대 50이라 마지막에 (1~26 사이의 수)(31의 50 제곱)이 발생하면 엄청 큰 수가 나와서 처리를 못 해내기 때문이다. 이 때는 수학적인 영역이 필요하다.

---

MOD의 연산

나머지 연산은 다음과 같은 특징을 갖는다는 것을 알고 있어야 이번 문제를 풀 수 있었다.

1. (a + b) mod n = {(a mod n) + (b mod n)} mod n

2. (a - b) mod n = {(a mod n) - (b mod n)} mod n

3. (a * b) mod n = {(a mod n) * (b mod n)} mod n

#include <iostream>
#include <vector>
#include <cmath>
#define ll long long
#define MOD 1234567891
using namespace std;

int main() {
	ll n;
	cin >> n;
	ll sum = 0;
	for (ll i = 0; i < n; i++) {
		char a;
		cin >> a;
		ll b = a - 96;
		ll cnt = i;
		while (cnt > 0) {
			b *= 31;
			cnt--;
			if (b > MOD) {
				b %= MOD;
			}
		}
		//b *= pow(31, i); // 결과 값이 커지면 ~~*e+~~ 형식으로 나오는 거 같아서
		sum += b;
	}
	cout << sum % MOD;
	return 0;
}

그래서 b가 MOD를 넘어갈 때마다 MOD로 나누어 주었다.

왜냐하면 기존의 코드에서는 각 항 b에 조건에 맞는 31의 몇 제곱을 해주어 sum에 더해주었다.

즉, sum % 1234567891 = (b + b + b + b....) % 1234567891이었다.

하지만 그럴 필요 없이 sum%1234567891 = {(b % 1234567891) + (b % 1234567891) + (b % 1234567891) +....} % 1234567891로 바꾸어 계산하면 큰 값 때문에 오류가 날 일 없이 100점을 맞을 수 있다.

---

해싱을 알게 되었다. (어떻게 돌아가는지만)

MOD(나머지) 연산을 알게 되었다.

 

+참고

https://sedangdang.tistory.com/4

[C] 백준 | 15829번 코드 - Hashing

https://jaimemin.tistory.com/1445

백준 15829번 Hashing