Dogfootruler Kim

신장트리(Spanning Tree)란? 1. N개의 정점 2. N-1개의 간선 3. 사이클이 존재하지 않는다. 위 3가지 조건을 갖춘 트리를 신장트리라고 한다. 최소 신장 트리란? (Minimum Spanning Tree) 무향 가중치 그래프에서 신장 트리를 구성하는 간선들의 가중치의 합이 최소인 신장트리를 말한다. MST 알고리즘 종류 크루스칼(Kruskal) - 간선중심 프림(Prim) - 정점 중심 따라서, 간선 적으면 크루스칼, 간선 많으면 프림을 사용하면 된다. 크루스칼 알고리즘 - 간선을 하나씩 선택해서 MST를 찾는 알고리즘 최초, 모든 간선을 가중치에 따라 오름차순으로 정렬 가중치가 가장 낮은 간선부터 선택하면서 트리를 증가시 사이클이 존재하면 다음으로 가중치가 낮은 간선 선택 - 사이클 ..

최단 경로 알고리즘 주어진 노드(node)와 간선(edge)들 중, 가장 짧은 경로를 찾는 알고리즘이다. 최단 경로 문제는 아래와 같이 3가지로 주어질 수 있다. 1. 특정 노드에서 시작해 특정 노드까지 도착하는 가장 짧은 경로 2. 특정 노드에서 시작해 모든 노드까지 도착할 수 있는 가장 짧은 경로 이동 경로 양수 시, Dijkstra 알고리즘 이동 경로 음수 포함 시, Bellman-ford 알고리즘 3. 모든 노드에서 시작해 모든 노드까지 도착할 수 있는 가장 짧은 경로 (Floyd Warshall 알고리즘) 다익스트라 알고리즘 (Dijkstra Algorithm) 다익스트라 알고리즘은 특정 노드에서 시작해 인접한 노드의 가장 짧은 경로들을 탐색하며 모든 노드의 최소 경로를 구하는 알고리즘이다. G..

LIS(Longest increasing Subsequence)란, 가장 긴 증가하는 부분 수열이다. 예를 들어, [6, 2, 5, 1, 7, 4, 8, 3] 이라는 배열이 있을 경우, LIS는 [2, 5, 7, 8]이 된다. 증가하는 부분 수열 중 가장 긴 것이기 때문. LIS를 풀기 위한 가장 일반적인 방법은 DP를 이용하는 것이다. dp = [1]*n for i in range(n): for j in range(i): #첫번째 요소부터 i번째까지 위와 비교 if arr[i] > arr[j]: #뒤에 있는 요소(arr[i])가 크면 dp[i] = max(dp[i], dp[k]+1) 위 알고리즘의 시간복잡도는 O(n^2)을 갖게 됩니다. 시간복잡도를 개선하기 위해서는 이분탐색을 활용합니다. 주어진 배열..

유니온 파인드(Union-Find)는 트리형태를 갖는 자료구조이다. 합집합 찾기 및 상호 배타적 집합(Disjoint-set)이라고도 한다. 이름 그대로 상호 배타적인 부분 집합들로 나누어진 원소들을 저장하고 조작하는데 사용된다. 유니온 파인드(Union-Find)의 기능에 대해서 설명해보겠다. 1) Union : 두 집합을 하나의 집합으로 합치는 연산 2) Find : 어떤 원소 x가 주어졌을 때 이 원소가 속한 집합을 반환 위와 같이 두 가지 연산을 해주는 자료구조라고 할 수 있다. 정의를 알았다면 구현을 해보자 ! 구현 1. 초기화 parent 배열을 만들어준다. 파이썬 parent[a] = b #배열은 a 원소의 부모는 b이다. 라는 뜻으로 해석하면 된다. #초기화 시작 parent[i] = i ..