![[백준] 15829 Hashing](https://img1.daumcdn.net/thumb/R750x0/?scode=mtistory2&fname=https%3A%2F%2Fblog.kakaocdn.net%2Fdn%2FdvOha4%2FbtrJgxO3rLM%2F1YBc2JmiYoB10YnvCkvZzk%2Fimg.png)
해싱을 적용하는 문제로, 솔직히 쉬운 축에 속하는 문제이다. 이 문제 자체에서만큼은 자료형만 무작정 키워도 100점을 맞을 수 있고, 인터넷에 찾아보면 모듈러 연산의 성질로부터 정말 쉽게 푸는 방법들이 많다.
나도 처음엔 50점만 맞아서 뭐지 하고 온갖 방법으로 시도했었고, 그중에서 인터넷에 찾아봐도 딱히 나오지 않은 방법이 하나 있어서 포스팅해보려고 한다. 이 방법은 솔직히 말하면 쓸데없이 복잡하니 심심한 사람이 아니라면 다른 블로그에서 풀이법을 찾아보길 바란다.
hash값이 $(\sum_0^{L-1}{a_ir^i})\,\bmod\,M$인데, 문제에서 주어진 $L,\,r$값으로 무작정 계산하면 일반적인 int 자료형의 크기를 넘어선다. 더 큰 자료형을 써도 되겠지만, 만약 $L$이 매우 커진다면 제대로 작동하지 않을 것이다. 그렇기에 어떤 $L$값이 입력되어도 작동할 수 있는 알고리즘을 고안해야 한다.
먼저, small size에서만 작동하는 간단한 알고리즘을 생각해보자. $\{a_i\}$이 이미 주어져 있을 때, 아래와 같은 알고리즘이 가장 먼저 떠오를 것이다.
hashVal = 0
for i in 0...(L - 1)
hashVal = hashVal + a[i] * r^i
hashVal = hashVal % M이 알고리즘의 가장 큰 문제점은 3번째 줄에 있다. $L$값이 증가하여 어느 순간부터 overflow가 일어나게 된다. $r^i$값을 계산하는 시점에서 overflow가 발생하는 것이다. 그러니 우리는 $r^i$값을 계산하지 않고도 $(\sum{a_ir^i})\,\bmod\,M$값을 계산해야 한다.
쉽게 생각해볼 수 잇는 접근 중 하나는, 모든 loop를 지나며 합한 값에 모듈러 연산을 적용하는 기존의 방식이 아니라, 매 loop마다 적당히 작은 단위의 값이 계산되어 해당 값들을 더하면 최종 해시값이 도출되는 알고리즘이다. 특히 $r^i\,\bmod\,M$의 값으로 $r^{i+1}\,\bmod\,M$의 값을 계산할 수 있는 알고리즘이 반가운 상황이다.
다음의 수식을 생각해보자.
$$ a_ir^i=P_iM+(a_ir^i\,\bmod\,M) $$
$P_i$는 $a_ir^i$를 $M$으로 나눈 몫이 된다. 그 다음 항은 자연스럽게 나머지가 되고, 이를 $H_i=a_ir^i\,\bmod\,M$이라 하자.
여기서 다음의 수식을 증명해야 한다.
$$ (\sum(a_ir^i)\,\bmod\,M=(\sum{H_i})\,\bmod\,M $$
이는 다음과 같이 보일 수 있다.
$\sum{a_ir^i}=\sum(P_iM+H_i)=M\sum{P_i}+\sum{H_i}$인데, $(N\pm kM)\,\bmod\,M=N\,\bmod\,M$이므로(직관적이므로 증명하지 않는다), $(\sum{a_ir^i})\,\bmod\,M=(\sum{H_i})\,\bmod\,M$이다.
따라서 우리는 매 loop마다 $H_i$를 계산하여 적당히 작은 값들의 합으로 hash를 구할 수 있게 된다. $H_i$는 어떻게 구할 수 있을까? $H_i=a_ir^i-P_iM=a_ir^i-floor(a_ir^i/M) \times M$의 수식대로 계산하면 되는 걸까?
이미 앞서서 $r^i$을 계산하면 안됨을 얘기했다. 우리는 작은 단위의 계산에서 $H_i$값을 구해야 한다. 이를 위해 몇 가지 새로운 도구를 도입해야 한다. 첫째로 $x$의 소수부를 구하는 함수 $f(x)$이다.
$$ f(x) := x -floor(x) $$
이 $f(x)$의 성질 중 $a\,\bmod\,c=f(a/c)\times c$ 라는 것이 중요하다. 둘 째로, $r^i$의 $M$에 대한 나머지 $h_i$이다.
$$ h_i = r^i\,\bmod\,M=f(r^i/M)\times M $$
$H_i$랑 다름에 유의하자. $H_i$는 $a_ir^i\,\bmod\,M$이고, $h_i$는 $r^i\,\bmod\,M$이다.
이 두 가지 도구를 활용하면 $H_i$를 다르게 표현할 수 있다.
$$ H_{i+1} = a_{i+1}r^{i+1}\,\bmod\,M=f(a_{i+1}r^{i+1}/M)\times M = f(a_{i+1}r\cdot{r^i\over M})\times M $$
여기서 $f(x)$의 또 다른 성질을 이용한다.
$ x = \text{floor}(x) + f(x),\,y = \text{floor}(y) + f(y) $ 에서
$ xy =$ $\text{floor}(x)\cdot\text{floor}(y)$ $+$ $\text{floor}(x)\cdot f(y)$ $+$ $\text{floor}(y)\cdot f(x)$ $+$ $f(x)\cdot f(y) $ 이고
$ f(xy) = f(\text{floor}(x)f(y)+\text{floor}(y)f(x) + f(x)f(y)) $ 이다.
$x=a_{i+1}r,\,y=r^i/M$으로 두면, $f(a_{i+1}r\cdot{r^/M})=f(\text{floor}(a_{i+1}r)f(r^i/M)+f(a_{i+1}r)\text{floor}(r^i/M)+f(a_{i+1}r)f(r^i/M))$이고, $a_{i+1}r$이 정수이므로 $f(a_{i+1}r)=0,\,\text{floor}(a_{i+1}r)=a_{i+1}r$이다. 따라서
$$ f(a_{i+1}r\cdot{r^i\over M})=f(a_{i+1}r\cdot f({r^i\over M})) $$
위에서 확인했듯, $h_i=f(r^i/M)\times M\Leftrightarrow f(r^i/M)=h_i/M$이다.
최종적으로 $H_{i+1}=f(a_{i+1}r\cdot h_i/M)\times M$이다. 여기서도 아직 해결되지 않은 문제가 있는데, $h_i$를 계산해야한다는 것이다. $f(r^i/M)$으로 계산하기에는 $r^i$을 구해야 하므로 불가하다. $h_i$는 점화식의 형태로 풀어내야 한다.
$h_i=r^i\,\bmod\,M$이므로, $r^i=Q_iM+r^i\,\bmod\,M=Q_iM+h_i$로 표현할 수 있다. 여기에 $r$을 곱하면 아래와 같다.
$$ r\cdot r^i=r^{i+1}=rQ_iM+rh_i=Q_{i+1}M+rh_{i+1} $$
$rh_i>M$일 수 있으므로 $rh_i=h_{i+1}$이라 하기 힘들다. 다만 $h_{i+1}=r^{i+1}\,\bmod\,M$이므로
$$ r^{i+1}\,\bmod\,M=(rQ_iM+rh_i)\,\bmod\,M=rh_i\,\bmod\,M=h_{i+1} $$
이 된다.
위 식으로부터 우리는 $r^i$과 같은 큰 수를 다루지 않고서도 $h_i$를 계산할 수 있고, 이로부터
$ H_i=f(a_ir\cdot{h_{i-1}\over M})\times M $
$ \,\,=f(a_ir{rh_{i-1}\,\bmod\,M\over M})\times M $
$ \,\,=[a_ir(rh_{i-1}\,\bmod\,M)]\,\bmod\,M $
임을 알 수 있다.
이 식은 $a_i,\,r,\,h_i$ 등 작은 단위의 수로만 이루어진 계산이다.
이를 알고리즘으로 작성하면 아래와 같다.
h[0] = 1
hashVal = 0
for i in 1...(L-1)
h[i] = (r * h[i - 1]) % M
hashVal = hashVal + (a[i] * r * h[i - 1]) % M
hashVal = hashVal % M
위와 같은 로직으로 답을 구할 수 있다. $a_i$의 최댓값이 26이고, $h_i$의 최댓값이 $M-1$이다. 즉, $a_irh_{i-1}\le26\times31\times1234567890$인데, 이는 int의 범위를 벗어난다. 따라서 변수들을 long int 정도로만 설정해주면 된다.
또, 위 알고리즘에서 마지막 라인의 모듈러 계산 부분을 loop 안으로 넣어주면 hashVal도 overflow할 가능성을 없애므로 아무리 큰 $L$값이 입력되어도 해시값을 계산할 수 있다.
코드 결과물에 비해 설명이 장황했다. 서두에 설명했지만 이것보다 더 좋은 방법이 많다. 다만 이렇게 쓸데없이 수식을 떡칠하면서 풀어낼 수도 있다고 글을 써보고 싶었다..ㅋㅋ;
C++ 답안 코드는 아래와 같다.
#include <iostream>
int main() {
long int r = 31;
long int M = 1234567891;
long int L;
std::cin >> L;
char *S = new char[L];
int a;
long int *h = new long int[L]; // r^i 에 대한 나머지
long int *H = new long int[L]; // a_i*r^i에 대한 나머지
std::cin >> S;
a = static_cast<long int>(S[0]) - 96;
h[0] = 1;
H[0] = a;
long int hashVal = a % M;
long int pow = 1;
for(int i = 1; i < L; i++) {
pow *= 31;
a = static_cast<int>(S[i]) - 96;
h[i] = (r * h[i - 1]) % M;
H[i] = (a * r * h[i - 1]) % M;
hashVal += H[i];
}
hashVal %= M;
std::cout << hashVal << std::endl;
}