파이썬을 이용한 검색 알고리즘2(해시)

검색 알고리즘에서 빠진 부분을 가져왔다!

이 부분도 놓치지 말고 따라 해 보자..!

1. 해시 검색법

• 기존 검색법의 단점
  • 기존 검색법은 추가, 삭제가 어렵다
  • 어떤 데이터가 어떤 요소에 저장되어있는지 모른다.

• 용어 정리
  • 해시(Hash) : 임의 값을 고정길이로 변환하는 것
  • 해시 테이블 : 키 값의 연산에 의해 직접 접근이 가능한 데이터 구조
  • 해시 함수 : key에 대해 산술 연산을 이용해 데이터 위치를 찾을 수 있는 함수
  • 해시 값 또는 해시 주소 : key를 해시 함수로 연산해서, 해시 값을 알아내고 , 이를 기반으로 해시 테이블에서 해당 key에 대한 데이터 위치를 일관성있게 찾을 수 있음
  • 슬록(버켓) : 한 개의 데이터를 저장할 수 있는 공간

• 성능은 O(1)이지만 충돌이 발생할 경우 O(n)이 될 수 있다.

• 파이썬에서는 dict타입을 사용하면 되므로 Hash를 구현할 필요가 없다.

• 충돌 해결
  • Chaining 기법
    • 개방해싱 기법 중 하나 : 해시 테이블 외의 저장 공간을 활용하는 방법
    • 충돌이 일어나면 링크드 리스트라는 자료 구조를 이용하는 방법
  • 오픈 주소법
    • 닫힌 해싱 기법 중 하나
    • 충돌이 일어나면 재 해시를 수행하여 빈 버킷을 찾는 방법

• 장점
  • 데이터의 저장 / 읽기 속도가 빠르다.(검색속도가 빠르다)
  • 해시는 키에 대한 데이터 확인이 쉽다.(중복 확인 용어)

• 단점
  • 일반적으로 저장 공간이 좀 더 많이 필요하다.
  • 충돌 발생

• 주요 용도
  • 검색이 많이 필요한 경우
  • 저장, 삭제, 읽기가 빈번한 경우

이론만 보면 이해하기 힘드니 예시를 같이해볼까!!???

---

# 사용 예
arr = [0 for i in range(7)]
data = [11, 15, 23, 26]

# 11 % 7 = 4
# 15 % 7 = 1
# 23 % 7 = 2
# 26 % 7 = 5

arr[4] = 11
arr[1] = 15
arr[2] = 23
arr[5] = 26

arr

 

 

[0, 15, 23, 0, 11, 26, 0]

---

# 사용 예2

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

# hash function 준비
def hash_func(key):
    return key%5

data1 = "Andy"
data2 = "Dave"
data3 = "Trumph"
data4 = "Anthony"

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

# hash table에 값 저장
# data:value와 같이 data와 value를 넣으면 해당 data에 대한 key를 찾아서
# 해당 key에 대응하는 해시 주소에 value를 저장
def data_save(data, value):
    key = ord(data[0])
    hash_address = hash_func(key)
    hash_table[hash_address] = value

data_save("Andy", "01011111111")
data_save("Dave", "01022222222")
data_save("Trumph", "01033333333")

# 데이터 읽어오기
def data_read(data):
    key = ord(data[0])
    hash_address = hash_func(key)
    return hash_table[hash_address]

data_read("Andy") # 01011111111

 

65 68 84 65
65 0

 

'01011111111'

---

# 사용 예3(충돌 해결)

# 먼저 배열 2개 준비
arrayA = [12, 25, 36, 20, 30, 8, 42]
arrayB = [0 for i in range(11)]

# 해시 처리를 통해 데이터(arrayA)를 hash table(arrayB)에 저장
for i in range(len(arrayA)):
    key = arrayA[i]%11
    
    if (arrayB[key] == None):
        arrayB[key] = arrayA[i]
    else:
        while(arrayB[key]):
            if(key < len(arrayB)-1):
                key += 1
            else:
                key = 0
                
        arrayB[key] = arrayA[i]
        
print(arrayB)

# 탐색 알고리즘 구현
def findHashData(arr, target):
    key = target % len(arr)
    
    # 찾고자 하는 값이 나올때까지
    while(arr[key] != target):
        # 원하는 결과가 아니면 +1
        key = (key + 1) % len(arr)
        
    return key+1

result = findHashData(arrayB, 42) # 저장 위치는 1번째 위치에 있습니다
print("저장위치는 {}번째 위치에 있습니다.".format(result))

 

[42, 12, 0, 25, 36, 0, 0, 0, 30, 20, 8]
저장위치는 1번째 위치에 있습니다.

---

 

문제를 풀어보자!

완주하지 못한 선수

---

문제 설명

수많은 마라톤 선수들이 마라톤에 참여하였다. 단 한 명의 선수를 제외하고는 모든 선수가 마라톤을 완주하였다.

*마라톤에 참여한 선수들의 이름이 담긴 배열 participant와 완주한 선수들의 이름이 담긴 배열 completion이 주어질 때, 완주하지 못한 선수의 이름을 return 하도록 solution 함수를 작성하시오.

제한 사항

• 마라톤 경기에 참여한 선수의 수는 1명 이상 100,000명 이하이다.
• completion의 길이는 participant의 길이보다 1 작다.(한명만 완주하지 못했다는 전제로 인함)
• 참가자의 이름은 1개 이상 20개 이하의 알파벳 소문자로 이루어져 있다.(여기서는 큰 의미가 없다)
• 참가자 중에는 동명이인이 있을 수 있다.(만약 동명이인이 없다면 이것을 집합으로 해서 차집합을 구하면 된다. 여기서는 가장 큰 문제일 수 있다.)

 

"""
참가자                                               완주자                                        결과
-----------------------------------------------------------------------------------------------------------
["leo", "kiki", "eden"]                              ["eden","kiki"]                               "leo"
["marina", "josia", "nikola", "vinko", "fillpa"]     ["josipa","fillpa","marina","nikola"]         "vinko"
["mislav", "stanko", "mislav", "ana"]                ["stanko","ana", "mislav"]                    "mislav"
"""

---

설루션 1

 

def solution1(participant, completion):
    d = {}
    for i in participant:
        d[i] = d.get(i, 0) + 1
        
    for i in completion:
        d[i] -= 1
        
    return [k for k, v in d.items()if v > 0]

solution1(["mislav", "stanko", "mislav", "ana"], ["stanko", "ana", "mislav"])

 

 

['mislav']

솔루션2

def solution2(participant, completion):
    participant.sort()
    completion.sort()
    
    for i in range(len(completion)):
        if participant[i] != completion[i]:
            return participant[i]
        
    return participant[len(participant)-1]
    
solution2(["mislav", "stanko", "mislav", "ana"], ["stanko", "ana", "mislav"])   

 

 

'mislav'

 

여러분들은 문제를 해결하셨나요???

어려워도 꾸준히 하다 보면 실력이 는다는 사실!

모두들 잊지 말고 고민하며 해결해보아요~~