본문 바로가기

알고리즘141

[코딩 + 알고리즘 완주반] 22일차. 최소 신장 트리 # 신장 트리 (Spanning Tree) 그래프의 모든 노드가 연결되어 있으면서 트리의 속성을 만족하는 그래프 모든 노드 포함, 모든 노드 서로 연결, 사이클 존재하지 않음 # 최소 신장 트리 (Minimum Spanning Tree, MST) 가능한 신장 트리 중에서 간선의 가중치 합이 최소인 Spanning Tree Kruskal's algorithm(크루스칼 알고리즘), Prim's algorithm(프림 알고리즘) # Kruskal's algorithm(크루스칼 알고리즘) 가중치가 가장 작은 간선부터 연결 ( 사이클일 경우 넘어감 ) # Union-Find 알고리즘 - 사이클이 생기는지 확인하는 알고리즘 Disjoint Set을 표현할 때 사용하는 알고리즘으로 트리 구조를 활용하는 알고리즘 Di.. 2021. 4. 9.
[코딩 + 알고리즘 완주반] 21일차. 최단 경로 알고리즘 # 최단 경로 문제 두 노드를 잇는 가장 짧은 경로 찾기 가중치 그래프에서 간선의 가중치 합이 최소가 되도록 하는 경로 # 단일 출발 및 단일 도착 최단 경로 문제 특정 노드에서 특정 노드에 도착하는 가장 짧은 경로 찾기 # 단일 출발 최단 경로 문제 특정노드와 그래프 내 모든 노드 각각의 가장 짧은 경로 찾기 # 전체 쌍 최단 경로 그래프 내 모든 노드 쌍에 대한 최단 경로 찾기 # 다익스트라 알고리즘 - 너비우선 탐색(BFS)과 유사 하나의 정점에서 다른 모든 정점 간의 각각 가장 짧은 거리 구하기 (단일 출발 최단 경로 문제) 첫 정점을 기준으로 연결되어 있는 정점들을 추가해가며, 최단 거리를 갱신 # 우선순위 큐를 활용한 다익스트라 알고리즘 초기 첫 정점의 거리는 0, 나머지는 무한대로 저장 우선.. 2021. 4. 9.
[코딩 + 알고리즘 완주반] 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.
[LEET CODE] 706. Design HashMap # Problem Design a HashMap without using any built-in hash table libraries. Implement the MyHashMap class: MyHashMap() initializes the object with an empty map. void put(int key, int value) inserts a (key, value) pair into the HashMap. If the key already exists in the map, update the corresponding value. int get(int key) returns the value to which the specified key is mapped, or -1 if this map c.. 2021. 4. 5.
반응형

티스토리툴바