코딩혜영

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)

🐸  코딩혜영의 소소한 이야기

요즘 백준 문제를 풀기 시작했다.

정말 부담 가지지 않고, 생각날 때 마다 몇 문제 씩 풀고 있다.

난이도 별로 나열해서 기초부터 풀고 있는데,

관련된 지식까지 복습하면서 가기에는 꽤 유용하다.

❓ 백준 9498 python : 시험성적

input_score=int(input())

if (input_score>=90 and input_score<=100):
    print('A')
elif (input_score>=80 and input_score<=89):
    print('B')
elif (input_score>=70 and input_score<=79):
    print('C')
elif (input_score>=60 and input_score<=69):
    print('D')
else :
    print('F')

input_score=int(input())

if (input_score>=90) :
    print('A')
elif (input_score>=80):
    print('B')
elif (input_score>=70):
    print('C')
elif (input_score>=60):
    print('D')
else :
    print('F')

문제가 더욱더 복잡해졌을 때, 이와 같은 실수를 반복하지 말아야겠다는 생각이 들었다.

또한 더 좋은 코드를 찾다가,

삼항표현식 이라는 개념을 공부하게 되었다.

➕개념) 삼항표현식

true_value if 조건식 else false_value

조건식이 참이면 true_value를

조건식이 거짓이면 false_value를 반환한다.

- 잘 사용하면 if-else 조건식보다 더 깔끔하게 표현할 수 있다.

- 한 줄로 코드 작성 가능

#삼항표현식
value = true_value if condition else false_value

#if-else 조건식
if condition:
	value = true_value
else:
	value=false_value

이 문제도 삼항표현식으로 풀 수 있다.

input_score=int(input())
print('A') if input_score>=90 else print('B') if input_score>=80 else print('C') if input_score>=70 else print('D') if input_score>=60 else print('F')

볼 때는 굉장히 복잡해보이지만, 실제로 작성할 때는 오히려 편하다. 하지만 가독성은 확실히 떨어지는 것 같다.

+관련지식1) 삼항연산자

조건식 ? true_value : false_value

+관련지식2) 중첩 삼항 표현식

true_value if 조건식 else 삼항표현식삽입

false_value 자리에 삼항표현식을 n번 삽입해서 중첩에 중첩을 시킬 수 있다.