Rootable의 개발일기

이미 정렬된 데이터 범위에 정렬되지 않은 데이터를 적절한 위치에 삽입시켜 정렬하는 방식 시간 복잡도 : O(N^2) 선택 데이터를 현재 정렬된 데이터 범위 내에서 적절한 위치에 삽입하는 것 📌 정렬 과정 현재 index에 있는 데이터 값을 선택 현재 선택한 데이터가 정렬된 데이터 범위에서 삽입될 위치를 탐색 처음 자신보다 작은 값이 나올 때까지(오름차순) 처음 자신보다 큰 값이 나올 때까지(내림차순) 삽입 위치부터 index 위치까지 shift 연산(우측 이동)을 수행 삽입 위치에 현재 선택한 데이터를 삽입하고 index++연산을 수행 마지막 index까지, 즉 선택할 데이터가 없을 때까지 반복 📌 알고리즘 import java.io.IOException; public class Main { public..

데이터의 인접 요소끼리 비교하고, swap 연산을 수행하며 정렬하는 방식 시간 복잡도: O(N^2) 📌 정렬 과정 비교 연산이 필요한 루프 범위를 설정 인접한 데이터 값을 비교 swap 조건에 부합하면 swap 연산 루프 범위가 끝날 때마다 2~3 반복 정렬 영역을 설정한다. 다음 루프를 실행할 때는 이 영역을 제외 비교 대상이 없을 때까지 1~5 반복 만약 특정한 루프의 전체 영역에서 swap이 한 번도 발생하지 않았다면 그 영역 뒤에 있는 데이터가 모두 정렬됐다는 뜻이므로 프로세스를 종료해도 됨 📌 알고리즘 public class BubbleSort { public static void main(String[] args) throws IOException { BufferedWriter bw = new..

대상 데이터에서 최대나 최소 데이터를 데이터가 나열된 순으로 찾아가며 선택하는 방법 시간 복잡도: 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..