Hashing

solved_ac[Class2][Hashing](https://www.acmicpc.net/problem/15829)

문제

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

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

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

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

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

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

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

입력

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

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

출력

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

Small (50점)

• 1 ≤ L ≤ 5

Large (50점)

• 1 ≤ L ≤ 50

예제 입력 1

5
abcde

예제 출력 1

4739715

예제 입력 2

3
zzz

예제 출력 2

25818

예제 입력 3

1
i

예제 출력 3

9

힌트

예제 1: abcde의 해시 값은 1 × 31^0 + 2 × 31^1 + 3 × 31^2 + 4 × 31^3 + 5 × 31^4 = 1 + 62 + 2883 + 119164 + 4617605 = 4739715이다.

예제 2: zzz의 해시 값은 26 × 31^0 + 26 × 31^1 + 26 × 31^2 = 26 + 806 + 24986 = 25818이다.

문제 해석

파이썬에서 제공해주는 ord 함수를 써서 문자열을 아스키 코드 값으로 돌려 받은 다음 전부다 더해주고 1234567891로 나눈 나머지 값을 출력해주면 100점이 나온다.
만약 나머지 값으로 출력을 안해줬을시에는 50점이 나온다.

하지만 나는 공부를 위해서 딕셔너리와 분할 정복을 이용해서 문제를 풀었다.

분할 정복

1. 분할(Divide)

   • 해결할 문제를 여러 개의 작은 부분 문제들로 분할

2. 정복(Conquer)

   • 나눈 작은 문제를 각각 해결

3. 통합(combine)

   • 필요 시 해결된 해답을 모음

• C의 거듭제곱 = 거듭제곱 값만큼 C를 곱하는 방법으로 연산 수행

C^2 = C * C

C^3 = C C C

C^n = C C C * C .... C

C를 n번 곱할 것을 2로 나누고 2로 나누고 계속 나누어주면서 시간 복잡도를 줄여준다. 이렇게 되면 n번 곱셈 연산을 할 것을 줄여준다.

만약 2로 나누어지지 않을 경우는 1을 빼서 짝수로 만들어주고 2로 나눈 후 C를 한번 더 곱해준다.

분할 정복 코드

def Recursive_Power(C, n):
    if n == 0:
        return 1
    
    if n == 1:
        return C
    
    if n % 2 == 0:
        y = Recursive_Power(C, n / 2)
        return y * y
    
    else:
        y = Recursive_Power(C, (n - 1) / 2)
        return y * y * C

첫번째 풀이(분할 정복 + 딕셔너리)

• 알파벳을 key로 사용하고 숫자를 value로 사용하는 딕셔너리를 만들어준다.
• 분할정복 함수를 만들어준다.
• L만큼 루프를 돌려서 해당 알파벳의 숫자를 뽑아내고 분할정복 함수를 불러서 i 제곱을 해준다. 그리고 더해준다.
• 1234567891로 나눈 나머지 값을 출력해준다.

import sys

alpha = {'a': 1,'b': 2,'c': 3,'d': 4,'e': 5,'f': 6,'g': 7,'h': 8,'i': 9,'j': 10,'k': 11,'l': 12,'m': 13,'n': 14,'o': 15,'p': 16,'q': 17,'r': 18,'s': 19,'t': 20,'u': 21,'v': 22,'w': 23,'x': 24,'y': 25,'z': 26}


def Recursive_Power(C, n):
    if n == 0:
        return 1
    
    if n == 1:
        return C
    
    if n % 2 == 0:
        y = Recursive_Power(C, n / 2)
        return y * y
    
    else:
        y = Recursive_Power(C, (n - 1) / 2)
        return y * y * C
    
L = int(sys.stdin.readline())

str_alpha = sys.stdin.readline().rstrip()

sum = 0

for i in range(L):
    sum += alpha[str_alpha[i]] * Recursive_Power(31, i)
    
print(sum % 1234567891)      

두번째 풀이(ord 함수)

• L번 루프를 돌면서 ord 함수를 이용해 아스키 코드 값을 받는다.

• a는 문제에서 1로 요구하기 때문에 96을 빼주게 되면 해당 번호를 받을 수 있다.
• 그리고 31의 거듭제곱을 순서에 맞게 곱해준 후 더해준다
• 총 더한 값의 1234567891을 나눈 나머지 값을 출력해준다.

L = int(sys.stdin.readline())
str_alpha = sys.stdin.readline().rstrip()

sum = 0

for i in range(L):
    sum += (ord(str_alpha[i]) - 96) * (31 ** i)

print(sum % 1234567891)

고찰

사실 ord 함수를 써서 쉽게 아스키 코드 값을 변환 받고 분할 정복을 쓰지 않고 31의 거듭제곱을 연산을 통해 얻어내면 그만인 문제이다. 하지만 공부를 하고 싶었고, 만약 거듭제곱이 계속해서 커지게 된다면 연산량이 많아져서 시간초과가 뜨게 될것이다. 그래서 나중에 쓸 분할정복 알고리즘을 미리 공부해서 풀어보았다.