컴퓨터 공학/알고리즘

다익스트라 알고리즘이란?다익스트라 알고리즘은 그래프에서 하나의 시작 정점으로부터 다른 모든 정점까지의 최단 경로를 찾는 알고리즘이다. 가중치가 있는 그래프에서 최단 경로를 찾기 위해 사용되며, 음의 가중치를 가지는 간선이 없는 경우에 유효하다.  다익스트라 알고리즘은 주로 우선순위 큐를 사용하여 현재까지 발견된 최단 경로를 저장하고, 이를 기반으로 다른 정점으로의 경로를 지속적으로 업데이트하는 방식으로 작동한다. 다익스트라 알고리즘 구현문제 설명아래와 같은 가중치 그래프가 있다고 할 때, 1번 정점에서 모든 정점으로 가는 최소 거리 비용을 출력하라. (없으면 Impression 출력) 코드 구현import java.util.ArrayList;import java.util.Arrays;import java..

Union-Find (Disjoint Set)이란? Union-Find, 또는 Disjoint Set 자료구조는 서로소 집합을 관리하는 자료구조(알고리즘)이다. 이 자료구조는 여러 개의 원소들이 각각의 집합에 속해 있을 때, 두 원소가 같은 집합에 속해 있는지 확인하거나, 두 집합을 하나로 합치는 작업을 빠르게 수행할 수 있다. 이 자료구조는 그래프에서 연결된 컴포넌트를 찾거나 사이클을 검출하는 데 자주 사용된다. Union-Find 구현 방법Union-Find는 두 가지 주요 연산으로 구성된다 이름 그대로 Union 연산과 Find 연산이 그것이다. Union 연산 Union 연산은 두 집합을 하나의 집합으로 합치는 연산이다. 두 원소의 루트를 찾아 하나의 루트로 통일하는 방식으로 진행된다. 이때 랭크..