Sean :: Dev

MST,MCST (Minimun_Cost Spanning Tree) (최소비용 신장트리) Spanning Tree : undirected graph에서 n개의 모든정점과 n-1개의 간선으로 만들어진 트리 순회(traversal)를 하면 n-1개의 간선을 이동하며 모든 정점을 방문하므로 spanning tree를 생성한다. DFS로 생성되면 DFST(Depth First Spanning Tree, 깊이우선 신장트리), BFS로 생성되면 BFST(Breadth First Spanning Tree, 너비우선 신장트리)라고 한다. weighted undirected graph에서 모든 노드를 포함하고 cycle이 없으며 weight의 합이 최소인 트리를 MST or MCST(Minimum Cost Spannin..

DFS (Depth First Search) (깊이 우선 탐색) LIFO(Last-In First-Out), Stack 활용 PseudoCode recursive non-recursive 1 non-recursive 2 예제 Input Output 첫 줄에 정점의 개수 N과 간선의 개수 M이 주어집니다. 다음 M줄에 간선의 관계 시작정점 u와 도착정점 v가 주어집니다. 입력에 따른 깊이 우선 탐색 결과를 출력합니다. import java.util.*; public class Test { static boolean edge[][]; static boolean visited[]; static int n; static int m; public static void main(String args[]) { Sca..

Two Pointer 2개의 지점(포인터)을 옮겨가며 답을 구한다. 순차적 접근 등이 요구되는 특수한 상황에서 사용된다. ex) 정렬된 두 배열을 하나의 정렬된 배열로 합칠 때(Merge Sort에서 사용됨), 어떤 배열의 연속 부분집합의 원소합이 k인 경우를 찾는 경우 등 ... 자세한 내용은 Merge Sort 부분 참고 Sliding Window Two pointer와 비슷하지만, 두 포인터 사이의 길이가 고정되어있다는 차이가 있다. Input Output 첫 번째 줄에는 배열 D의 원소의 개수 N과 윈도우 사이즈 K 가 주어지고, 두 번째 줄에는 배열의 원소 Di가 주어집니다. (Di 는 자연수) 배열 D의 길이가 K인 연속부분집합의 원소 합의 최대값을 출력합니다. import java.util...

# Heap Sort (힙 정렬) # Tree Sort (트리 정렬)

Shell Sort (셸 정렬) https://gmlwjd9405.github.io/2018/05/08/algorithm-shell-sort.html 일정간격으로 부분집합을 구성하고, 각 부분집합에 대해 삽입정렬을 수행. 간격을 줄여가며 반복. 부분집합을 만드는 기준이 되는 간격 값에 따라 성능 좌우 일반적으로 시간 복잡도는 O(n1.25~1.5)로 측정 삽입정렬보다는 개선된 방법 import java.lang.Math; import java.util.Scanner;; public class Test { public static void printArray(int[] arr) { for(int i=0; i

Quick Sort (퀵 정렬) 기준값(pivot)을 잡고, pivot보다 작은수는 좌partition으로 큰수는 우partition으로 보낸다. 다시 좌/우partition에서 각각 pivot을 설정하고 좌/우partition으로 나눈다. 이러한 과정 반복 divide & conquer pivot을 설정하는 방법이 다양하고, 이에 따라 성능이 결정된다. (pivot을 좌우끝값 또는 중앙값으로 등등..) 평균 시간 복잡도 : O(nlog2n) 최악 시간 복잡도 : O(n2) 구현방법이 제각각, 다양하다 import java.lang.Math; import java.util.Scanner;; public class Test { public static void printArray(int[] arr) { f..

Selection Sort (선택 정렬) 0번째 자리와 '1번째-N-1번째 중에서 가장 작은 값'을 교환, 1번째 자리와 '2번째-N-1번째 중에서 가장 작은 값'을 교환, ... 평균/최악 시간 복잡도 : O(n2) import java.lang.Math; import java.util.Scanner;; public class Test { public static void printArray(int[] arr) { for(int i=0; i

Sieve of of Eratosthenes (에라토스테네스의 체) 소수판별 알고리즘 필요한 범위의 배열 생성후, 2부터 시작해서 차례대로 배수들을 소수가 아닌것으로 체크 최적화 첫번째 반복문의 범위를 1-N이 아닌 1-sqrt(N)으로 바꿔 속도 향상 가능. A의 약수를 구할때 1-sqrt(A)까지만 구하면 되는것은 자명하다. 해당범위내에서 N번째 소수를 구하는 경우라면, 1-N까지 모두 돌려야하겠지만 해당범위내에서 특정숫자 N이 소수인지 판별하는 경우라면, 1-sqrt(N)으로 최적화 가능. import java.lang.Math; import java.util.Scanner;; public class Test { private final static int MAX = 50; static boolea..