Rootable의 개발일기

여러 노드가 있을 때 특정 2개의 노드를 연결해 1개의 집합으로 묶는 union 연산과 두 노드가 같은 집합에 속해 있는지를 확인하는 find 연산으로 구성된 알고리즘 📌 union, find 연산 union 연산 : 각 노드가 속한 집합을 1개로 합치는 연산노드 a, b가 a ∈ A, b ∈ B일 때 union(a, b) == A U Bfind 연산 : 특정 노드 a에 관해 a가 속한 집합의 대표 노드를 반환하는 연산노드 a가 a ∈ A일 때 find(a)는 A 집합의 대표 노드를 반환 📌 원리 🔎 1차원 배열 1차원 배열을 통해 초기 배열을 생성한다. 초기 배열은 인덱스가 곧 값이 되며, 이는 각 노드가 속한 집합이 없어 자신이 대표 노드가 된 상태인 것이다.   🔎 union 연산 2개의 노..

사이클 없는 양수 가중치 그래프에서 최단 거리를 구하는 알고리즘 시간 복잡도 : O(ElogV) (V : 노드 수, E : 에지 수) 📌 핵심 이론 🔎 인접 리스트 다익스트라 알고리즘은 인접 행렬보다 시각 복잡도 측면, N의 크기가 클 것을 대비해 인접 리스트로 구현하는 것이 좋다. 🔎 최단 거리 배열 초기화 최단 거리 값을 저장하기 위한 배열을 만든다. 출발 노드는 0, 나머지 노드는 매우 큰 값으로 초기화한다. 🔎 값이 가장 작은 노드 고르기 최단 거리 배열에서 현재 값이 가장 작은 노드를 고른다. 따라서, 출발 노드에서 시작하면 된다. 🔎 최단 거리 배열 업데이트 인접 리스트와 최단 거리 배열 값을 비교하여 둘 중 작은 값으로 최단 거리 배열을 갱신한다. Min(출발 노드의 최단 거리 배열의 값 +..

📌 정의 시작점을 지정하지 않고 그래프에서 모든 노드와 관련된 최단 거리를 구하는 알고리즘 📌 주요 특징 기능 특징 시간 복잡도(노드 수: V) 모든 노드 간에 최단 경로 탐색 - 음수 가중치 Edge가 있어도 수행 가능 - 동적 계획법의 원리를 이용해 알고리즘에 접근 O(V^3) 📌 핵심 이론 최단 경로를 구했다고 가정했을 때, 그것을 이루는 부분 경로 역시 최단 경로이다. 예를 들어, A에서 B까지 최단 경로를 구했다고 가정한다. 이때, 해당 경로 위에 K 노드가 존재한다면 A에서 K 노드를 거쳐 B에 도착하는 경로 역시 최단 경로라는 것이다. 따라서 점화식은 다음과 같이 도출된다. D[S][E] = Math.min(D[S][E], D[S][K] + D[K][E]) 📌 접근 방법 🔎 초기 배열 D[S..