🌈 백엔드/자료구조 썸네일형 리스트형 자료구조_검색 ④ 보간검색 [1] 보간 검색 (1) 보간검색 개요 제어검색의 종류 데이터의 개수와 찾는 값의 성질에 따라 있음직한 위치를 처음 검색위치로 지정하는 방식 성능 : 이진검색 < 피보나치검색 더보기 자료구조_검색 ③ 피보나치 검색 [1] 피보나치 검색 (1) 피보나치 검색 개요 제어검색의 종류 검색에 사용하는 위치를 피보나치 수열을 이용하여 선정함 성능 : 이진검색 < 피보나치검색 더보기 자료구조_검색 ② 이진검색 [1] 이진검색 (1) 이진검색 개요 제어검색의 종류 이진검색 = 이분검색 자료들 중 중간에 위치한 항목을 키 값과 비교하여 다음 검색 위치를 결정하여 검색을 계속하는 방법 데이터의 반에 해당 위치를 찾아간다 성능 : 이진검색 < 피보나치검색 더보기 자료구조_검색 ① 순차검색 [1] 순차검색 (1) 순차검색 개요 일렬로 나열된 정렬되지 않은 자료를 처음부터 마지막까지 순서대로 검색하는 방법 검색기간이 길지만 정렬되어 있지 않아도됨 (2) 시간복잡도 O(N) 더보기 자료구조_정렬 ⑦기수 정렬 [1] 기수 정렬 (1) 기수정렬 개념 Radix 정렬 버킷 정렬 자릿수의 값을 기준으로 정렬 사용되는 데이터 진법에 따라 버킷의 갯수가 달라짐 10진수는 10+1 =11개 버킷 8진수는 8+1 = 9개 버킷 (2) 삽입정렬 과정 세자리 정수로 구성된 데이터가 있으면 먼저 100의 자리의 값을 기준으로 버킷을 이용하여 정렬하고 결과를 10의 자리값을 기준으로 정렬하고 1의 자리값을 기준으로 정렬하여 정렬을 완료한다 (3) 시간복잡도 O(n) 더보기 자료구조_정렬 ⑥ 병합 정렬 [1] 병합 정렬 (1) 병합정렬 개념 merge 정렬 두개의 그룹을 하나의 그룹으로 병합하여 그룹 내를 정렬하는 방식 외부정렬 수행능력은 좋으나 데이터 크기보다 2배의 기억공간이 필요하다 (2) 시간복잡도 O(nlog2n) 더보기 자료구조_정렬 ⑤힙 정렬 [1] 힙 정렬 (1) 힙 정렬 개념 heap 정렬 정렬을 위한 목적으로 만든 힙 트리를 이용한 정렬 (2) 시간복잡도 O(nlog2n) 더보기 자료구조_정렬 ④ 퀵 정렬 [1] 퀵 정렬 (1) 퀵 정렬 개념 quick 정렬 가장 빠른 정렬 방법 분할 정복 정렬 방식 데이터 리스트 중 중간에 위치한 값을 피벗이라한다 피벗은 알고리즘에 따라 첫 값, 마지막 값, 중위수 값을 선택할수 있다 피벗 기준으로 왼쪽에서는 피벗보다 큰 값을 , 오른쪽에서는 피벗보다 작은 값을 찾아 교환하는 작업을 반복하여 정렬한다 (2) 퀵 정렬 과정 (3) 시간복잡도 O(nlogn) 최악이면 O(N⌒2) 가 나올수 있다 더보기 이전 1 2 3 4 다음 목록 더보기
