[파이썬 코테 대비 동아리] _개념을 공부하자 "해시"편

즈_말 2022. 9. 24. 19:18

해쉬

해시(Hash) 란?

: 자료구조의 하나이다. 임의 값을 ( a, 124, 안녕하세요, Hello World ) 해시( Hash ) 함수로 일정한 길이의 값으로 바꾸는 것이다.

해시 테이블( Hash Table )이란?

: 해시 함수를 사용하여 출력값인 색인( index )을 이용해 key 와 value로 저장된 해시 테이블에서 데이터를 찾는다. 데이터를 다루는 기법 중 하나로 데이터의 검색과 저장이 빠르게 진행된다 .

파이썬에서는 dictionary, 루비에서는 Hash, 자바에선 Map이 해시 테이블의 대표적인 예시이다. 보통은 배열로 미리 Hash Table 사이즈 만큼 생성 후에 사용한다. ( 공간과 탐색 시간을 맞바꾸는 기법) 그러나 파이썬에서는 해시 테이블 사이즈를 딕셔너리 타입을 쓰면 끝이기 때문에 별도로 구현할 필요가 없다 !

: 기본 연산으로는 search, insert, delete가 있다.

: 순차적으로 데이터를 저장하지 않고 key를 통해서 value 값을 얻는다.

: slot이란 단어를 종종 볼 수 있는데 slot은 해시 테이블에서 한 개의 데이터를 저장할 수 있는 공간이다.

: 쉽게 말하면 데이터 테이블 같은 느낌인 듯 ?

해시는 자료구조의 하나
key를 이용해서 해시함수를 거치면 출력값 ( index )가 나오는데 이를 해시 주소라고 하며, 해시 테이블에서 해시 주소를 대입하면 데이터 위치를 일관성 있게 찾을 수 있다.
해시 테이블의 한 개의 데이터 저장 공간을 슬롯( slot )이라고 부른다.
데이터 검색과 저장이 아주 빠르게 진행되기 때문에 많이들 쓴다 !
주로 검색이 많이 필요한 경우 / 저장, 읽기, 삭제가 빈번한 경우 / 캐쉬 구현시에 많이 쓴다.

Dictionary를 쓰기 전에.. 초간단 해시 함수를 한번 만들어보자

hash_table = list([ 0 for i in range(10)])
hash_table

#output
#[0,0,0,0,0,0,0,0,0,0]

해시 함수 ?

: 임의의 길이를 갖는 메시지를 입력 받아서 고정된 길이의 해시값을 출력하는 함수이다. 원래 입력 값과는 완전히 다른 모습이기 때문에 암호화 영역에서 주요하게 사용되며 SHA ( Secure Hash Algorithm )알고리즘이 대표적인 예시이다 .

: 가끔… 해시 충돌이 일어난다. 고정된 해시값을 출력하기 때문에 다른 값을 입력해도 같은 해시값이 나오는 것이다. 이를 해결하기 위해서는 별도의 자료구조가 필요하다.

해시 충돌 방지

: 개방 주소법(open addressing)으로 해시 테이블 크기는 고정하면서 빈 곳을 찾아 채우거나 분리 연결법(seperate chaining)으로 해시 테이블의 크기를 가변적으로 만드는 방법이다.

개방 주소법(open addressing)

: 선형 탐사법(Linear Probing)으로 선형적이게 순차적으로 검색한다. slot에 이미 값이 저장되어 있으면 이 slot만큼 폭을 옮겨 다음 해시값에 저장한다.

또는 제곱 탐사법(Quadratic Probing)으로 고정폭이 아닌 제곱으로 폭을 늘리는 방법이다. 또는 이중 해싱(Double Hashing) 으로 해시값의 규칙을 없앤다. 충돌된 해시에 또 해시를 적용해서 값을 다르게 변화시키는 것이다.

분리 연결법(seperate chaining)

: 하나의 슬롯에 들어갈 값의 제한을 듣지 않는다. 이때 slot 에는 linked list 나 tree를 이용해준다. linked list로 노드가 연결되기 때문에 (기차라고 생각한다 나는…) 주소가 변하지 않고 데이터 개수 제약이 없다. 하지만 메모리 문제가 있을 수 있다.

파이썬에서의 해시 테이블. 딕셔너리(Dictionary)

: 먼저 딕셔너리에 대해서 살펴보자

value1 = {
	'color' : 'green'.
	'age' : '24'.
	'address' :'Seoul'
}

print(value1) #전체 출력
print(value1.keys()) #key만 출력
print(value1.values()) # value만 출력
print(value1['age']) # key로 값에 접근
value1['grade'] = 5 # key값 추가
value1['grade'] =7 #값 수정
del value1['grade'] # key값 삭제

이제 key와 value를 출력 해보자.

for key, value in value1.items(): #item함수는 딕셔너리의 key value반환
	print("key :"+key)
	print("value: "+value)
	print("키에 따른 값 :" +user[key]

위는 딕셔너리의 구조와 정의 사용법이다.

hash_table = list([0 for i in range(10)])
print(hash_table)

def hash_func(key):
    return key % 5

data1 = "red"
data2 = "yellow"
data3 = 'blue'

print(ord(data1[0]), ord(data2[0]), ord(data3[0]))
print(ord(data1[0]), hash_func(ord(data1[0])))

def save_data(data, value):
    key = ord(data[0])
    hash_address = hash_func(key)
    hash_table[hash_address] = value

save_data("red", "1000")
save_data("yellow", "2000")
save_data("blue", "3000")

def get_data(data):
    key = ord(data[0])
    hash_address = hash_func(key)
    return hash_table[hash_address]

print(get_data("red"))

이런식으로 hash로 dictionary를 이용해 값에 접근할 수 있다.

우리의 목표는 뭐다 ? 코딩 테스트다

해시가 뭔지 다 알아봤으니 이제 몸으로 느껴보자 !

https://codingpractices.tistory.com/entry/Python-파이썬-해시-Hash-해싱-Hashing-문제로-알아보기

여기서 풀이를 가져옴 …! 왜냐면..난…아무것도 모르니까..배우는 의미로다가…

프로그래머스 Level2 전화번호 목록

:전화번호부의 전화번호 중 한 번호가 다른 번호의 접두어인 경우 확인.

구조대 : 119

박준영 : 97 674 223

지영석 : 11 9552 4421

다음의 전화번호의 경우 구조대의 번호가 영석이의 접두사이다.

전화번호부에 적힌 전화번호를 담은 배열 phone_book이 solution함수의 매개변수로 주어질 때 어떤번호가 다른 번호의 접두어인 경우가 있으면 false, 그렇지 않으면 true 를 return 하도록 solution함수를 작형한다.

해시 x 풀이

def soulution(phone_book):
	answer = True
	for i in phone_book:
		temp=''
		for j in i:
			temp += j
			if temp in phone_book and temp != i:
				answer = False
			return answer

이러면 효율성 문제에서 오류가 난다구 하네요 ~

해시 o 풀이

def solution(phone_book):
	answer = True
	hash = {}

	for i in phone_book:
		hash[i] = 1
	for i in phone_book:
		temp = ''
		for j in i:
			temp += j
			if temp in hash and temp !=i:
			answer = False

	print(answer)

solution(['119','97676223','1195524421'])
solution(['123','456','789'])

사실 봐도 이해가 잘 안 됨 ㅠ-ㅠ

꾸역꾸역 노력해보자면…

hash i값에 1을 담는 이유는 value값이 필요없고 key값만 비교하면 되는 문제이기 때문인 것 같다. 딱히 다른 값도 없고 전번만 비교하면 되기 때문에.. 그래서 temp(임시)변수에다 값 너어가며 hash로 비교해가면서 같은 게 있나 없나 검사하는 거 같은데…어…….ㅠㅠㅠㅠㅠㅠ모르겠다..

다른 블로그의 문제풀이와 해설을 또 가져오봤다

https://scarletbreeze.github.io/articles/2019-07/pythonKit문제풀이(1)

완주하지 못한 선수

수많은 사람들이 선수들이 마라톤에 참여
단 한 명의 선수를 제외하고는 모든 선수가 마라톤을 완주
마라톤에 참여한 선수들의 이름이 담긴 배열 participant와 완주한 선수들의 이름이 담긴 배열 completion이 주어질 때,
완주하지 못한 선수의 이름을 return 하도록 solution 함수를 작성해주세요
제한사항
마라톤 경기에 참여한 선수의 수는 1명 이상 100,000명 이하
- participant의 길이는, 10만 이하를 가질 것이네.
completion의 길이는 participant의 길이보다 1 작다.
참가자의 이름은 1개 이상 20개 이하의 알파벳 소문자로 이루어져 있다.
참가자 중에는 동명이인이 있을 수 있다.
- 동명이인 조건이 없었다면, 집합으로 구해서 차집합으로 구해버리면 되는데, 이 조건을 인해 접근 방법이 달라짐
입출력 에시도 잘 살펴보기

일단 해설보기 전 내 생각은 마라톤선수 참가선수 배열과 완주 선수 배열을 비교해서( 참가선수 해시에 value값을 모두 0으로 설정 ) 단 한명의 선수 제외하고는 해시 value값이 1로 들어가게끔 만들어주고 해시찾기로 value값이 1인 사람을 출력하게끔 하면 되겠는데 음…

동명이인을 어떻게 할까 ㅠ가 문제이다.

해설을 보니 !!! 이런 생각이 …!!! 참가 선수 이름을 a b c d라고 하면 참가 선수에 value에 이름이 나올 때 마다 1을 증가시켜준다. 만약 b가 3명이라 하면 참가 선수만 등록한 해시에는 value가 3이 들어감. 이제 완주 선수 해시를 비교해서 1씩 감소시켜주면 …!! b만 1을 가지기 때문에 리턴값(key)을 호출하면 b가 나온다 !!

def solution(participant, completion):
	table = { } # 빈 딕셔너리 == 해시 테이블 만들고
	for x in participant :
		table[x] = table.get(x,0) + 1 #key로 value얻어내느 함수 get 사용. 딕셔너리에 x가 없을시 default 입력, 처음 등장하면 1로 만들고 아니면 기존 value에 1 더하기
	for x in completion :
		table[x] -= 1  #완주 인원 빼주기
	tablenf = [ i for i , k in table.items() if k > 0]
	answer = dnf[0]
	return answer

다른건 다 이해했는데 7번째 줄 이해불가..ㅠ 파이썬 이해부족인듯 파이썬을 개념부터 안 하고 그냥 찍먹수준으로 필요한 것 만 골라 공부했더니..뭔지 모르겠다…

일단 items()함수가 key 의 value만 반환한다.

dnf라는 변수는 배열이며 k와 딕셔너리의 …. 이부분 이해가 안댐 ㅠ0ㅠ

i for i 가 i 를 리스트 안에 넣는데... items()로 밸류 값 뽑아내서 1이상이면 k가 되고 그 k를 i에 넣는다는건가….?

아@@@ 알아냈다 i 를 리스트 안에 넣는데 key i의 value값 k를items로 1보다 큰 밸류 가 있으면 key값 i를 넣는다 !! 라는 듰 인듯 !!

728x90