본문 바로가기

분류 전체보기161

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.
5397-키로거 (python) 1. 내가 작성한 코드 (실패: 시간초과) - 효율성을 높이고자 pop(0) 대신, pop() 을 사용하려고 했으나 이것도 시간초과로 실패하였다 - 그 이유는 아래 핵심 로직에 있듯이, 최대 L의 길이가 1,000,000개인 것이 문제가 된다 - 시간 복잡도를 계산하면, 아래 단순 구현 코드에선 최악의 경우 O(n^2)이 나온다 - 시간제한이 1초, 컴퓨터가 1초당 대략 1억 번의 연산한다는 걸 감안할 때, 시간제한에 당연히 걸릴 것이다. - 이에 따라 다른 적절한 알고리즘을 고려해야 하고, 결과적으로 스택을 사용하는 방법을 선택하기로 한다 그리고 스택을 사용한 풀이는 두 번째 코드에 기록해두었다 tc = int(input()) for _ in range(tc): data = input() l = len.. 2020. 10. 3.
탐욕 알고리즘(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.

티스토리툴바