Rootable의 개발일기

대상 데이터에서 최대나 최소 데이터를 데이터가 나열된 순으로 찾아가며 선택하는 방법 시간 복잡도: O(N^2) 최솟값 또는 최댓값을 찾고, 남은 정렬 부분의 가장 앞에 있는 데이터와 swap하는 것 📌 정렬 과정 남은 정렬 부분에서 최솟값 또는 최댓값을 찾는다. 남은 정렬 부분에서 가장 앞에 있는 데이터와 선택된 데이터를 swap 가장 앞에 있는 데이터의 위치를 변경해(index++) 남은 정렬 부분의 범위를 축소 전체 데이터 크기만큼 index가 커질 때까지, 즉 남은 정렬 부분이 없을 때까지 반복 (반드시 N^2만큼 수행하므로 시간 복잡도를 줄이기 힘들다) 📌 알고리즘 public class SelectionSort { public static void main(String[] args) throws..

그래프에서 모든 노드를 연결할 때 사용된 에지들의 가중치의 합을 최소로 하는 트리 📌 특징 사이클이 포함되면 가중치의 합이 최소가 될 수 없으므로 사이클을 포함하지 않는다. N개의 노드가 있으면 최소 신장 트리를 구성하는 에지의 개수는 항상 N - 1개다. 최소 신장 트리를 만드는 알고리즘으로 크루스칼과 프림이 있다. 📌 크루스칼(Kruskal) 알고리즘 최소 신장 트리를 만드는 알고리즘(Union-Find 이용) 🔎 에지 리스트(Edge List) 데이터를 노드가 아닌 에지 중심으로 저장하므로 인접 리스트가 아닌 에지 리스트의 형태로 저장한다. 클래스는 일반적으로 출발, 도착 노드와 가중치 변수로 구성된다. class Edge { int start; int end; int weight; public E..

여러 노드가 있을 때 특정 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(출발 노드의 최단 거리 배열의 값 +..