정용이의 놀이동산

import java.util.HashSet; import java.util.Set; /** * Recursive */ public class Recursive { static Set subSet = new HashSet(); static int n = 3; static Set permutation = new HashSet(); static boolean[] visited; static int range = 5; static int size = 3; public static void main(String[] args) { makeSubSet(1); visited = new boolean[range + 1]; makePermutation(1); } static void makeSubSet(int k) { ..

소개 정렬된 배열에 특정 원소가 존재하는지를 O(log n)의 시간에 파악할 수 있는 알고리즘. 구현은 반반반 방법과 매 라운드마다 폭을 줄이며 건너뛰는 방법이 있다. 반반반 방법은 흔히 볼 수 있는 구현방법이다. 매 단계마다 배열의 중앙값을 살펴본다. 중앙값이 찾는 값이면 true를 반환한다. 중앙값과 찾는 값이 다르면, 중앙값과 대소비교를 통해서 탐색 배열을 절반으로 줄인다. 마지막 단계까지 찾지 못하면 해당 배열에 찾는 값이 없음을 의미한다. 구현 // 반반반 구현 public boolean binarySearch(int[] arr, int target) { int start = 0; int end = n - 1; while(start target) { end = middle - 1; } else ..

소개 매우 빠른 정렬 알고리즘입니다. 피벗(pivot)을 기준으로 그룹을 나누어 모든 그룹에 요소가 1개일 때 정렬을 마칩니다. 배열의 요소가 n개 있을 때 시간복잡도는 O(n log n) 구현 // 분할 정복 패러다임 public class QuickSort { public void quickSort(int[] arr, int left, int right) { int pl = left; int pr = right; int pivot = arr[(pl + pr) / 2]; do { // 피벗보다 큰 요소를 찾습니다. while (arr[pl] pivot) { pr--; } // 왼쪽과 오른쪽 포인터가 서..

소개 도널드 쉘(Donald L. Shell)이 고안한 정렬 알고리즘입니다. 삽입 정렬의 장점은 살리고, 단점은 보완한 정렬 알고리즘입니다. 단순 삽입 정렬 장점 : 정렬을 마친 상태에 가까울수록 정렬속도가 높아짐 단점 : 삽입할 위치가 멀수록 이동횟수가 증가함 정렬할 배열의 요소를 그룹으로 나누어 그룹별 삽입정렬(H-정렬)을 수행합니다. 그룹을 합치며 정렬을 반복합니다. 증분값 H는 초깃값이 너무 크면 효과가 없습니다. n(배열의 요솟수)/9 값을 넘지 않도록 합니다. 배열의 요소가 n개 있을 때 시간복잡도는 O(n^1.25) 구현 public class ShellSort { public void shellSort(int[] arr) { // 증분값 h int h; // h의 초기값을 구합니다. for..

소개 선택한 요소를 선택한 위치의 앞쪽에 있을 수 있는 올바른 위치에 삽입합니다. 2번 째 요소부터 선택해서 정렬 작업을 수행합니다. 선택한 요소 앞쪽은 항상 정렬되어 있는 구간입니다. 정렬이 수행되면서 정렬된 구간을 탐색하는 내부 반복문의 반복 횟수는 증가합니다. 배열의 요소가 n개 있을 때 시간복잡도는 O(n^2) 구현 public class InsertionSort { static void insertionSort(int[] arr) { // 정렬은 배열의 2번째 요소부터 시작합니다. for (int i = 1; i < arr.length; i++) { int j; int temp = arr[i]; // 정렬된 구간을 뒤에서부터 앞으로 순회한다. // 처음 temp와 arr[j]는 같은 대상이다. ..

소개 가장 작은 요소부터 선택하여 순서대로 정렬하는 알고리즘입니다. 선택 --> 교환 --> 정렬이 반복됩니다. 정렬은 배열의 앞쪽부터 이뤄집니다. 선택할 요소를 고르는 구간은 뒤쪽으로 점점 좁아집니다. 배열의 요소가 n개 있을 때 시간복잡도는 O(n^2) 구현 public class SelectionSort { static void selectionSort(int[] arr) { // 앞쪽부터 순서대로 정렬합니다. for (int i = 0; i < arr.length; i++) { // 가장 작은 값의 인덱스를 찾기 위해 초기화합니다. int min = i; for (int j = i + 1; j < arr.length; j++) { // 탐색 과정에서 더 작은 값이 있다면 해당 값의 인덱스를 저장합..

소개 이웃한 두 수의 크기를 비교하여 교환을 반복합니다. 매 라운드마다 1개씩 요소가 앞쪽부터 정렬됩니다. 정렬은 앞쪽부터 이뤄지고, 라운드 별 수의 크기 비교는 뒤쪽부터 시작됩니다. 배열의 요소가 n개 있을 때 시간복잡도는 O(n^2) 구현 public class BubbleSort { static void bubbleSort(int[] arr) { // 배열 앞쪽부터 정렬해간다. for (int i = 0; i i; j--) { if (arr[j - 1] > arr[j]) { swap(arr, j - 1, j); } } }..

개요 그리디 기반의 최소 신장 트리(MST, Minimum Spanning Tree)를 구하는 알고리즘 간선을 다 떼어내고 가중치 순으로 간선들을 조회하며, 사이클이 생기지 않으면 간선을 노드에 연결한다. 알고리즘 실행을 마친 후에는 모든 노드가 연결된 MST가 완성된다. 가중치를 오름차순으로 정렬하여 연결하면 최소 신장 트리, 가중치를 내림차순으로 정렬하여 연결하면 최대 신장 트리를 구할 수 있다. MST를 만들기 위해서는 반드시 최소 가중치 간선이 포함되어야 하므로, 크루스칼 알고리즘의 결과는 항상 MST이다. 구현 그래프를 간선 리스트 형태로 구현하는 게 편리하다. 간선이 사이클이 형성되는지 파악하고, 간선을 연결하기 위해서 유니온-파인드 자료구조를 사용한다. 노드가 n개, 간선이 m개일 때, 간선..

개요 모든 노드에서 모든 노드까지의 최단 경로를 계산하는 알고리즘이다. 알고리즘을 한 번 실행함으로써 모든 노드 간 최단 경로를 계산할 수 있다. 노드 간 거리를 저장하기 위해서 행렬을 사용한다. 행렬의 초깃값은 그래프의 인접 행렬과 같다. 매 라운드마다 각 경로에서 중간 노드로 사용할 노드를 선택하여 거리를 줄여나간다. 구현 3중 반복문으로 쉽게 구현할 수 있다. 가장 바깥쪽은 중간 노드이고, 2번째, 3번째는 경로를 계산할 대상 노드이다. 각 반복문은 그래프의 노드 개수만큼 수행되므로, 노드 개수 n에 대하여 시간복잡도는 O(n^3)이다. Java int INF = 무한, 알고리즘 구현 상 도출될 수 없는 큰 값으로 선언함. int [] [] adj; int [] [] dist; ... void fl..

개요 특정 노드에서 다른 모든 노드 간 최단 경로를 계산하는 알고리즘이다. 벨만-포드 알고리즘보다 효율적이다. 가중치에 음수가 없는 그래프에서만 사용할 수 있다. 벨만 포드처럼 각 노드까지의 거리를 INF로 초기화하고 탐색과정에서 값을 줄인다. 알고리즘의 각 단계에서는 아직 처리하지 않은 노드 중 거리가 가장 작은 노드를 먼저 선택하고, 해당 노드에서 시작하는 모든 간선을 보며 다른 노드까지의 거리를 줄일 수 있다면 줄인다. 음수 가중치가 없다고 전제하여 모든 간선을 단 한 번만 처리한다. 그래서 매우 효율적이다. 각 노드를 처리한 뒤에는 해당 노드까지의 거리가 절대 변하지 않는다. 음수 간선이 존재하면 사용할 수 없다. 구현 효율적인 구현을 위해서는 아직 처리하지 않은 노드 중 거리가 가장 짧은 노드를..