위상 정렬(Topological Sort)이란?위상 정렬은 순서가 정해져 있는 작업들을 올바른 순서대로 나열하는 알고리즘입니다.쉽게 말해, 어떤 작업이 다른 작업보다 먼저 수행되어야 할 때, 그 선후 관계를 지키면서 전체 순서를 구하는 방법입니다.예를 들어,선수 과목이 있는 과목 수강 순서빌드 의존성이 있는 프로젝트 컴파일 순서작업 간 선행 조건이 있는 스케줄링같은 문제에서 자주 사용됩니다.1. 위상 정렬의 핵심 개념위상 정렬은 방향 그래프(Directed Graph) 에서 사용합니다.그리고 아무 그래프에서나 가능한 것은 아니고, 반드시 사이클이 없는 방향 그래프(DAG, Directed Acyclic Graph) 이어야 합니다.왜 사이클이 있으면 안 될까?예를 들어,A를 하려면 B가 먼저 필요B를 하려..

플로이드-워셜(Floyd-Warshall) 알고리즘 정리그래프 문제를 풀다 보면 한 정점에서 다른 정점까지의 최단 거리를 구해야 하는 경우가 자주 나옵니다.그중에서도 모든 정점 쌍 사이의 최단 거리를 한 번에 구하고 싶을 때 사용하는 대표적인 알고리즘이 바로 플로이드-워셜 알고리즘입니다.다익스트라 알고리즘은 보통 한 출발점에서 다른 모든 정점까지의 최단 거리를 구하는 데 적합하지만,플로이드-워셜은 모든 정점에서 모든 정점으로 가는 최단 거리를 구하는 데 강력합니다.이번 글에서는 플로이드-워셜 알고리즘의 개념, 동작 원리, 시간 복잡도, 그리고 자바 구현까지 차근차근 정리해보겠습니다.1. 플로이드-워셜 알고리즘이란?플로이드-워셜 알고리즘은 모든 정점 쌍 사이의 최단 거리(All-Pairs Shortest ..

안녕하시렵니까..오늘은 유니온-파인드에 대해서 알아보겠습니다! 유니온 파인드(Union-Find) 알고리즘 정리알고리즘 문제를 풀다 보면 서로소 집합(Disjoint Set) 을 다루는 문제가 자주 나온다.이때 가장 대표적으로 사용하는 자료구조가 바로 유니온 파인드(Union-Find) 이다.유니온 파인드는 이름 그대로Union: 두 집합을 합치기Find: 어떤 원소가 어느 집합에 속하는지 찾기를 빠르게 처리하기 위한 알고리즘이다.보통 다음과 같은 문제에서 많이 사용된다.두 노드가 같은 그룹인지 판별네트워크 연결 여부 확인사이클 판별크루스칼(Kruskal) 최소 스패닝 트리1. 정의유니온 파인드는 서로 겹치지 않는 여러 집합을 관리하는 자료구조이다.예를 들어 원소가 1, 2, 3, 4, 5, 6 이 있..

프림(Prim) 알고리즘 완전 정리1. 정의프림(Prim) 알고리즘은 가중치가 있는 무방향 그래프에서 최소 신장 트리(MST, Minimum Spanning Tree) 를 구하는 알고리즘이다.먼저 최소 신장 트리부터 보면,신장 트리: 모든 정점을 포함하면서 사이클이 없는 트리최소 신장 트리: 그중에서 간선 가중치의 합이 가장 작은 트리즉, 프림 알고리즘은모든 정점을 최소 비용으로 연결하는 방법을 찾는 알고리즘이라고 보면 된다.프림 알고리즘의 핵심은 탐욕법(Greedy) 이다.현재까지 선택한 정점 집합에서 아직 방문하지 않은 정점으로 가는 간선 중 가장 가중치가 작은 간선을 계속 선택한다.특징무방향 그래프에서 사용최소 신장 트리(MST) 를 구할 때 사용시작 정점 하나를 정하고 점점 트리를 확장하는 방식우..