참고자료

Grokking Algorithms
소프트웨어 속 알고리즘 #2 슬라이드
쥬피터 노트북 파일

해시테이블 (hash tables)

book = dict()

book["apple"] = 0.67
book["milk"] = 1.49
book["avocado"] = 1.49
print(book)
print(book["avocado"])
{'milk': 1.49, 'apple': 0.67, 'avocado': 1.49}
1.49

해시테이블은 키(key), 값(value)으로 구성합니다.
파이썬에서 딕셔너리(해시테이블)dict()로 생성합니다.

해시테이블 사용 예 - 전화번호부
phone_book = dict()
# phone_book = {}
phone_book["jenny"] = 8675309
phone_book["emergency"] = 911
print(phone_book["jenny"])
print(phone_book["emergency"])
8675309
911
해시테이블 사용 예 - 투표자 명단확인 (중복 방지)
voted = {}

def check_voter(name):
    if voted.get(name):
        print("돌려 보내세요!")
    else:
        voted[name] = True
        print("투표하게 하세요")
        
        
check_voter("tom")
check_voter("mike")
check_voter("mike")
투표하게 하세요
투표하게 하세요
돌려 보내세요!
해시테이블 사용 예 - 캐시로 사용하기
cache = {}

def get_page(url):
    if cache.get(url):
        return cache[url]
    else:
        data = get_data_from_server(url)
        cache[url] = data
        return data

graph 해시테이블로 친구 목록을 모델링 합니다.
가장 적은 수의 노드를 지나는 경로를 찾습니다.

graph = {}
graph["you"] = ["alice", "bob", "claire"]
graph["bob"] = ["anuj", "peggy"]
graph["alice"] = ["peggy"]
graph["claire"] = ["thom", "jonny"]
graph["anuj"] = []
graph["peggy"] = []
graph["thom"] = []
graph["jonny"] = []

파이썬 양방향 큐(deque)를 사용하여 graph의 모든 경로를 큐에 저장합니다.

from collections import deque
search_queue = deque() # 새 큐를 생성
search_queue += graph["you"] # 모든 이웃을 탐색 큐에 추가
print(search_queue)
deque(['alice', 'bob', 'claire'])

너비 우선 탐색 구현

graph 를 큐에 담아 처리 popleft 를 사용하여 한명씩 꺼내면서 망고 판매상인지 확인

def search(name):
    search_queue = deque()
    search_queue += graph[name]
    searched = []
    while search_queue: # 큐가 비어 있지 않는 한 계속 실행
        person = search_queue.popleft() # 큐의 첫번째 사람을 꺼냄
        if not person in searched: 
            if person_is_seller(person): # 망고 판매상인지 확인
                print(person + " is a mango seller")
                return True
            else:
                search_queue += graph[person] 
                searched.append(person) # 망고 판매상이 아님, 모든 이웃을 탐색 목록에 추가
    return False # 여기에 도달한다면 망고판매상이 없음


def person_is_seller(name):
    return name[-1] == 'm'
print(search("you"))
thom is a mango seller
True

다익스트라 알고리즘 (dijkstras algorithm)

너비우선 탐색과는 달리 가장 적은 비용이 드는 경로를 찾습니다.

그래프

graph

graph = {}
graph["start"] = {}
graph["start"]["a"] = 6
graph["start"]["b"] = 2
print(graph["start"].keys())
dict_keys(['a', 'b'])
print(graph["start"]["a"])
print(graph["start"]["b"])
6
2
graph["a"] = {}
graph["a"]["fin"] = 1

graph["b"] = {}
graph["b"]["a"] = 3
graph["b"]["fin"] = 5

graph["fin"] = {}
정점의 가격을 저장하는 해시 테이블
infinity = float("inf")

costs = {}
costs["a"] = 6  # start -> a 까지의 비용
costs["b"] = 2  # start -> b 까지의 비용
costs["fin"] = infinity
부모를 저장하는 해시테이블
parents = {}
parents["a"] = "start"
parents["b"] = "start"
parents["fin"] = None
이미 처리한 정점을 추적하기 위한 배열
processed = []
다익스트라 알고리즘
def find_lowest_cost_node(costs):
    lowest_cost = float("inf")
    lowest_cost_node = None
    # 모든 정점을 확인
    for node in costs:
        cost = costs[node] 
        # 아직 처리하지 않은 정점 중 더 싼 것이 있으면
        if cost < lowest_cost and node not in processed:
            # 새로운 최저 정점으로 설정
            lowest_cost = cost
            lowest_cost_node = node
    return lowest_cost_node

# 아직 처리하지 않은 가장 싼 정점을 찾는다.
node = find_lowest_cost_node(costs)  # b

while node is not None: # 모든 정점을 처리하면 반복문 종료
    cost = costs[node]
    neighbors = graph[node]
    for n in neighbors.keys(): # 모든 이웃에 대해 반복
        new_cost = cost + neighbors[n]
        if costs[n] > new_cost: # 이 점을 지나는 것이 가격이 더 싸다면 
            costs[n] = new_cost # 정점의 가격을 갱신
            parents[n] = node # 부모를 이 정점으로 새로 설정
    processed.append(node) # 정점을 처리한 사실을 기록
    node = find_lowest_cost_node(costs) # 다음으로 처리할 정점을 찾아 반복
print("부모 테이블 (경로 이동) : ")
print(parents) 
print("최단 거리 노드 비용은 : ")
print(costs)
부모 테이블 (경로 이동) : 
{'a': 'b', 'b': 'start', 'fin': 'a'}
최단 거리 노드 비용은 : 
{'a': 5, 'b': 2, 'fin': 6}

start -> b -> a -> fin

탐욕 알고리즘 (greedy algorithm)

set(집합)

arr = [1, 2, 2, 3, 3, 3]

set(arr)
set([1, 2, 3]) # 집합 생성
{1, 2, 3}
fruits = set(["avocado", "tomato", "banana"])
vegetables = set(["beets", "carrots", "tomato"])
print(fruits | vegetables) # 합집합
print(fruits & vegetables) # 교집합
print(fruits - vegetables) # 차집합
print(vegetables - fruits) # 차집합
{'banana', 'avocado', 'beets', 'carrots', 'tomato'}
{'tomato'}
{'banana', 'avocado'}
{'carrots', 'beets'}

근사 알고리즘

하나의 방송국을 통해 청취할 수 있는 지역은 한정되어있어 전국의 방송국을 돌며 방송을 하고 싶다.
쇼를 하는데 돈을 들기 때문에 최대한 적은 수의 방송국을 돌아야 한다.

states_needed = set(["mt", "wa", "or", "id", "nv", "ut", "ca", "az"])

stations = {}
stations["kone"] = set(["id", "nv", "ut"])
stations["ktwo"] = set(["wa", "id", "mt"])
stations["kthree"] = set(["or", "nv", "ca"])
stations["kfour"] = set(["nv", "ut"])
stations["kfive"] = set(["ca", "az"])

final_stations = set()

while states_needed:
    best_station = None
    states_covered = set()
    for station, states in stations.items(): # 키, 데이터
        covered = states_needed & states # 교집합
        if len(covered) > len(states_covered): # best_station 보다 더 많은 주를 커버하는지 확인
            best_station = station
            states_covered = covered

    states_needed -= states_covered # states_needed 가 완전히 빌때까지 반복
    final_stations.add(best_station) # best_station 을 추가

print("최대한 적은 수로 모든 주를 커버하는 방송국은 : ")
print(final_stations)
최대한 적은 수로 모든 주를 커버하는 방송국은 : 
{'ktwo', 'kfive', 'kthree', 'kfour'}

states_needed 배열을 하나씩 돌면서 그 주에 가장 많이 겹치는 방송국을 찾은 후
best_station 이 발견되면 states_covered 는 states_needed 에서 제거한다.

정확한 결과는 아니지만 배열이 많아지면 해결이 불가능해지는 NP완전문제의 답을 내주는 좋은 방법이 됩니다.