211026화 - 깊이 우선 탐색(Depth First Search), 탐욕 알고리즘, 최단...

211026화 - 깊이 우선 탐색(Depth First Search), 탐욕 알고리즘, 최단...

1. 깊이 우선 탐색 (DFS)

: 한 노드의 자식을 타고 끝까지 순회한 후, 다시 돌아와서 다른 형제들의 자식을 타고 내려가며 순회함.

- 자료구조 스택과 큐를 활용

- 알고리즘 구현

=> 파이썬의 딕셔너리(map)와 리스트(array) 자료 구조를 활용해서 그래프를 표현할 수 있다.

graph = dict() graph['A'] = ['B', 'C'] graph['B'] = ['A', 'D'] graph['C'] = ['A', 'G', 'H', 'I'] graph['D'] = ['B', 'E', 'F'] graph['E'] = ['D'] graph['F'] = ['D'] graph['G'] = ['C'] graph['H'] = ['C'] graph['I'] = ['C', 'J'] graph['J'] = ['I']

- need_visit 스택과 visited 큐 를 활용하여 구현함

need_visit 스택(BFS는 큐)에서 시작점key 부터 하나씩 꺼내서 visited 큐에 저장. 그 과정에서 key 의 value들을 need_visit 큐에 저장. 만약 need_visit 큐에서 막 꺼낸 key가 이미 visited 큐 속의 key와 중복일 시, 아무것도 안하고 다음 need_visit 큐 pop

=> 이런식으로 그래프 쭉 가면 DFS 방식의 탐색이 된다.

- 코드로 구현

def dfs(graph, start_node): visited, need_visit = list(), list() need_visit.append(start_node) while need_visit: node = need_visit.pop() # BFS와의 차이. DFS는 need_visit이 스택이다. if node not in visited: visited.append(node) need_visit.extend(graph[node]) return visited

dfs(graph, 'A')

=> ['A', 'C', 'I', 'J', 'H', 'G', 'B', 'D', 'F', 'E']

- 시간복잡도 (BFS와 동일)

* 노드수: V

* 간선 수: E

* 위코드에서 while need_visit 은 V+E 번 만큼 수행함.

* 시간 복잡도: O(V+E)

2. 탐욕 알고리즘

: 최적의 해에 가까운 값을 구하기 위해 사용됨.

: 여러 경우 중 하나를 결정해야할 때마다, 매순간 최적이라고 생각되는 경우를 선택하는 방식으로 진행해서, 최종적인 값을 구하는 방식.

EX)

문제1: 동전 문제

지불해야 하는 값이 4720원 일 때 1원 50원 100원, 500원 동전으로 동전의 수가 가장 적게 지불하시오. 가장 큰 동전부터 최대한 지불해야 하는 값을 채우는 방식으로 구현 가능 탐욕 알고리즘으로 매순간 최적이라고 생각되는 경우를 선택하면 됨

1) 코인 종류를 크기가 큰 순서대로 출력

coin_list = [1, 100, 50, 500] print (coin_list) coin_list.sort(reverse=True) print (coin_list)

=> [1, 100, 50, 500]

[500, 100, 50, 1]

2) 리스트 갯수(동전 종류) 만큼 반복(몫을 구함. -> 몫을 토탈 카운트에 더함 -> value값 차감, -> details에 코인 정보랑, 갯수 저장 )

coin_list = [500, 100, 50, 1] def min_coin_count(value, coin_list): total_coin_count = 0 details = list() coin_list.sort(reverse=True) ## for coin in coin_list: # 리스트 갯수 만큼 반복. coin_num = value // coin # 몫을 구함. total_coin_count += coin_num # 토탈 카운트에 더함 value -= coin_num * coin # value값 차감 details.append([coin, coin_num])# details에 코인 정보랑, 갯수 저장 return total_coin_count, details

min_coin_count(4720, coin_list)

=> (31, [[500, 9], [100, 2], [50, 0], [1, 20]])

- 각 단계에서 최적의 경우를 고르고, 그 다음단계에 대해서도 최적의 경우를 구하는 전략!

문제2: 부분 배낭 문제 (Fractional Knapsack Problem) ¶

무게 제한이 k인 배낭 에 최대 가치를 가지도록 물건을 넣는 문제 각 물건은 무게(w)와 가치(v)로 표현될 수 있음 물건은 쪼갤 수 있으므로 물건의 일부분이 배낭에 넣어질 수 있음, 그래서 Fractional Knapsack Problem 으로 부름 Fractional Knapsack Problem 의 반대로 물건을 쪼개서 넣을 수 없는 배낭 문제도 존재함 (0/1 Knapsack Problem 으로 부름) 물건은 하나씩만 있고, 하나를 쪼개 담을 수 있다.

data_list = [(10, 10), (15, 12), (20, 10), (25, 8), (30, 5)] # 듀플로 표현 (-> 수정 불가)

1) 가장 무게대비 가치가 높은 순으로 sorting 을 해야합니다.

data_list = sorted(data_list, key=lambda x: x[1] / x[0], reverse=True)

=> [(10, 10), (15, 12), (20, 10), (25, 8), (30, 5)]

-> 이제 약간 동전문제와 비슷해짐. 이제 W(무게) 만큼 최대로 넣으면 된다.

2)

def get_max_value(data_list, capacity): data_list = sorted(data_list, key=lambda x: x[1] / x[0], reverse=True) total_value = 0 details = list() for data in data_list: # 튜플단위로 하나씩 가져옴 if capacity - data[0] >= 0: # 가방 수용 무게가 넣을 무게보다 넉넉할 때 capacity -= data[0] # 넣었으니, 남은무게가 차감 total_value += data[1] # 넣은 무게만큼 가치 상승 details.append([data[0], data[1], 1]) else: # 가방 수용 무게가 넣을 무게보다 작을 때 (마지막 빈틈 다 채울때) fraction = capacity / data[0] # 물건을 쪼갬 (몫 구함) # capacity -= data[0] * fraction # 어차피 마지막이라 남은무게 계산 안해도 된다. total_value += data[1] * fraction # 쪼갠 만큼의 무게 구함 details.append([data[0], data[1], fraction]) break return total_value, details

get_max_value(data_list, 30)

=> (24.5, [[10, 10, 1], [15, 12, 1], [20, 10, 0.25]])

- 전체 물건의 조합을 고려하지 않고, 매 순간의 최적의 경우만 생각하고 문제를 풀어가는 방식!

3. 탐욕 알고리즘의 한계

탐욕 알고리즘은 근사치 추정에 활용

반드시 최적의 해를 구할 수 있는 것은 아니기 때문

최적의 해에 가까운 값을 구하는 방법 중의 하나임

1. 최단 경로 알고리즘의 이해

: 두 노드를 잇는 가장 짧은 경로를 찾는 문제

: 가중치 그래프 에서 간선의 가중치 합이 최소가 되도록 하는 경로를 찾는 것이 목적

1) 단일 출발 및 단일 도착 최단 경로 문제

2) 단일 출발 최단 경로 문제 (특정 노드와 각각 노드간에 최단 짧은 경로)

3) 전체 쌍 최단 경로 ( 그래프 내의 모든 노드와 노드 의 경우의 수에 대한 최단 경로)

2. 최단 경로 알고리즘 - 다익스트라 알고리즘

: 단일 출발 최단 경로문제.

: 특정 출발점을 가지고 그래프에 있는 각각의 노드와 특정 출발점간에 최단 경로를 다중으로 구해줌.

- 다익스트라 알고리즘 로직

- 첫 정점을 기준으로 연결되어 있는 정점들을 추가해 가며, 최단 거리를 갱신하는 기법.

- 너비우선탐색과 유사. (뎁스별로 탐색)

( 기준 정점과 연결되어 있는 정점(가장 얕은 뎁스)들 부터 탐색, 각각의 정점에서 연결되어 있는 정점들 계산)

- 우선순위 큐를 사용

from http://jun01.tistory.com/97 by ccl(A) rewrite - 2021-10-26 21:26:54