풀소유

위상 정렬(Topological Sorting)은 사이클이 없는 방향 그래프에서 노드 순서를 찾는 알고리즘이다. 위상 정렬에서는 항상 유일한 값으로 정렬되지 않는다. 시간 복잡도는 O(노드의 수:V + 에지 수:E)이다. DFS를 이용하는 방법과 BFS를 이용하는 방법이 있다. 위상 정렬 수행 과정진입 차수가 0인 노드를 큐에 저장한다.큐에서 데이터를 poll 해 해당 노드를 탐색 결과에 추가하고, 해당 노드가 가리키는 노드의 진입 차수를 1씩 감소한다.감소했을 때 진입 차수가 0이 되는 노드를 큐에 offer 한다.큐가 빌 때까지 1~3을 반복한다. import java.util.*; public class topologicalSort { public static List topologicalSort(..

퀵선택 알고리즘은 특정 위치의 원소를 찾는 데 사용되는 효율적인 분할 정복 알고리즘 중 하나이다. 퀵정렬 알고리즘 일부를 이용하여 전체를 정렬하지 않고 특정 위치의 원소를 찾을 수 있다. 이 알고리즘의 평균 시간 복잡도는 O(n)이며, 최악의 경우에 O(n^2)이 될 수 있다. 동작 순서 피벗 선택: 배열에서 피벗을 선택한다. 일반적으로 배열의 가운데 원소를 선택한다. 분할: 피벗을 기준으로 배열을 두 그룹으로 나눈다. 작은 원소는 피벗 왼쪽에 위치하고, 큰 원소는 오른쪽에 위치한다. 쿼리 위치 확인: 찾고자 하는 원소의 위치를 확인한다. 이 위치가 현재 피벗의 위치와 일치하면 찾은 것이다. 재귀적으로 반복: 찾고자 하는 위치가 피벗의 위치보다 작으면 왼쪽 부분 배열에서 반복적으로 알고리즘을 수행한다. ..

유니온-파인드(Union-Find) 알고리즘은 여러 집합을 효율적으로 관리하는 데 사용되는 알고리즘이다. 주로 서로소 집합(disjoint-set)을 다루는 데에 활용된다. 유니온-파인드 알고리즘은 각 집합을 대표하는 원소를 찾거나, 두 집합을 합치는 등의 연산을 수행할 수 있다. 대표적으로 "합집합 찾기(Union)"와 "찾기(Find)" 연산이 있다. 간단한 버전 class UnionFind { private final int[] parent; public UnionFind(int size) { this.parent = new int[size]; for (int i = 0; i < size; i++) { parent[i] = i; } } public void union(int x, int y) { i..

단순 선택 정렬 단순 선택 정렬은 가장 작은 요소부터 선택해 알맞은 위치로 옮겨서 순서대로 정렬하는 알고리즘이다. 오름차순을 예를 들어 설명하자면 '정렬되지 않은 열에서 가장 작은 값을 찾아 정렬되지 않은 열에 첫 번째 요소와 교환'하는 것이다. 시간 복잡도는 O(n^2)이다. // 기존 배열 // 정렬된 수 : 없읍 // 정렬되지 않은 수: 전부 [6,4,8,3,1,9,7] // 가장 작은 수 1을 첫 번째 요소 6과 변경한다. // 정렬된 수 : 1 // 정렬되지 않은 수: 4,8,3,6,9,7 [1,4,8,3,6,9,7] // 정렬된 수 1을 제외한 수 중 가장 작은 수 3을 4와 변경한다. // 정렬된 수 : 1,3 // 정렬되지 않은 수: 8,4,6,9,7 [1,3,8,4,6,9,7] stati..

버블 정렬'버블 정렬'이라는 말은 액체 안의 공기 방울이 보글보글 위로 올라오는 모습에서 착안한 것이다. 이 알고리즘은 서로 인접한 두 원소를 비교하여 순서가 맞지 않으면 서로 교환하는 방식으로 정렬을 수행한다. 배열 요소 전체를 훑는 일련의 과정(비교, 교환작업)을 패스(pass)라고 한다. 한 패스가 끝나면, 배열의 가장 큰 원소 혹은 가장 작은 원소가 맨 끝으로 이동한다. 버블 정렬의 시간 복잡도는 최악, 평균, 최선 모두 O(n^2)이다. 최악의 경우, 배열이 이미 정렬되어 있는 경우에도 교환 연산이 발생하므로 비효율적이다. 서로 이웃한 요소에 대해서만 교환하므로 이 정렬 알고리즘은 안정적이라고 할 수 있다. 기본적인 버블 정렬// a[idx1] 와 a[idx2]의 값을 바꾼다. static vo..

정렬이란? 정렬 알고리즘의 안정성 정렬 알고리즘은 안정된(stable) 알고리즘과 그렇지 않은 알고리즘으로 나눌 수 있다. 안정된 정렬이란 같은 값을 가진 요소의 순서가 정렬 전후에도 유지되는 것을 말한다. 안정되지 않은 알고리즘은 같은 점수인 경우 반드시 학번 순서대로 정렬되지는 않는다. // 정렬 전 { 0 = 13, 1 = 9, 2 = 6, 3 = 4, 4 = 6, 5 = 12 } // value를 오름차순으로 정렬 // 2,4 의 순서가 유지된다 { 3 = 4, 2 = 6, 4 = 6, 1 = 9, 5 = 12, 0 = 13 } 내부 정렬과 외부 정렬 정렬할 모든 데이터를 하나의 배열에 저장할 수 있는 경우에 내부 정렬을 사용하고 정렬할 데이터가 너무 많아서 하나의 배열에 저장할 수 없는 경우에 ..

예제 재귀 알고리즘 static void recur(int n) { if (n > 0) { recur(n - 1); System.out.println(n); recur(n - 2); } } 꼬리 재귀의 제거 메서드의 꼬리에서 재귀 호출하는 메서드 recure(n-2)는 아래처럼 바꿀 수 있다. n의 값을 n-2로 업데이트하고 메서드의 시작지점으로 돌아간다 코드로 표현하자면 이렇게 할 수 있다. static void recur(int n) { while (n > 0) { recur(n - 1); System.out.println(n); n = n - 2; } } 재귀의 제거 앞에 재귀를 제거하기 위해서는 n의 값을 잠시 저장해야 할 필요가 있다. n을 출력하기 전에 recur(n-1)을 실행해야 하기 때문..

유클리드 호제법(Euclidean algorithm)은 최대공약수(Greatest Common Divisor, GCD)를 구하는 알고리즘 중 하나이다. 이 알고리즘은 고대 그리스의 수학자 유클리드(Euclid)에 의해 고안되었으며, 두 정수의 최대공약수를 효과적으로 찾는 데 사용된다. 최대공약수(Greatest Common Divisor, GCD)는 두 개 이상의 정수의 가장 큰 공약수를 나타내는 개념이다. 공약수는 주어진 두 수의 모두에 나누어 떨어지는 수를 말하며, 최대공약수는 이러한 공약수 중에서 가장 큰 수를 의미한다. 두 수 24와 36의 경우 공통된 약수는 1, 2, 3, 4, 6, 12이다. 이 중에서 가장 큰 수인 12가 두 수 24와 36의 최대공약수가 된다. 따라서 GCD(24, 36)..

조합(Combination) N개 중에서 R개를 선택하는 경우의 수 C(N, R) = N! / (N-R)! * R! 순열(Permutation) N개 중에서 R개를 순서대로 나열하는 경우의 수 P(N, R) = N! / (N-R)! = N * (N-1) * (N-2) *... * ( N-R + 1)

구간 합은 합 배열을 이용하여 시간 복잡도를 더 줄이기 위해사용하는 특수한 목적의 알고리즘이다. 구간 합 알고리즘을 활용하려면 합 배열을 구해야 한다. 합 배열을 미리 구해 놓으면 기존 배열의 일정 범위의 합을 구하는 시간 복잡도가 O(N)에서 O(1)로 감소한다. 1차원 배열의 합 배열 1차원 합 배열 S 정의 S [i] = A [0] + A [1] +... + A [i-1] + A [i] 합 배열 S를 만드는 공식 S [i] = S [i-1] + A [i] i-1에서 알 수 있듯 합 배열은 기존 배열보다 하나 크게 생성해서 1번 인덱스부터 값이 들어간다. i에서 j까지의 합을 구하는 공식 S [j] - S [i-1] 1에서 3까지의 구간합 S [3] - S [0] 5에서 5까지의 구간합 S [5] -..