15829) Hashing

15829

제목 : 스티커

• APC에 온 것을 환영한다. 만약 여러분이 학교에서 자료구조를 수강했다면 해시 함수에 대해 배웠을 것이다. 해시 함수란 임의의 길이의 입력을 받아서 고정된 길이의 출력을 내보내는 함수로 정의한다. 해시 함수는 무궁무진한 응용 분야를 갖는데, 대표적으로 자료의 저장과 탐색에 쓰인다.

  이 문제에서는 여러분이 앞으로 유용하게 쓸 수 있는 해시 함수를 하나 가르쳐주고자 한다. 먼저, 편의상 입력으로 들어오는 문자열에는 영문 소문자(a, b, …, z)로만 구성되어있다고 가정하자. 영어에는 총 26개의 알파벳이 존재하므로 a에는 1, b에는 2, c에는 3, …, z에는 26으로 고유한 번호를 부여할 수 있다. 결과적으로 우리는 하나의 문자열을 수열로 변환할 수 있다. 예를 들어서 문자열 “abba”은 수열 1, 2, 2, 1로 나타낼 수 있다.

  해시 값을 계산하기 위해서 우리는 문자열 혹은 수열을 하나의 정수로 치환하려고 한다. 간단하게는 수열의 값을 모두 더할 수도 있다. 해시 함수의 정의에서 유한한 범위의 출력을 가져야 한다고 했으니까 적당히 큰 수 M으로 나눠주자. 짜잔! 해시 함수가 완성되었다. 이를 수식으로 표현하면 아래와 같다.

  \[H=\sum_{i=0}^{l-1}a_i \mod M\]

  해시 함수의 입력으로 들어올 수 있는 문자열의 종류는 무한하지만 출력 범위는 정해져있다. 다들 비둘기 집의 원리에 대해서는 한 번쯤 들어봤을 것이다. 그 원리에 의하면 서로 다른 문자열이더라도 동일한 해시 값을 가질 수 있다. 이를 해시 충돌이라고 하는데, 좋은 해시 함수는 최대한 충돌이 적게 일어나야 한다. 위에서 정의한 해시 함수는 알파벳의 순서만 바꿔도 충돌이 일어나기 때문에 나쁜 해시 함수이다. 그러니까 조금 더 개선해보자.

  어떻게 하면 순서가 달라졌을때 출력값도 달라지게 할 수 있을까? 머리를 굴리면 수열의 각 항마다 고유한 계수를 부여하면 된다는 아이디어를 생각해볼 수 있다. 가장 대표적인 방법은 항의 번호에 해당하는 만큼 특정한 숫자를 거듭제곱해서 곱해준 다음 더하는 것이 있다. 이를 수식으로 표현하면 아래와 같다.

  \[H=\sum_{i=0}^{l-1}a_ir^i \mod M\]

  보통 r과 M은 서로소인 숫자로 정하는 것이 일반적이다. 우리가 직접 정하라고 하면 힘들테니까 r의 값은 26보다 큰 소수인 31로 하고 M의 값은 1234567891(놀랍게도 소수이다!!)로 하자.

  이제 여러분이 할 일은 위 식을 통해 주어진 문자열의 해시 값을 계산하는 것이다. 그리고 이 함수는 간단해 보여도 자주 쓰이니까 기억해뒀다가 잘 써먹도록 하자.

• 입력 : 첫 줄에는 문자열의 길이 L이 들어온다. 둘째 줄에는 영문 소문자로만 이루어진 문자열이 들어온다.

  입력으로 주어지는 문자열은 모두 알파벳 소문자로만 구성되어 있다.

• 출력 : 문제에서 주어진 해시함수와 입력으로 주어진 문자열을 사용해 계산한 해시 값을 정수로 출력한다.

• small (50점) : $ 1<= l <= 5$

• Large (50점) : $ 1<= l <= 50$

문제의 요는 이렇다. 문자를 입력받으면 a부터 z까지 1~26의 숫자를 각각 대응시킨다. 예를들어 apple = [1, 16, 16, 5 ,12]가 된다. 이를 모두 더하면 $1+16+16+5+12 = 50$인데, 안타깝게도 fight또한 $6+9+7+8+20=50$이므로 합한 값의 결과를 가지고는 두 단어를 분간할 수 없다. 이러한 문제를 피하기 위해서 단어의 자리마다 31의 제곱수를 곱해서 구분하는 것이다. 예를 들어 apple = $1 \times 31^0 + 16 \times 31^1+ 16\times 31^2 + 5\times 31^3 + 12\times 31^4= 18715760$ 이 된다. (여담이지만 2d list를 1d로 풀 때, 인덱스를 비슷한 개념으로 접근한다.)

어쨋든 이런식으로 접근할 경우 small case는 zzzzz에 대해서 24811930이므로 integer범위 내에서 쉽게 구할 수 있다. 하지만 Large case의 경우 최대 50글자의 단어가 주어지므로 그 수가 기하급수적으로 늘어나게 되므로 mod를 사용하여 그 값을 조절하도록 문제에서 조건을 주었다. mod는 나머지를 말한다. small case만 고려할 경우 브론즈문제가 맞지만 패스가 아니라 만점을 노린다면 어느정도 모듈러 공식에 대해 알고 있어야 한다.

모듈러 공식은 내용이 방대하고 애초에 이걸 좀 만 더 파고 들어가면 중국인의 나머지 정리나 페르마와 오일러의 정리 등 정수론의 파도에 휩쓸리므로 이 문제에 필요한 부분만 짚고 넘어가려고 한다. 먼저 아주 당연하지만 다음과 같은 식이 성립한다.

예를 들어 $(11 \times 15) \mod 8 = 165 \mod 8 = 5 = (11 \mod 8 \times 15 \mod 8) \mod 8 = (3\times7)\mod8 = 21\mod 8 = 5$가 되는 것이다. 이건 당연한 것이 $a=Q\times n+R$과 같이 구성될 것이고 이건 $b=Q’\times n+R’$로 마찬가지이다. a와 b의 곱은 고등학교 때 배우는 나머지정리와 같이 $a\times b = QQ’n^2 + (QR’+Q’R)n + RR’$이 되므로 $RR’$을 제외한 모든 항은 n으로 나누어 떨어진다. 그러므로 위의 식은 성립한다는 것을 간단하게 확인할 수 있다.

그런데 이 뿐만 아니라 다른 하나를 더 알아야 한다. 이건 좀 복잡하다.

제곱에 관한 성질인데, 위의 공식으로부터 시작해보자. $a^2 \mod n = (a \mod n \times a \mod n) \mod n $가 된다는 것은 자명하다. 그렇다면 임의의 양의 정수 b에 대해서 $a^b\mod n$은 어떨까? 예를 들어보자. $7^8 \mod 13$은 8이 2의 제곱수이기 때문에 위의 공식을 반복하면 쉽고 빠르게 구할 수 있다.

$7^2\mod 13 = (7\mod 13 \times 7\mod 13) \mod 13 = (7\times 7) \mod 13 = 49 \mod 13 = 10$

$7^4\mod 13 = (7^2\mod 13 \times 7^2\mod 13) \mod 13 = (10\times 10) \mod 13 = 100 \mod 13 = 9$

$7^8\mod 13 = (7^4\mod 13 \times 7^4\mod 13) \mod 13 = (9\times 9) \mod 13 = 81 \mod 13 = 3$

이런식으로 쉽게 계산할 수 있다. 하지만 이 방법의 아주 강력한 점은 2의 제곱수 b가 아니라 임의의 양의 정수 b에 대해서도 똑같이 접근 할 수 있다는 것이다. 왜냐하면 모든 수를 이진법으로 접근하면 되니까.

예를 들어 $17^{92} \mod 19$와 같이 $b=92$일 경우, $92=1011100_{(2)}$이므로 다음과 같이 된다.\

그리고 위에서의 과정을 동일하게 수행하면 된다.

$ 17^1 \mod 19 =5 $

$ 17^2 \mod 19 = (17^1 \mod 19 \times 17^1 \mod 19) \mod 19 = 289 \mod 19 = 4 $

$ 17^4 \mod 19 = (17^2 \mod 19 \times 17^2 \mod 19) \mod 19 = 4\times4 \mod 19 = 16$

$ 17^8 \mod 19 = (17^4 \mod 19 \times 17^4 \mod 19) \mod 19 = 16\times 16 \mod 19 = 9 $

$ 17^{16} \mod 19 = (17^8 \mod 19 \times 17^8 \mod 19) \mod 19 = 9\times 9 \mod 19 = 5$

$ 17^{32} \mod 19 = (17^{16} \mod 19 \times 17^{16} \mod 19) \mod 19 = 5\times 5 \mod 19 = 6$

$ 17^{64} \mod 19 = (17^{32} \mod 19 \times 17^{32} \mod 19) \mod 19 = 6\times 6 \mod 19 = 17$

이렇게 계산한 mod값들을 바탕으로 우리는 다음과 같이 계산할 수 있다.

$ 17^{92} \mod 19 = 17^{(4+8+16+64)}\mod 19 = (17^4\mod 19 \times 17^8 \mod 19 \times 17^{16}\mod 18 \times 17^{64}\mod 19)\mod 19$

$ 17^{92} = (16 \times 9 \times 5 \times 17) \mod 19 = 12240 \mod 19 = 4$

이러한 모듈러의 특성을 활용하여 이 문제에서 원하는 $(a_i \times 31^{i}) \mod 1234567891 $의 합을 구하면된다.

코드는 다음과 같다.

import sys

l = int(sys.stdin.readline())
word = list(map(ord, str(sys.stdin.readline().rstrip())))
wordint = [0]*l

def ABmodC(a, b, c):
    binb = bin(b)[2:]
    modc = [0]*len(binb)
    modc[0] = a%c
    for i in range(1, len(binb)):
        modc[i] = (modc[i-1]*modc[i-1])%c

    res = 1
    for i in range(len(binb)):
        if int(binb[-1-i]):
            res *= (modc[i])
            res %= c
    return res

hashres = 0

r, m = 31, 1234567891
for i in range(l):
    hashres += (word[i]-96) * ABmodC(r, i, m)
    hashres %= m
print(hashres)

5글자 이하의 문제는 브론즈 난이도가 맞는거 같은데 솔직히 만점기준으로는 실버를 줘야하지 않나…?