해시함수란? 너비우선탐색 사용하기

1. 해시함수의 예 :

식료품 가게에 오늘 첫 알바를 시작했다.

손님이 물건을 사러오면 모든물건의 가격이 적혀있는 가격장부의 가격을 찾아봐야한다.

가격장부가 알파벳순서로 되어있지 않다면 모든가격을 하나씩 살펴봐야한다.

장부가 알파벳순서로 되어 있다면 이진탐색을 써서 apple가격을 찾을수 있고 이 경우 log n 시간이 걸림.

알파벳 순서로 되어 있지 않다면 단순탐색을 써야하므로 n 시간이 걸림

그런데 장부가 정렬 되어 있다하더라도 계속 물건에 대한 가격을 알려고 장부를 봐야한다면 힘이 든다.

가격을 찾고 있는 동안 손님이 밀려온다. 모든 물건의 이름과 가격을 알고 있는 동료가 있다면 장부따위를 찾아볼 필요가 없다.

동료에게 물어보면 바로 대답해주니깐

동료인 철수는 모든 항목에 대해 O(1) 실행시간 만에 가격을 알려준다. 가격장부의 리스트가 아무리 많아도 상관 없다. 

그리고 이진탐색보다 빠르다.

가격장부를 배열로 구현할수 있다.

배열에 있는 각각의 항목은 두개의 항목으로 이루어짐 

하나는 물건의 이름, 하나는 가격이다.

해시함수를 사용하면 된다.

2. 해시함수란?

해시함수는 문자열을 받아서 숫자로 반환하는 함수이다.

해시함수는 문자열에 대해 숫자를 할당합니다.

해시함수는 일관성이 있어햐 한다. 

apple을 넣었을때 4를 반환한다면 apple을 넣을때마다 반환되는 값은 항상 4이어야 한다.

그렇지 않으면 해시함수로의 역할을 할 수 없다.

다른단어가 들어가면 다른숫자가 나와야 합니다. 

예를 들어 어떤 단어를 넣어도 1만 나온다면 좋은 해시함수가 아니다.

가장 좋은 경우는 서로 다른 단어에 대해 모두 서로 다른숫자가 나와야 한다.

해시 함수는 문자열에 대해 숫자를 할당하는 것이다.

해시함수에 apple을 넣는다. > 해시함수는 3을 반환한다.

apple의 가격은 배열의 3번 인덱스 위치에 저장합니다.

해시함수에 milk을 넣는다. > 해시함수는 0을 반환한다.

milk의 가격은 배열의 0번 인덱스 위치에 저장합니다.

이런식으로 하면 전체배열이 가격으로 채워진다.

milk의 가격이 얼마지 ? 물어본다면 배열을 탐색할 필요가 없다.

그냥 milk를 해시함수에 넣기만 하면 된다.

그러면 가격이 인덱스 0 위치에 저장되어 있다고 알려준다. 당연히 그곳엔 milk의 가격이 저장되어 있다.

해시함수는 가격이 저장된 위치를 정확하게 알려준다. 그래서 탐색을 할 필요가 전혀 없다.

3. 해시함수 코드

 

# 1. 장부에서 물건가격 찾기
book = dict() # dict() 은 딕셔너리라 불리는 파이썬의 해시테이블
book["apple"] = 0.67
book["milk"] = 1.49
book["avocado"] = 2.51
 
print(book)
print(book["apple"])
 
# 2. 전화번호부에서 이름을 갖고 번호찾기
phone_book = {} # phone_book = dict()과 같다.
phone_book["sanghyun"] = 1234
phone_book["emergency"] = 911
print(phone_book["sanghyun"])
 
voted = {}
 
# 3. 투표한 사람 구분하기
def check_voter(name):
    if voted.get(name):
        print ("투표한 사람입니다.")
    else:
        voted[name] = True
        print ("투표하지 않은 사람입니다.")
 
check_voter("harry") 
check_voter("harry")
 
cache = {}
 
# 4. 캐시된 페이지 구분하기
def get_page(url):
    if cache.get(url):
        return cache[url]
    else:
        data = get_data_from_server(url)
        cache[url] = data
        return data
 
def get_data_from_server(url):
    cache[url] = True

해시함수 충돌 해결

같은 공간에 여러개의 키를 연결리스트로 만들어 넣는다.

4. 너비 우선 탐색

너비우선탐색을 사용하면 두항목간의 최단경로를 찾을 수 있다.

4.1 너비우선탐색을 사용( 김포공항 ~ 마포대교 )

그래프 알고리즘을 사용한다.

김포공항에서

1단계로 갈수 있는 곳은 100번 버스타기와 200번 버스타기이다.

2단계로 갈수 있는 곳은 지하철타기, 201번 버스타기, 202번 버스타기 이다.

3단계로 갈수 있는 곳은 마포대교, 지하철타기 이다.

알고리즘을 통해 마포대교까지 최단경로가 3단계라는 것을 알게 되었다.

최단 경로 문제(shortest-path problem) 라고 한다.

즉 가장 짧은 것을 찾아야한다.

1. 문제를 그래프로 모형화한다.

2. 너비우선탐색으로 문제를 푼다.

4.2 너비우선탐색을 사용( 지팡이 사기 )

나는 지팡이를 사려고 한다.

누가 지팡이를 가졌는지 확인해봐야한다.

질문 1. 정점 A에서 정점 B로 가는 경로가 존재하는가?( 지팡이를 판매하는 사람이 있는가? )

질문 2. 정점 A에서 정점 B로 가는 최단경로는 무엇인가?( 누가 가장 가깝게 지팡이를 파는가? )

1촌 관계부터 확인해야한다.

내가 지팡이를 사기위해서는 해리, 해르미온느, 론 부터 먼저 지팡이를 파는지 확인해야 한다.

너비우선탐색은 단순히 A에서 B로 가는 경로를 찾는것이 아닌 최단경로를 찾을 수 있다.

파이썬 코드

from collections import deque
 
graph = {}
graph["me"] = ["rohn","harry","hermione"]
graph["harry"] = ["voldemort","jinny"]
graph["rohn"] = ["jinny"]
graph["hermione"] = ["malfoy","dumbledore"]
graph["voldemort"] = []
graph["jinny"] = []
graph["malfoy"] = []
graph["dumbledore"] = []
 
 
def search(name):
    search_queue = deque()
    print("1번",search_queue)
    print("1번 name: ",name)
    search_queue += graph[name]
    print("2번",search_queue)
    searched = []
    while search_queue: # ["rohn","harry","hermione"]
        print("3번",search_queue)
        person = search_queue.popleft()
        print("4번",person)
        if not person in searched:
            if person_is_seller(person):
                print (person + " is a elder wand seller!")
                return True
            else:
                print("5번 name: ",person)
                search_queue += graph[person]
                print("5번",search_queue)
                searched.append(person)
                print("6번",searched)
    return False
 
def person_is_seller(name):
    return name[-1] == 't' # t자로 끝나는 사람이름
 
search("me")
 
'''
1번 deque([])
1번 name:  me
2번 deque(['rohn', 'harry', 'hermione'])
3번 deque(['rohn', 'harry', 'hermione'])
4번 rohn
5번 name:  rohn
5번 deque(['harry', 'hermione', 'jinny'])
6번 ['rohn']
3번 deque(['harry', 'hermione', 'jinny'])
4번 harry
5번 name:  harry
5번 deque(['hermione', 'jinny', 'voldemort', 'jinny'])
6번 ['rohn', 'harry']
3번 deque(['hermione', 'jinny', 'voldemort', 'jinny'])
4번 hermione
5번 name:  hermione
5번 deque(['jinny', 'voldemort', 'jinny', 'malfoy', 'dumbledore'])
6번 ['rohn', 'harry', 'hermione']
3번 deque(['jinny', 'voldemort', 'jinny', 'malfoy', 'dumbledore'])
4번 jinny
5번 name:  jinny
5번 deque(['voldemort', 'jinny', 'malfoy', 'dumbledore'])
6번 ['rohn', 'harry', 'hermione', 'jinny']
3번 deque(['voldemort', 'jinny', 'malfoy', 'dumbledore'])
4번 voldemort
voldemort is a elder wand seller!
'''
 

1. 확인할 사람의 명단을 넣을 큐를 준비

2. 큐에서 한 사람을 꺼낸다

3. 이사람이 지팡이 판매자인지 확인한다.

4. if 지팡이 판매자가 맞다면 end

   else 지팡이 판매자가 아니라면 그 사람의 이웃을 모두 큐에 추가한다.

론부터 시작해서 론이 지팡이 판매자가 아니면 론의 이웃 지니를 추가한다.

론 > 해리 > 해르미온느 > 지니 > 볼드모트가 나오게 된다.

graph.pptx

bfs.py