해싱이란❓ - 해싱함수 (Hashing Function)를 이용하여 레코드키에 대한 해시 테이블 (Hash Table)내의 홈주소(Home Address)를 계산하여 주어진 레코드에 접근하는 방식입니다. - 직접접근 파일을 구성할 때 사용됩니다. - 속도는 가장 빠르지만, 충돌 현상 시 오버플로 해결의 부담이 가중되며, 많은 기억 공간을 요구합니다. 해시테이블(Hash Table)❓ 해시테이블은 레코드를 한 개 이상 보관할 수 있는 버킷(Bucket)들로 구성된 기억공간으로, 보조기억장치에 구성할 수도 있고 주기억장치에 구성할 수도 있다. - 버킷(Bucket) 하나의 주소를 갖는 파일의 한 구역을 의미하며, 버킷의 크기는 같은 주소에 포함될 수 있는 레코드의 수를 의미한다. - 슬롯(Slot) 한 개의..

- 완전 이진트리를 이용하여 정렬하는 방법으로, 우선순위 큐를 위하여 만들어진 자료구조입니다. - 정렬한 입력 자료들로 힙을 구성하고, 가장 큰 키값을 갖는 루트 노드를 제거하는 과정을 반복하여 정렬하는 기법입니다. - 최대값, 최소값을 쉽게 추출할 수 있는 자료구조입니다. - 입력 자료의 레코드를 완전 이진트리로 구성합니다. 그렇다면 힙(Heap)자료구조란 무엇이며, 완전 이진트리는 또 무엇일까요? 완전이진트리 (Complete Binary Tree)자료구조란? 완전 이진 트리란 각 노드가 최대 2개의 자식 노드를 갖는 트리 형태의 자료구조로서 마지막 레벨을 제외한 모든 노드는 완전히 채워져 있어야 합니다. 또한, 최하단 레벨의 노드는 좌측만 노드가 채워져 있거나 좌측과 우측 모두 채워져 있어야 하며,..

많은 자료 이동을 없애고, 하나의 파일을 부분적으로 나누어가면서 정렬하는 방법으로 피봇(Pivot)을 기준으로 작은 값은 왼쪽에, 큰 값은 오른쪽에 모이도록 서로 교환시키는 부분 교환 정렬법이다. 분할 정복 알고리즘의 하나로, 평균적으로 매우 빠른 수행 속도를 가진다. -> 합병정렬과는 달리 퀵 정렬은 리스트를 비균등하게 분할한다. 퀵 정렬 동작 과정 설명 피봇(Pivot)은 편의를 위해 제일 첫 번째 원소로 선택하겠습니다. 배열에 {5, 3, 8, 4, 9, 1, 6, 2, 7}이 저장되어있다고 가정합니다. 우리는 피봇 5를 기준으로 작은 값은 왼쪽, 큰 값은 오른쪽에 오도록 분할을 해야합니다. 그럼 어떤 식으로 로직을 구현해야할까요? 우선, 위와같이 변수들을 할당합니다. 1회 수행이 끝나면, 5보다 ..

두 개의 키들을 한 쌍으로 하여 각 쌍에 대해 순서를 정합니다. 이후 순서대로 정렬된 각 쌍의 키들을 합병하여 하나의 정렬된 서브리스트로 만듭니다. 정리하자면, 문제를 작은 2개의 문제로 분리하고, 각각을 해결한 다음 결과를 모아서 원래의 문제를 해결하는 분할 정복의 방법을 사용하는 것입니다. 그 동작 과정은 아래와 같습니다. 1. 리스트의 길이가 0 또는 1이면 이미 정렬된 것으로 봅니다. 2. 그렇지 않은 경우에는 리스트를 절반으로 잘라 비슷한 크기의 두 리스트로 나눕니다. 3. 나누어진 각 부분 리스트를 재귀적으로 합병 정렬을 이용해 정렬합니다. 4. 마지막 단계에서 최종적으로 남은 2개의 부분리스트를 하나의 정렬 리스트로 합병합니다. 결과적으로, - 분할 (Divide) : 입력 배열을 같은 크기..

N개의 원소 중에서 최소값(또는 최대값)을 찾아 1st 위치에 놓고, 나머지 (n-1)개의 원소 중에서 최소값(또는 최대값)을 찾아 2nd 위치에 놓는 방법을 반복하여 정렬하는 알고리즘이다. 1회전을 수행하고 나면 최소값(또는 최대값)이 맨 앞으로 오게 되므로 그 다음 수행부터는 2번째 위치, 3번째 위치 순으로 나머지 자료에 대해 탐색한 후 채워나갑니다. 선택 정렬 알고리즘의 동작 예시 (오름차순 기준) - 1회전 (1번째 인덱스 결정) : 1번째 원소를 2 ~ N 번째 인덱스의 원소까지 탐색하며 선택한 최소값과 SWAP한다. - 2회전 (2번째 인덱스 결정) : 2번째 원소를 3 ~ N 번째 인덱스의 원소까지 탐색하며 선택한 최소값과 SWAP한다. - 3회전 (3번째 인덱스 결정) : 3번째 원소를 ..

서로 인접한 두 원소를 비교하여 정렬하는 알고리즘입니다. 인접한 두 원소를 비교하여 크기가 순서대로 되어 있지 않으면 서로 교환합니다! 버블 정렬 알고리즘 동작 과정 (오름차순을 기준으로 하겠습니다.) - [ i, i+1 ] 번째 인덱스를 비교하여 교환하면서 자료를 정렬합니다. - 한 번의 수행이 끝나면 가장 큰 수가 맨 뒤로 가게되므로, 2번째 수행에서는 마지막 원소를 제외한 범위만큼 다시 같은 과정을 반복합니다. - 당연하게도, 정렬을 1회전 수행할 때마다 정렬에서 제외되는 데이터가 하나씩 늘어납니다. 버블 정렬 알고리즘 예시 남은 4회전과 5회전도 같은 방법으로 수행을 하시면 됩니다. Java로 구현한 버블정렬 알고리즘 import java.io.*; import java.util.*; public..