백준 15829 python Hashing 문제 풀이

1. 해시함수란?

임의의 길이의 입력을 받아서, 고정된 길이의 출력을 내보내는 함수.

보통 자료의 저장에도 사용 되지만, 주로 매우 빠른 데이터 탐색에도 사용된다.

 

2. 해시함수 알고리즘이란?

긴 길이의 데이터를 짧은 길이의 데이터로 변환하는 알고리즘이다.

단, 제 3자는 짧은 길이 데이터로부터 긴 길이의 데이터를 도출할 수 없어야한다.

그리고 동일한 출력을 갖는 데이터를 찾을 수 없어야한다.

 

공개키 암호 알고리즘 RSA가 해시함수의 일종이지 않을까 생각해봤다.

그러나 공개키 암호 알고리즘은, 긴 길이의 데이터를 짧은 길이의 데이터로 변환하는 것은 아니니, 완전히 같지는 않고

제 3자로부터 암호화 전의 비밀번호를 알지 못하게 하는 '보안'에서 사용된다는 공통점이 있겠다.

 

3. 문제 풀이

영어 알파벳은 26개 이므로, a~z에 1~26 숫자를 부여한다.

    따라서 문자열을 입력하면, 수열을 얻을 수 있다.

이렇게 얻은 수열을 하나의 정수로 치환하기 위해서, 적당히 큰 수 M으로 나눠주겠다.

M으로 나눴을 때의 나머지를 H(출력 값=해시 값)이라고 하겠다.

 

나누는 수가 생긴다는 것은, 나눴을 때 나오는 나머지의 범위로 범위가 정해진다.

    (비둘기집의 원리-27로 나누는데, 전체 모수가 28개 이상이 되면 비둘기집의 원리에 의해 겹치는 쌍이 1개 이상 발생한다.)

이렇게 동일한 해시 값을 가지는 것을 '해시 충돌'이라고 하고, 좋은 해시 함수는 해시 충돌의 수가 적다.

 

지금까지의 해시함수 암호화 방법은

1) a~z에 1~26 숫자 부여

2) 다 더한 뒤, 적당히 큰 수 M으로 나눈다.

이 방법이다. 그런데 이것은, abc와 acb와 같이 순서가 달라져도 같은 값을 가지므로 해시 충돌이 발생한다.

 

따라서 이 방법을 개선하기 위해서, 각 항마다 고유한 계수를 부여한다.

특정한 숫자 r을 i번째면 i만큼 곱해준다.(0번째 수는 r^0, 1번째 수는 r^2)

r과 M은 서로소로 정하는 것이 일반적이다.

이 문제에서는 r=31, M=1234567891로 가정한다.(둘 다 소수임)

 

4. 코드 작성 순서

1. a~z를 1~26으로 전환하는 코드 작성

2. 반복문으로 문자열의 위치에 따른 계수들을 곱해줌

3. 합을 구하고, M으로 나눈 H값 출력

 

1. a~z를 1~26으로 전환하는 코드 작성

우선 아스키 코드를 활용해보면 좋을 것 같다.

a=97이므로 아스키 코드 수로 바꾼 후, -96을 해줬다. 그리고 문자로 바꾼 뒤, new_string이라는 문자열에 더해주는 반복문을 작성했다.

이렇게 하면 수열로 바뀐 것을 출력할 수 있다.

import sys
input=sys.stdin.readline

l=int(input().rstrip()) #문자열의 길이
string=input().rstrip() #문자열

r=31 #예시 소수 : 
m=1234567891 #예시 소수 : 나누는 수

new_string=''
for chr in string:
    new_string+=str(ord(chr)-96)

 

2. 반복문으로 문자열의 위치에 따른 계수들을 곱해줌

수열을 출력하는 것이 아니라, 한번의 반복문으로 해결 시키기 위해서, for문 안에서 바로 r을 곱한 후의 sum 값을 가져오도록 코드를 짰다.

import sys
input=sys.stdin.readline

l=int(input().rstrip()) #문자열의 길이
string=input().rstrip() #문자열

r=31 #예시 소수 : 
m=1234567891 #예시 소수 : 나누는 수

sum=0
i=0
for chr in string:
    sum+=(ord(chr)-96)*(r**i)
    i+=1

3. 합을 구하고, M으로 나눈 H값 출력 🚀 정답 코드

자 이제 정답만 구하면 끝난다. 정답이다.

import sys
input=sys.stdin.readline

l=int(input().rstrip()) #문자열의 길이
string=input().rstrip() #문자열

r=31 #예시 소수 : 
m=1234567891 #예시 소수 : 나누는 수

sum=0
i=0
for chr in string:
    sum+=(ord(chr)-96)*(r**i)
    i+=1

result=sum % m
print(result)