STUDY/DSA (6) 썸네일형 리스트형 해싱(hashing) / 해시 테이블(Hash Table) 해시 테이블은 키와 해시함수, 그리고 버킷이라는 데이터를 저장하는 장소로 이루어짐. 키(key) - 고유한 값, 해싱함수의 인자값 해시 함수(hash function) - 키를 입력받은 후 키에 맞는 데이터가 저장 된 위치값을 반환(이 과정을 해싱이라고 함). 버킷(bucket) - 해시 함수를 통해 생성된 해시 값을 고유 주소(키)로 사용하며 키에 맞는 값(value)의 한 쌍으로 저장하는 장소. 해시 테이블은 데이터가 키-값의 한 쌍으로 이루어져있기 때문에 삽입, 삭제, 검색 등의 과정에서 모두 O(n)의 시간복잡도를 가짐. 키값이 순차적으로 생성되는 것은 아니므로 순서나 관계가 있는 배열에서 사용하는 것은 적합하지 않으며 해시충돌이 일어날 수 있음. 해시 충돌(hash collision) 해시 충돌.. 이분 탐색/이진 탐색(Binary Search) 이진 탐색 알고리즘은 정렬된 원소 리스트를 받아 리스트에 원하는 원소가 있을경우 그 원소의 위치를 반환, 없을경우 null을 반환함. 시간복잡도는 O(log n)으로 매우 빠른편. Java 구현 코드 static int binarySearch(int[] arr, int num) { Arrays.sort(arr); int l = 0, r = arr.length-1; while(l 기수 정렬(Radix sort) / 계수 정렬(Counting sort) 1. 기수 정렬(Radix sort) 낮은 자리수 부터 비교하여 정렬해간다는 것을 기본 개념으로 하는 정렬. 문자열이나 정수 정렬에는 사용가능하며 속도도 매우 빠르지만, 부동 소숫점 실수 같이 자릿수가 없는 경우 정렬할 수 없음. 시간 복잡도는 O(d * (n + b)) == O(dn)으로 매우 빠른편. Java 구현 코드 (1) 배열의 최대값을 찾는 함수(getMax)를 통해 배열의 최대값 찾음 static int getMax(int[] arr) { int max = arr[0]; // 배열에서의 최대 원소 찾아 반환 for (int i = 1; i < arr.length; i++) { if(max < arr[i]) { max = arr[i]; } } return max; } (2) count sort.. 힙 정렬(Heap sort) 1. 힙 정렬(Heap sort) 완전 이진 트리를 기본으로 하는 힙(Heap) 자료구조를 기본으로하는 정렬. 불안정 정렬(unstable sort)에 속하며 평균, 최선, 최악 시간 복잡도 모두 O(n log n)임. 가장 크거나 작은 값을 구할 때 유용 완전 이진 트리(complete binary tree)? 이진 트리의 한 종류로서 왼쪽 부터 차례대로 노드를 삽입하는 트리(왼쪽부터 채움, 왼쪽이 비어있는데 오른쪽이 채워져있을 수 없음) Java 구현 코드 static void heapSort(int[] arr) { int n = arr.length; for (int i = n/2-1; i >= 0; i--) { // 최초 heap 구성 heapify(arr, n, i); } for (int i = .. 퀵 정렬(Quick sort) / 병합(합병) 정렬 (Merge sort) 1. 퀵 정렬(Quick sort) 퀵 정렬 알고리즘은 분할과 재귀로 이뤄진다. 1. 배열을 분할한다. 2. 피벗의 왼쪽과 오른쪽에 있는 하위 배열을 각각 또다른 배열로 보고, 각 하위 배열을 분할하고 각 하위 배열에 있는 피벗의 왼쪽과 오른쪽에서 더 작아진 하위 배열을 얻는다. 분할 정복 방법을 통해 정렬. 배열 중 한 원소를 정한 뒤(pivot) 피벗 보다 작은 원소들, 피벗보다 큰 원소들로 나눔(분할 divide). 나눈 배열들에 대해 재귀적으로 함수 실행(피벗을 정하고 다시 그 배열에서 작은 배열로 나누고의 반복) 시간 복잡도는 최악의 경우 O(N²)이며 최선의 경우 O(NlogN)임. 다른 정렬 알고리즘에 비해 빠름. 불안정 정렬(unstable sort)이며 오히려 정렬이 되어있는 경우 더 오.. 거품 정렬(Bubble sort) / 선택 정렬(Selection sort) / 삽입 정렬(Insertion sort) 1. 거품정렬(Bubble sort) 인접한 두 원소를 비교해 조건에 따라 자리를 교환(swap)하여 정렬하는 방법. 안정 정렬(stable sort)이며 구현이 간단하고 소스 코드또한 직관적이므로 자주 사용되지만 시간 및 공간복잡도가 모두 O(n²)로 비효율적임. Java구현 코드(오름차순) 내림차순 정렬은 조건을 반대로 해주기만 하면 됩니다. static void bubblesort(int []arr) { System.out.println("정렬 전 : " + Arrays.toString(arr)); // 배열 원소를 담아둘 변수 int temp; for (int i = 0; i < arr.length; i++) { for (int j = 1; j < arr.length-i; j++) { // 앞의 .. 이전 1 다음
