본문 바로가기

플밍 is 뭔들/자료구조

08-4 해싱 ※ 해싱(Hashing) - 해싱은 키값을 비교하여 검색하는 것이 아니라 산술적 연산을 이용하여 키가 있는 위치를 계산하여 바로 찾아가는 계산 방법이다. - 키값을 원소의 위치로 변환하는 함수를 해싱 함수(Hashing Function)라 한다. - 해싱 함수에 의해 계산된 주소의 위치에 항목을 저장한 표를 해시 테이블(Hash Table) 이라 한다. - 즉 해싱은 어떤 키값을 해시함수를 통해 그 키값이 저장될 해시 테이블의 위치를 구한다. 그리고 그 위치에 저장하거나 검색한다. - 해시 테이블을 버킷과 슬롯으로 구성한다. - 해싱 함수에 의해서 계산된 주소는 버킷 주소가 된다. - 버킷에 여러개의 슬롯을 만들어 값이 비슷한 여러개의 키값을 저장할 수 있다. ※ 해싱 구조 용어 동거자 : 모든 키값이 .. 더보기
08-3 이진 트리 검색 ※ 이진 트리 검색(Binary Tree Search) - 이진 트리 검색은 이진 탐색 트리를 이용하여 검색하는 방법이다. - 이진 트리는 루트 노드의 왼쪽에는 루트노드보다 작은값, 오른쪽에는 루트노드보다 큰 값으로 되어있기 때문에 중위 순회 방법으로 순회하면 오름차순으로 정렬된 자료를 구할 수 있다. - 이러한 성질을 이용하면 쉽게 검색이 되지만 원소 삽입, 삭제 연산에 대해 이진 트리를 유지해야 하기 때문에 추가 작업이 필요하다. * 중위순회를 통해 오름차순으로 정렬된 값을 통하여 키값을 검색하는것도 좋지만 루트노드 기준으로 큰값일땐 오른쪽, 작은값일땐 오른쪽 탐색을 하여 해당 key값을 찾을때까지 탐색해도 괜찮을듯 하다. 더보기
08-2 이진 검색 ※ 이진 검색(Binary Search) - 가운데에 있는 항목을 키값과 비교하여 키값이 더크면 오른쪽을 검색하고, 키값이 더 작으면 왼쪽 부분을 검색하는 방법이다. - 가운데 값을 기준으로 왼쪽과 오른쪽의 두 부분으로 나누어 검색하는데 이를 이분 검색 또는 보간 검색(Interpolation Search)라고도 한다. - 지속적으로 왼쪽과 오른쪽으로 분할해가며 검색 범위를 반으로 줄여가면서 검색한다. - 분할 정복 (divide and conquer)기법이라고도 한다. - 이진 검색 방법은 시간 복잡도가 다른 검색 방법에 비해 좋지만, 항상 배열의 상태를 정렬된 상태로 유지해야 하므로 삽입이나 삭제시 추가 작업이 필요할 수 있다. BinarySearch public class BinarySearch {.. 더보기
08-1 순차 검색 ※ 순차 검색(Sequential Search) - 일렬로 되어있는 자료를 처음부터 마지막까지 검색하는 방법 - 선형 검색(Linear Search)이라고도 한다. - 검색하는 양에 따라 효율이 달라진다. 자료의 양이 많아질수록 비효율 적이지만 알고리즘이 단순하여 구현이 쉽다. ※ 정렬되지 않은 순차 자료구조에서의 순차 검색 - 첫 번째 원소부터 시작하여 키값이 일치하는 원소를 찾는다. - 정렬이 되어있지 않기때문에 키값이 일치하는 원소를 찾을때 까지 검색한다. - 끝까지 검색했는데 키값이 없다면 검색 실패 ※ 정렬이 된 순차 자료구조에서의 순차 검색 - 첫 번째 원소부터 시작하여 키값이 일치하는 원소를 찾는다. - 단 정렬되어 있기 때문에 키값보다 작거나 같은 원소까지만 검색을 하고 그 이후는 하지 않.. 더보기
07-9 트리 정렬 ※ 트리 정렬(TreeSort) - 트리 정렬은 이진 탐색 트리를 이용하여 정렬하는 방법 - 정렬할 원소들을 이진 탐색 트리로 구성하고 중위 순회 방법을 사용하여 이진 탐색 트리의 원소들을 순회하여 꺼내온다. TreeSort public class TreeSort { Node root =null; int[] result = null; int idx=0; public void treeSort(int[] a){ result = new int[a.length]; for(int i=0; i data){ if(temp.left == null){ temp.left= newNode; return; }else{ temp = temp.left ; } }else{ if(temp.right == null){ temp.rig.. 더보기
07-8 힙 정렬 ※ 힙 정렬(Heap Sort) - 힙 자료구조를 이용해 정렬하는 방법으로 정렬하려는 자료를 힙으로 만든 후 최대 힙이라면 제일 큰 수 부터 뒤에서 정렬하고 최소 힙이면 가장 작은 수 부터 앞으로 정렬시킨다. - 힙정렬은 힙을 만들고 힙에서 원소를 삭제한 후에 최대힙, 최소힙의 조건에 맞게 힙을 재구성 해야한다. HeapSort public class HeapSort { int[] result =null; int resultIdx=0; int heapSize = 0; int[] maxHeap = null; public int makeHeap(int a[]){ int temp; int idx; // 최대 힙 만들기 if(maxHeap ==null){ maxHeap = new int[a.length+1]; .. 더보기
07-7 기수 정렬 ※ 기수정렬(Radix Sort) - 분배 방식의 정렬 방법 - 정렬할 원소의 키값에 해당하는 버킷(bucket)에 원소를 분배하였다가 버킷의 순서대로 원소를 꺼내는 방법을 반복 - 원소의 키를 표현하는 값의 기수(radix)만큼의 버킷이 필요하고, 키값의 자리수만큼 기수 정렬을 반복한다. - 10진수로 표현된 키값을 가진 원소들을 정렬할 때에는 0~9까지의 10개의 버킷을 이용 - 키값의 일의 자리에 대해 기수 정렬을 수행하고 그 다음 십의 자리에 대해 기수 정렬을 하고 그 다음 백의 자리에 대해 기수정렬을 하고.... 자리수에 맞게 반복한다. - 버킷은 원소들을 순서대로 꺼내어 다음 단계의 기수 정렬을 수행해야 하므로 큐를 사용하여 만든다. ※ 구현 Radix Sort public class Radi.. 더보기
07-6 병합 정렬 ※ 병합정렬(Merge Sort) - 분할, 정복, 결합의 순서로 이루어 지는 정렬 - 분할(divide) : 2개의 부분집합으로 분할 - 정복(conquer) : 부분집합의 원소들을 정렬한다. 부분집합의 크기가 충분히 작지 않으면 다시 분할한다. - 결합(combine) : 정렬된 부분집합들을 하나의 집합으로 통합한다. - 새로 병합하여 만든 부분집합을 저장할 공간이 추가로 필요하기 때문에 정렬할 원소 n개에 대하여 2*n개의 메모리 공간을 사용한다. ※ 분할 ※ 병합 ※정렬과정 ※ 구현 MergeSort public class MergeSort { int[] result =null; int[] a=null; public void sorting(int[] a, int start, int end){ if.. 더보기
07-5 셸 정렬 ※ 셸 정렬(Shell Sort) - 일정한 간격(interval)으로 떨어져 있는 자료들끼리 크기를 비교하여 교환 - 일정한 간격(interval)은 원소의 개수/2 를 하고 비교가 끝난 후에는 다시 간격(interval)/2를 해서 간격이 1이 될때 까지 수행한다. - 전체 원소에 대하여 삽입 정렬을 수행하는 것보다 부분집합으로 나누어 정렬하면 비교 연산과 교환 연산의 횟수를 줄일 수 있다. ※ 구현 Main public class Main { public static void main(String args[]){ int a[] = {69,10,30,2,16,8,31,22}; int size = a.length; ShellSort ss = new ShellSort(); System.out.printl.. 더보기
07-4 삽입 정렬 ※ 삽입정렬(Insert Sort) - 정렬되어 있는 부분집합에 정렬할 새로운 원소의 위치를 찾아 삽입하는 방법. - 앞부분은 Sorted/ 뒷부분은 Unsorted로 되어있다. - 즉 맨앞의 원소로 부터 시작하여 오른쪽원소와 비교하여 알맞은 위치에 정렬시켜 넣어주는것 이다. ※구현 Main public class Main { public static void main(String args[]){ int a[] = {69,10,30,2,16,8,31,22}; int size = a.length; InsertSort is = new InsertSort(); System.out.println("정렬할 원소 : "); for(int i=0; i0; j--){ if(this.a[j-1] > this.a[j]){.. 더보기
07-3 퀵 정렬 ※ 퀵 정렬(Quick Sort) - 기준값을 중심으로 왼쪽 부분집합과 오른쪽 부분집합으로 분할(divide) 한다. 왼쪽 부분집합에는 기준값보다 작은 원소들을 이동시키고, 오른쪽으로는 기준값보다 큰 원소들을 이동시킨다. 이때 사용하는 기준값을 피봇(pivot)이라 한다. 일반적으로 피봇은 전체 원소 중에서 가운데에 위치한 원소를 피봇으로 선택한다. - 퀵 정렬은 다음의 두가지 기본 작업을 반복 수행하여 완성한다. 분할(divide) : 정렬할 자료들을 기준값을 중심으로 2개의 부분집합으로 분할한다. 정복(conquer) : 부분집합의 원소들 중에서 기준값보다 작은 원소들은 왼쪽 부분집합으로, 기준값보다 큰 원소들은 오른쪽 부분집합으로 정렬한다. 부분집합의 크기가 1 이하로 충분히 작지 않으면 순환 호출.. 더보기
07-2 버블 정렬 ※ 버블 정렬(Bubble Sort) - 인접한 두개의 원소를 비교하여 자리를 교환하는 방식 ※ 구현 Main public class Main { public static void main(String[] args) { int a[] = {69,10,30,2,16,8,31,22}; BubbleSort bs = new BubbleSort(); System.out.println("\n정렬할 원소 : "); for(int i =0; i=0; i--){ for(int j=0; j a[j+1]){ swap(j,j+1); } } } printSortResult(); } private void swap(int idx1, int idx2){ int temp = a[idx1]; a[idx1] = a[idx2]; a[id.. 더보기

티스토리툴바