반응형 C11 [자료구조] 보간 탐색(Interpolation Search 보간 탐색은 이진탐색과 유사하다. 이진 탐색은 정렬된 배열의 중앙에 위치한 데이터를 기준으로 탐색을 시작한다. 보간탐색은 이런한 방식에서 발생할 수 있는 비효율을 줄이기 위해 등장하였다. 탐색 기준 선정방식 중복된 키가 없이 정렬된 데이터 들에 대한 탐색이라는점을 고려하여 탐색할 대상이 대략적으로 어디에 위치해 있는지를 파악하는 식이 존재한다. 이는 데이터의 값과 그 데이터가 저장된 위치의 인덱스값이 비례하다는 생각을 근거를 기반에 두고있다. "x" 라는 데이터를 찾는 경우, 해당 데이터의 인덱스 값 "s"에 대한 식은 다음과 같다. low : 탐색 대상의 시작 인덱스 high : 탐색 대상의 마지막 인덱스 #include int ISearch(int ar[], int first, int last, in.. 2024. 1. 16. [자료구조] 이진 탐색(Binary Search) 이진 탐색이란? - 테이터가 정렬되어있는 배열에서 특정 값을 찾을때 중간에 있는 임의의 값을 선택하여 특정값X와 비교한다. X가 중간값보다 작으면 중간값을 기준으로 좌측의 데이터들을 대상으로, 중간값보다 크면 우측의 데이터들을 대상으로 동일한 방법으로 다시 중간값을 임의로 선택해서 비교하는 과정을 X값을 찾을때까지 반복한다. - 이진탐색에 사용되는 배열은 정렬이 되어있어야 한다. - 구역을 나누었을때 first(첫번째 인덱스)가 last(마지막 인덱스)보다 커지면 해당 배열에 특정값이 없다고 판단하여 탈출하는 부분을 구현해야한다. - 시간 복잡도 : O(logn) int BSearchRecursive(int arr[], int target, int low, int high) { if (low > high.. 2024. 1. 16. [자료구조] 기수정렬(Radix Sort) 기수정렬이란 - 데이터들의 값을 비교연산을 하지 않는 알고리즘이다. - 데이터를 구성하는 기본요소, 즉 기수를 이용하여 정렬을 진행하는 방식이다. - 낮은 자리부터 정렬하는 LSD, 높은자리부터 정렬하는 MSD가 있다. - MSD는 추가적인 연산을 필요로 하기때문에 LSD를 선호한다. 단점 - 자릿수가 없는 것은 정렬할 수 없다.(부동 소숫점) - 중간 결과를 저장할 bucket 공간이 필요하다. - 시간복잡도 : O(n) void countSort(int arr[], int n, int exp) { int buffer[n]; int i, count[10] = {0}; // exp의 자릿수에 해당하는 count 증가 for (i = 0; i < n; i++){ count[(arr[i] / exp) % 1.. 2024. 1. 15. [자료구조] 퀵 정렬(Quick Sort) 퀵 정렬이란 - 분할 정복 방법을 통해 주어진 배열을 정렬한다.(분할, 정복, 결합) 과정 1. 배열 가운데서 하나의 원소를 골라 피벗(pivot)이라고 정한다. 2. 피벗 앞에는 피벗보다 우선순위가 높은 원소들이 오고, 피벗 뒤에는 우선순위가 낮은 원소들이 오도록 분할 한다. 3. 이렇게 두구역으로 나눈뒤 해당 구역에서의 피벗을 정하여 이과정을 재귀적으로 반복한다. - 이미 정렬되어있는 리스트에서 가장 최악의 시간복잡도를 갖게된다. O(n^2) - 평균적인 시간복잡도 : O(nlog2n) # include # define MAX_SIZE 9 # define SWAP(x, y, temp) ( (temp)=(x), (x)=(y), (y)=(temp) ) // 1. 피벗을 기준으로 2개의 부분 리스트로 나눈.. 2024. 1. 15. 이전 1 2 3 다음 반응형