본문 바로가기

전체 글264

[코딩 + 알고리즘 완주반] 20일차. 탐욕 알고리즘 (Greedy algorithm) # 탐욕 알고리즘(Greedy Algorithm) 최적의 해에 가까운 값을 구하기 위해 사용 여러 경우 중 하나를 결정해야할 때마다, 매순간 최적이라고 생각되는 경우를 선택하는 방식으로 진행 # 문제1 ) 동전 문제 지불해야 하는 값을 동전의 수가 가장 적게 지불하기 가장 큰 동전부터 최대한 지불해야하는 값을 채우는 방식 지불해야 하는 값 : 4720 1원, 50원, 100원, 500원 동전 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 =.. 2021. 4. 6.
[코딩 + 알고리즘 완주반] 20일차. 너비 우선 탐색(Breadth-First Search ), 깊이 우선 탐색(Depth-First Search) # 너비 우선 탐색 (BFS) 정점들과 같은 레벨에 있는 노드들을 먼저 탐색 # 깊이 우선 탐색 (DFS) 정점의 자식들을 먼저 탐색하는 방식 # BFS 알고리즘 구현 자료구조 큐 활용 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'] def bfs(graph, start_node): visited = list() need.. 2021. 4. 6.
[코딩 + 알고리즘 완주반] 19일차. 그래프 이해와 자료구조 # 그래프 실제 세계의 현상이나 사물을 정점( 또는 노드)와 간선으로 표현 # 그래프 관련 용어 노드 (Node) : 정점(Vertex) , 위치 간선 (Edge) : 위치 간의 관계를 표시한 선으로 노드를 연결한 선 (link 또는 branch) 인접 정점 (Adjacent Vertex) : 간선으로 직접 연결된 정점 (또는 노드) 정점의 차수(Degree) : 무방향 그래프에서 하나의 정점에 인접한 정점의 수 진입 차수(In-Degree) : 방향그래프에서 외부에서 오는 간선의 수 진출 차수(Out-Degree) : 방향 그래프에서 외부로 향하는 간선의 수 경로 길이 (Path Length) : 경로를 구성하기 위해 사용된 간선의 수 단순 경로(Simple Path) : 처음 정점과 끝 정점을 제외하.. 2021. 4. 5.
[코딩 + 알고리즘 완주반] 19일차. 이진탐색( Binary Search ), 순차탐색 ( Sequential Search ) # 이진 탐색 탐색할 자료를 둘로 나누어 해당 데이터가 있을만한 곳을 탐색하는 방법 # 분할 정복 알고리즘 divide : 문제를 하나 또는 둘 이상으로 나눈다 conquer : 나눠진 문제가 충분히 작고 해결이 가능하다면 해결하고, 그렇지 않으면 다시 나눈다 # 이진탐색 divide : 리스트를 두 개의 서브 리스트로 나눈다 conquer : 검색할 숫자 > 중간값이면 뒷부분의 서브 리스트에서 검색할 숫자를 찾는다 검색할 숫자 < 중간값이면 앞부분의 서브 리스트에서 검색할 숫자를 찾는다 # 알고리즘 구현 def binary_search(data, search): print (data) if len(data) == 1 and search == data[0]: return True if len(data) .. 2021. 4. 5.
[LEET CODE] 347. Top K Frequent Elements( zip 함수, * (아스테리스크)) # Problem Given an integer array nums and an integer k, return the k most frequent elements. You may return the answer in any order. Constraints: 1 List[int]: freqs = collections.Counter(nums) freqs_heap = [] # 힙에 음수로 삽입 for f in freqs: heapq.heappush(freqs_heap, (-freqs[f], f)) topk = list() # k번 만큼 추출, 민 힙 이므로 가장 작은 음수 순으로 추출 for _ in range(k): topk.append(heapq.heappop(freqs_heap)[1]) return .. 2021. 4. 5.
[LEET CODE] 3. Longest Substring Without Repeating Characters # Problem Given a string s, find the length of the longest substring without repeating characters. Constraints: 0 2021. 4. 5.
반응형

티스토리툴바