신장 트리(Spanning Tree) 원래 그래프의 모든 노드가 연결되어 있으면서 트리의 속성을 만족하는 그래프 신장 트리의 조건 본래의 그래프의 모든 노드를 포함해야 함 모든 노드가 서로 연결 트리의 속성을 만족시킴 (사이클이 존재하지 않음) 최소 신장 트리(Minimum Spanning Tree, MST) 가능한 Spanning Tree 중에서, 간선의 가중치 합이 최소인 Spanning Tree를 지칭함 최소 신장 트리 알고리즘 그래프에서 최소 신장 트리를 찾을 수 있는 알고리즘이 존재함 대표적인 최소 신장 트리 알고리즘 Kruskal’s algorithm(크루스칼 알고리즘), Prim's algorithm(프림 알고리즘) 크루스칼 알고리즘(Kruskal's algorithm) 모든 정점을 독립적인..

최단 경로 문제최단 경로 문제란 두 노드를 잇는 가장 짧은 경로를 찾는 문제임가중치 그래프 (Weighted Graph)에서 간선 (Edge)의 가중치 합이 최소가 되도록 하는 경로를 찾는 것이 목적 최단 경로 문제 종류단일 출발 및 단일 도착(single-source and single-destination shortest path problem) 최단 경로 문제그래프 내의 특정 노드 u에서 출발해서 또 다른 특정 노드 v에 도착하는 가장 짧은 경로를 찾는 문제단일 출발(single-source shortest path problem) 최단 경로 문제그래프 내의 특정 노드 u와 그래프 내 다른 모든 노드 각각의 가장 짧은 경로를 찾는 문제다익스트라 알고리즘에 해당전체 쌍(all-pair) 최단 경로그래..

** 탐욕 알고리즘(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 d..

** DFS 알고리즘 구현 자료구조 스택과 큐를 활용함 need_visit 스택과 visited 큐, 두 개의 자료 구조를 생성 BFS 자료구조는 두 개의 큐를 활용하는데 반해, DFS 는 스택과 큐를 활용한다는 차이가 있음을 인지해야 함 큐와 스택 구현은 별도 라이브러리를 활용할 수도 있지만, 간단히 파이썬 리스트를 활용할 수도 있음 def dfs(graph, start_node): visited, need_visit = list(), list() need_visit.append(start_node) while need_visit: node = need_visit.pop() # BFS와 차이: 스택 정책 if node not in visited: visited.append(node) need_visit..

** BFS와 DFS 대표적인 그래프 탐색 알고리즘 너비 우선 탐색 (Breadth First Search): 정점들과 같은 레벨에 있는 노드들 (형제 노드들)을 먼저 탐색하는 방식 깊이 우선 탐색 (Depth First Search): 정점의 자식들을 먼저 탐색하는 방식 ** BFS/DFS 방식 이해를 위한 예제 BFS 방식: A - B - C - D - G - H - I - E - F - J 한 단계씩 내려가면서, 해당 노드와 같은 레벨에 있는 노드들 (형제 노드들)을 먼저 순회함 DFS 방식: A - B - D - E - F - C - G - H - I - J 한 노드의 자식을 타고 끝까지 순회한 후, 다시 돌아와서 다른 형제들의 자식을 타고 내려가며 순화함 ** 파이썬으로 그래프를 표현 파이썬에서..

** 그래프(Graph) 실제 세계의 현상이나 사물을 노드와 간선으로 표현 ** 그래프 관련 용어 노드 (Node): 위치 (= 정점, Vertex) 간선 (Edgd): 위치 간의 관계를 표시한 선, 노드를 연결한 선 (= Link, Branch) 인접 정점(Adjacent Vertex): 간선으로 직접 연결된 노드 참고 용어 정점의 차수 (Degree): 무방향 그래프에서 하나의 정점에 인접한 정점의 수 진입 차수 (In-Degree): 방향 그래프에서 외부에서 오는 간선의 수 진출 차수 (Out-Degree): 방향 그래프에서 외부로 향하는 간선의 수 경로 길이 (Path Length): 경로를 구성하기 위해 사용된 간선의 수 단순 경로 (Simple Path): 처음 정점과 끝 정점을 제외하고 중복..