분류 전체보기

해시 테이블 해시 테이블은 원소의 값에 의해 결정되는 자료구조이다. 즉, 저장된 자료와의 비교를 통해 자리를 찾지 않고 단 한번의 계산으로 자리를 찾는다. 해시 함수 임의의 원소를 해시 테이블에 저장하려면 먼저 해당 원소의 해시값을 계산한다. 해시값은 해시 함수에 의해 계산된다. 해시 함수는 키값을 입력으로 받아 해시 테이블 상의 주소를 리턴하며 다음의 두 가지 성질을 가지도록 만들어야 한다. 입력 원소가 해시 테이블 전체에 고루 저장되어야 한다. 계산이 간단해야 한다. 1) 나누기 방법 나누기 방법은 원소를 해쉬 테이블의 크기로 나누어 나머지의 값을 테이블의 주소로 사용하여 저장하는 방법이다. 위의 예제는 해쉬 테이블의 크기가 13 일때 해쉬함수에 25, 13, 16, 5 ,7 의 입력값이 주어진 경우..

개요 K-D 트리 (K-Dimensional Tree라고도 함)는 각 노드의 데이터가 공간의 K 차원 포인트인 이진 검색 트리다. 즉, K 차원 공간의 점을 구성하기위한 공간 분할 구조이다. K-D 트리의 비 잎 노드(non-leaf node)는 공간을 두 부분으로 나눈다. 루트는 x- 정렬 된 평면을 가질 것이고, 루트의 자식들은 모두 y- 정렬 된 평면을 가질 것이고, 루트의 손자들은 모두 x- 정렬 된 평면들을 가질 것이며, 루트의 증손자들은 모두 y- 정렬 된 평면들을 가질 것이다. 그래서 이해가능한 적당한 이미지를 찾기 힘들었다. 보통은 위의 2차원의 kdtree 이미지들이 많이 보이지만 이를 일반 트리처럼 표현하면 아래처럼 된다. 아래 좌표랑 위의 그래프랑 비교해보면 쉬울듯하다. 삽입 다른 검..

개요 B-Tree는 데이터베이스나 파일 시스템에서 주로 사용되는 자료구조이다. 디스크 액세스하는 수를 줄이기 위해 나온 자료구조이다. 대부분의 트리연산들은 O(h) (h는 트리의 높이)인데 B-트리는 노드에 가능한 최대로 값을 넣어서 높이의 수를 줄인다. 특성 루트를 제외한 모든 노드는 적어도 k-1개의 키를 포함해야한다. 최대로 2t-1의 키를 가질 수 있다. 각 노드는 일련의 키와 여러 개의 자식 (자식 노드)을 가질 수 있다. 여기서 자식의 수는 0 또는 해당 키의 총 수에 1을 더한 값이 될 수 있다. 노드 [x]를 생각해보자. node [x]가 잎 노드 인 경우는 자식을 가지지 다 이것이 내부 노드인 경우 전체 자식 수는 n [x] + 1이다. 여기서 n [x]는 해당 키의 총 수이다. 제약 조..

개요 일반 이진 탐색 트리의 경우 균형이 맞지 않을 수 있다. 이를 해결하기 위한 알고리즘이 레드 블랙 트리이다. 특징 이진 탐색 트리의 특징에 더해서 레드 블랙 트리만의 특징들이 있다. 노드는 레드 혹은 블랙 중의 하나이다. 루트 노드는 블랙이다. 모든 널 포인터는 블랙이다. 레드 노드의 자식노드 양쪽은 언제나 모두 블랙이다. (즉, 레드 노드는 연달아 나타날 수 없으며, 블랙 노드만이 레드 노드의 부모 노드가 될 수 있다) 어떤 노드로부터 시작되어 리프 노드에 도달하는 모든 경로에는 리프 노드를 제외하면 모두 같은 개수의 블랙 노드가 있다. 삽입 이진 탐색 트리와 같이 삽입 연산을 진행하고, 색을 빨간색으로 지정한다. 이후 레드 블랙 트리의 특징을 유지하기 위해서 회전 연산을 해야하는 경우들이 있다...

개요 이진 트리는 비선형 자료 구조에 속하며 부모 노드에 붙는 자식 노드가 최대 2인 구조이다. 각 노드마다 값이 존재하고 한 노드의 왼쪽 서브트리에는 자신보다 작은 값들만 위치하며, 한 노드의 오른쪽 서브트리에는 자신보다 큰 값들만 위치한다는 특징이 있다. 삽입 이진 트리에서 삽입 연산은 현재 노드의 값과 새로 들어올 노드의 값을 비교한다. 현재가 더 크면 새로 들어올 노드는 현재 노드의 왼쪽 서브 트리에 놓게 된다. 이때 현재 노드의 왼쪽 자식 값이 null이면 새로 들어올 노드를 현재 노드의 왼쪽 자식에 삽입하고 null이 아니면 왼쪽 자식 노드에서 위의 연산을 반복하여 자리를 찾아간다. 반대로 현재가 작은 경우에는 오른쪽 서브 트리에 놓게 되며 위와 비슷한 과정을 거치며 자리를 찾아서 삽입해준다...

기수 정렬 기수 정렬은 배열 안의 데이터가 모두 n자릿수 이하의 자연수인 경우 사용 가능한 정렬이다. 일의 자릿수로 크기 비교후 정렬하고 다음은 십의 자리, 백의 자리,...해서 n자릿수까지 크기를 비교하는 독특한 정렬이다. 시간 복잡도는 O(dn)으로 빠른 편이다. 다만 테이블이 따로 필요하다는 단점이 있다. 기수 정렬이 어떤 순서로 동작하는지는 아래의 영상에 나와있다. https://youtu.be/nu4gDuFabIM import java.io.*; import java.util.*; class Radix { static void countSort(int arr[], int n, int exp) { int output[] = new int[n]; int i; int count[] = new int[..

힙 정렬은 자료구조의 최대 힙 트리나 최소 힙 트리를 구성해 정렬을 하는 방법이다. 각각의 차이는 내림차순이냐 오름차순이냐에 있다. 트리 구조를 이용해서 작성할 필요는 없고 간단하게 1차원 배열로도 충분히 표현 가능하다. 정렬해야 할 값을 배열에 저장하고 힙 삽입을 통해 차례대로 삽입한다. 이 과정이 끝나면 힙이 구성되는데 배열에서 최소값부터 삭제하면서 정렬한다. 위의 그림은 최대 힙 정렬을 하는 과정을 보여준다. 부모노드와 자식노드의 크기 비교를 해서 오름차순, 내림차순에 맞게 삽입을 하면서 힙을 구성한다. 다음에는 부모노드를 제거하고 그 자리에 최하위 자식 노드를 삽입한다. 다시 루트 노드의 자식 노드와 크기 비교를 하며 힙을 재구성한다. 이 과정을 반복하면 힙 정렬이 끝난다. 힙 정렬의 시간 복잡도..

퀵정렬은 병합 정렬처럼 분할 정복 알고리즘에 속하지만 병합 정렬과는 달리 불안정 정렬이다. 배열에 있는 값중 아무거나 하나를 pivot으로 정한다. 이를 값을 기준으로 pivot보다 작은 값은 왼쪽으로 큰 값은 오른쪽으로 정렬한다.(오름차순 정렬) 이렇게 pivot을 기준으로 왼쪽과 오른쪽으로 분할된 배열로 위의 과정을 반복한다. 퀵 정렬의 시간 복잡도는 O(nlogn)으로 병합 정렬과 동일하다. import java.util.Random; public class Quick { public static void quickSort(int[] a,int p,int r) { int q; if(p

Merge Sort 번역하기에 따라 병합 정렬 혹은 합병 정렬이라고 불린다. 분할 정복 알고리즘의 하나로 배열을 잘게 쪼개서 정렬을 하고 이를 합치는 방식이다. 말로 설명하기보다 그림으로 이해하는 것이 더 편하다. 아래와 같은 7size의 배열이 있다고 가정하자. 이를 4size의 배열과 3size의 배열로 나눈다. 다시 4size배열을 2size의 배열 두개로 나누고,... size가 하나가 될때까지 반복한다. 이후 각각을 비교해서 합치면서 정렬된 7size의 배열로 만들어준다. Merge Sort의 시간 복잡도는 O(nlogn)가 된다. public class merge { public static void mergeSort(int[] a,int p,int r) { int q = (int)Math.f..

삽입 정렬을 설명할때 보통 카드 게임에서 카드를 정렬하는 방식과 같다고 말한다. 0번 인덱스와 1번 인덱스를 비교하여 정렬한다. 이후 0,1,2를 비교해서 자리를 찾는다. 그 다음은 3번 인덱스가 들어갈 자리를 찾고 이런 식으로 끝까지 비교한다. 정렬된 배열에서 지정한 자리에 자료를 삽입하여 정렬하므로 삽입 정렬이라고 부른다. 단 초기 Key값을 0번 인덱스의 값이 아닌 1번 인덱스의 값으로 지정한다. 삽입 정렬의 시간 복잡도 또한 O(n2)로 버블,선택 정렬과 동일하다. 이 과정을 자바 코드로 표현하면 아래와 같다. public class insert { public static void insertSort(int[] a){ int N = a.length; int key; int i,j; for (i ..