본문 바로가기

알고리즘/알고리즘 종류3

[MST] 최소 스패닝 트리 - 크루스칼(Kruskal), 프림(Prim) MST란? 최소 신장 트리(Minimum Spanning Tree)로 가중 그래프(Weight Graph)에서 가장 적은 비용(Weight)으로 모든 정점(Vertex)으로 이동할 수 있는 부분 그래프(Sub Graph)이다. MST는 각 정점에서 정점 사이에 하나의 간선(Edge)만 필요하므로 총 N-1 개의 간선을 가지게 되므로 마치 트리의 형태를 하고 있어서 트리라는 이름이 붙는다.크루스칼 알고리즘 1. 모든 간선을 비용이 적은 순서를 기준으로 정렬한다. - Sort2. 간선에 붙은 정점 u와 v를 기준으로 부모를 찾는다. - Find3. 정점 u의 부모와 정점 v의 부모가 다르다면 서로 다른 집합에 속해있지만, 1번 과정으로 인해 해당 간선이 두 정점의 최소 비용의 간선임을 알 수 있으므로 하나의.. 2024. 7. 11.

[최단경로] Bellman-Ford Algorithm 최단경로 알고리즘package com.study.datastructrue.mst;import java.util.ArrayList;import java.util.Arrays;class Pair { T node; V cost; public Pair(T node, V cost) { this.node = node; this.cost = cost; }}public class BellmanFord { static long[] dist = new long[6]; public static void main(String[] args) { // 집 1, 학교 2, 박물관 3, 영화관 4, 마트 5 ArrayList>> graph = inpu.. 2024. 7. 6.

[이분 탐색] 이분 탐색(Binary Search) 이란 ? 이분 탐색 두 이, 나눌 분을 써서 이분인가? 정답, 이분 탐색은 두개로 나누어서 탐색하는 것이다. 예를 들어, 1부터 10까지 있다고 생각해보자. {1, 2, 3, 4, 5, 6, 7, 8, 9, 10} 우리가 8을 찾을 때, 눈으로 바로 보이니까 위치를 파악할 수 있다. 하지만 몇 번째에 있는가? 배열은 0번째부터 시작하니 7번째에 있다는 것을 알 수 있다. 컴퓨터 배열 인덱스 개념이 없는 사람들은 8번째라고 답할 것이다. 즉, O(1) 시간이다. 그럼, {1, 4, 7, 10, 12, 23, 30, 35, 100, 120} 이 있을 때, 35의 위치는? 우리는 앞에서 값을 세어가면서 몇 번째에 있는지 알 것이다. 즉, O(N) 시간이다. 100만개의 숫자가 있다면? 우리는 100만개를 일일이 세다가.. 2024. 2. 1.

이전 1 다음

티스토리툴바