백준 링크 : https://www.acmicpc.net/problem/15829

문제 개요

$$ H=\sum^{i-1}{i=0}a{i}r^{i} \bmod M $$

입력으로 문자열이 들어오는데 위의 점화식을 이용해서 해쉬함수를 구현하고, 해쉬함수를 통해 해쉬값을 출력하는 문제이다.

아이디어

• 점화식을 반복문과 곱셈 연산, 나머지 연산 등을 통해 구현한다.

  • 점화식을 의사코드로 표현하면 아래와 같다.

    string s;
    
    for(i : s)
    	ret += a[i] * pow(r, i)
    ret = ret % M;
    

주의사항

• 값을 연산하는 과정에서 오버플로우가 발생한다. 이것은 나머지 연산자의 성질을 통해 해결해야 한다.

  $$ (a\pm b)\ \%\ c = (a\ \%\ c \pm b\ \%\ c)\ \%\ c \\ (a\ *\ b)\ \%\ c = (a\ \%\ c\ * b\ \%\ c)\ \%\ c $$

• 나머지 연산으로 값을 제한하더라도, 연산 과정의 중간 값이 21억을 넘는 경우가 생기므로, long long형을 사용해서 오버플로우를 방지한다.

// 아래의 코드는 dev c++환경에서 동작됩니다.
// visual studio에서는 bit/stdc++.h가 기본적으로 없기 때문에
// 정삭적인 작동이 되지 않을 수 있습니다.
#include <bits/stdc++.h>
using namespace std;

#define hash ksjdfi
int l, a, ratio;
string s;
long long M = 1234567891, hash, r = 1;

int main()
{
    ios::sync_with_stdio(NULL); cin.tie(NULL); cout.tie(NULL);
	cin >> l;
	cin >> s;

	for(int i = 0; i < s.length(); i++)
	{
		a = s[i] - 'a' + 1;
		hash += (a * r) % M;
		hash %= M;
		r = (r * 31) % M;
	}
	cout << hash;
    return 0;
}

후기

처음에는 나머지 연산에 대한 성질을 잘 몰라서 50점밖에 못맞았다. 언제 한 번 정수론도 배워야 하는데 앞으로 배워야 할 것들이 너무 많아서 시간이 걸릴 것 같다.

그냥 필요한 지식이 나올때마다 그 때 배운다는 생각으로 접근해야할 것 같다.