본문 바로가기

알고리즘 이론19

DFS 기본 구현 DFS (Depth First Search) : - 노드에 연결된 자식들을 탐색하고 그와 연결된 노드들을 탐색하는 기법 * visited 큐와 need_visit 스택을 사용 * 시간 복잡도: O(N+E) (N: 노드 수, E: 간선 수) 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'] """ { 'A': ['B', 'C.. 2020. 10. 5.
BFS 기본 구현 BFS (Breath First Search) : - 같은 깊이에 있는 노드들을 탐색하고 그와 연결된 다음 깊이의 노드들을 탐색하는 기법 * visited, need_visit 두 개의 큐를 사용 * 시간 복잡도: O(N+E) (N: 노드 수, E: 간선 수) 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'] """ { '.. 2020. 10. 5.
탐욕 알고리즘(greedy algorithm) 1. 탐욕 알고리즘이란? - 여러 경우 중 하나를 결정해야 하는 순간마다, 최적의 선택을 진행하여 결과를 구하는 기법 - 특정 순간에 전체 조합(예, 전체 동전의 조합)을 고려하지 않고 그 순간의 최적의 선택을 시행한다 2. 탐욕 알고리즘의 문제 1. 최소 동전 개수 구하기 - 주어진 금액을 지불해야 할 때, 동전을 가장 적게 사용해 지불할 수 있는 경우 찾기 - 가장 큰 금액의 동전을 사용해 최대한 많이 지불하는 것이 매순간(지금 이 순간) 가장 좋은 선택! coin_list = [1,50,500,100] def count(value, coin_list): total_count = 0 details = list() coin_list.sort(reverse = True) for coin in coin_l.. 2020. 10. 3.
이진 탐색(binary search) 이진탐색 : 주어진 목록을 둘로 나누어 원하는 데이터를 탐색하는 기법 * 이진 탐색은 정렬되어 있는 리스트에서 수행 가능하다! * 시간 복잡도: O(log n) def binary_search(data, search): if len(data) == 1 and search == data[0]: return True if len(data) == 1 and search != data[0]: return False if len(data) == 0: return False mid = len(data) // 2 if search == data[mid]: return True else: if search > data[mid]: return binary_search(data[mid:], search) else: ret.. 2020. 10. 3.

티스토리툴바