EI_HJ

1. 순열(Permutation) 서로 다른 n개중에 r개를 선택하여 정렬하는 경우의 수 정렬은 r개를 택하여 일렬로 배열하는 경우를 말한다. [1, 2, 3]과 [3, 2, 1]은 다른 것. static boolean[] visited; static int[] result; public static void main(String[] args) { int[] arr = {1, 2, 3}; int r = 2; visited = new boolean[arr.length]; result = new int[r]; permutation(arr, 0, r); } public static void permutation(int[] origin, int depth, int r) { if (depth == r) { for..

Disjoint Set? 디스조인트 셋은 서로 중복되지 않는 부분 집합들로 나눠진 원소들에 대한 정보를 저장하고 조작하는 자료 구조이다. Distjoint Set - 서로소 집합 Union-Find? Disjoint Set을 표현할 수 있는 알고리즘 집합을 구현할 때 벡터, 배열, 리스트 등을 사용할 수 있으며, 주로 트리구조와, Hash구조(대량)을 사용하여 구현한다. Union-Find 연산 1. Make-Set(x) - 집합들을 초기화하는 원소로, 집합에는 x만 있을 수 있게, 즉 유일한 원소로 하는 집합(들)을 만든다. 2. union(x, y) - 집합들을 합치는 용도로, x와 y가 포함된 두 집합을 합치는 연산 3. find(x) - 루트, 최상의 부모노드(=루트, 같은 말) 찾기, x가 어떤..

병합 정렬(Merge sort) 알고리즘의 개념 병합 정렬(Merge sort)은 배열을 앞부분과 뒷부분을 나누어 각각 정렬한 다음 병합하는 작업을 반복하여 정렬을 수행하는 알고리즘이다 일반적인 방법으로 구현했을 때 안정 정렬에 속하며, 분할 정복 알고리즘의 하나이다. 병합 정렬(Merge sort) 알고리즘의 세부 과정 정렬되지 않은 배열을 절반으로 잘라 비슷한 크기의 두 부분 배열로 나눈다. 나뉜 배열들을 다시 재귀적으로 병합 정렬을 이용해 정렬한다. 두 부분 배열들을 다시 하나의 정렬된 배열로 합병한다. 병합 정렬(Merge sort) 예제 배열의 요소가 3, 4, 2, 1, 6, 8, 9, 5 순으로 저장돼있고 오름차순을 기준으로 정렬할 때 코드를 확인해보자 [Java 코드] 1 2 3 4 5 6..

퀵 정렬(Quick sort) 알고리즘의 개념 퀵 정렬(Quick sort)은 일반적으로 사용되고 있는 아주 빠른 정렬 알고리즘 '찰스 앤터니 리처드 호어(C. A. R. Hoare)가 개발한 정렬 알고리즘 불안정 정렬에 속하며, 원소들과의 비교만으로 정렬을 수행 분할 정복 알고리즘 중 하나 퀵 정렬(Quick sort) 알고리즘 세부 과정 먼저 하나의 요소를 선택한다. 이렇게 고른 요소를 피벗(pivot)이라고 한다. 피벗을 기준으로 피벗보다 작은 값을 피벗기준 왼쪽으로, 큰 값을 피벗기준 오른쪽으로 정렬한다. 피벗을 제외한 왼쪽 값들과 오른쪽 값들을 다시 정렬한다. 위처럼 나눈 값들의 길이가 1이 될 때까지 반복한다. 퀵 정렬(Quick sort) 알고리즘 예제 배열의 요소가 5, 7, 1, 4, 6..

셸 정렬(Shell sort) 알고리즘의 개념 셸 정렬(Shell sort)은 삽입 정렬의 장점은 살리고 단점은 보안하여 좀 더 빠르게 정렬하는 알고리즘으로 D. L. Shell이 고안했다. 먼저 정렬할 배열의 요소를 그룹으로 나눠 각 그룹 별로 삽입 정렬을 수행하고, 그 그룹을 합치면서 정렬을 반복하여 요소의 이동 횟수를 줄이는 방법이다. 셸 정렬(Shell sort) 알고리즘 세부 과정 정렬할 배열을 일정한 기준(간격)에 따라 분류 각 부분 배열을 삽입 정렬로 정렬 다시 전체 배열을 더 적은 개수의 부분 배열로 분류 위의 과정(2,3)을 부분 배열의 길이가 1이 될 때까지 반복 셸 정렬(Shell sort) 알고리즘 예제 배열의 요소가 8, 1, 4, 2, 7, 6, 3, 5 순으로 저장돼있고 오름차..

삽입 정렬(Insertion sort) 알고리즘의 개념 (오름 차순 기준) 선택한 요소를 그보다 더 앞쪽의 알맞은 위치에 삽입하는 작업을 반복하여 정렬하는 알고리즘이다. 선택 정렬과 비슷하게 보이지만 삽입 정렬은 해당 값을 가져와 알맞은 위치에 옮긴다는 점이 다르다. 삽입 정렬(Insertion sort) 예제 배열에 6, 4, 1, 7, 3 순으로 값이 들어가 있고 오름차순으로 정렬할 때의 삽입 정렬 예를 확인해보자 위와 같이 정렬을 하지 않은 부분의 첫 번째 요소를 가져와 정렬을 마친 부분의 적절한 위치를 찾아 옮기는 알고리즘이 삽입 알고리즘이다. [Java 코드] 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 public class Insert..

선택 정렬(Selection sort) 알고리즘의 개념 (오름 차순일 경우)가장 작은 요소부터 선택해 알맞은 위치로 옮겨서 순서대로 정렬하는 알고리즘이다. 제자리 정렬(in-place sorting) 알고리즘의 하나 정렬을 마친 부분과 아직 정렬하지 않은 부분이 나뉘어 있으며, 아직 정렬되지 않는 부분에서 최솟값을 찾아 정렬의 마친 부분의 끝 부분에 값을 넣어준다. 선택 정렬(Selection sort) 예제 배열에 3, 2, 6, 4, 1 순으로 값이 들어가 있고 오름차순으로 정렬할 대의 선택 정렬 예를 확인해보자 위의 과정과 같이 배열 중 최솟값을 찾아 회색 부분(정렬하지 않은 부분의 첫 번째 요소)과 살구색 부분(정렬하지 않은 부분의 최솟값)을 교환해주고 만약 둘이 같은 값을 가진다면 다음 단계로 ..

버블 정렬(Bubble sort) 알고리즘의 개념 버블 정렬은 이웃한 두 요소의 대소 관계를 비교하여 교환을 반복하는 알고리즘이다. 선택 정렬과 기본 개념이 비슷하다. 버블 정렬(Bubble sort) 예제 배열에 1, 5, 4, 10, 8, 19, 3 순으로 값이 들어가 있고 오름차순으로 정렬할 때의 버블 정렬 예를 확인해보자 버블 정렬은 이웃한 두 요소 간 대소 관계를 파악하여 정렬하는 행위를 배열 전체에 한번 해주게 된다. 다음 두 요소 간 대소 관계 파악은 이전에 했던 대소 관계 비교 횟수보다 -1 만큼만 해줘도 된다는 특징이 있다. 위와 같이 오른쪽 끝에서 왼쪽 끝까지 이웃한 숫자끼리 대소 비교를 하며 정렬했다. 중요한 포인트는 이렇게 1회전이 끝난 버블 정렬의 맨 왼쪽 요소는 배열 중 최솟값으..

Floyd-Warshall(플로이드와샬 알고리즘)이란? - 그래프에서 모든 정점 사이의 최단거리를 구하는 알고리즘. - 음수 가중치에 대한 처리가 어려운 다익스트라 알고리즘에 비해 플로이드 와샬 알고리즘은 사이클이 없는 경우 음수 가중치 처리가 가능 - for문(반복문)을 vertex(정점)만큼 3번 돌기 때문에 O(n3)의 시간 복잡도를 가진다. Floyd-Warshall process - 2차원 배열의 크기만큼 배열을 선언해준다. (각 정점에서 모든 정점을 가는 최소거리를 표현해줄 것이다.) - 연결돼있는 부분을 표기해준다. - 시작 정점에서 목표 정점까지 바로 가는 거리보다 또 다른 정점을 거쳐 지나가는 거리가 짧으면 업데이트를 해준다. - 플로이드 워샬 알고리즘에서는 1부터 시작해서 n까지 순차적..

heap 이란? 힙(heap)은 최댓값 및 최솟값을 찾아내는 연산을 빠르게 하기 위해 고안된 완전이진트리(complete binary tree)를 기본으로 한 자료구조(tree-based structure)이다. 우선순위 큐를 구현할 때 주로 사용한다. - 부모보다 작은 값을 가진 힙을 최대힙이라 부른다. - 부모보다 큰 값을 가진 힙을 최소힙이라 부른다. - 항상 부모에 어떤 값이 오느냐에 따라 최소/최대가 달라진다. -키값의 대소관계는 오로지 부모 노드와 자식 노드 간에만 성립하며, 특히 형제 사이에는 대소 관계가 정해지지 않는다. 힙은 다른 이진트리와 마찬 가지로 부모는 node/2의 인덱스에 있으며 자식은 node * 2 | node * 2 +1에 위치해있다. 값 입력은 항상 맨 뒤에 되며 입력된..