5장 컴퓨터 과학/Data Structure & Algorithm27 [알고리즘] 퀵 정렬(Quick Sort) 퀵 정렬은 병합 정렬과 마찬가지로 분할과 정복 패러다임에 기반하고 있지만 모든 힘든 작업이 재귀 호출 앞에 행해지기 때문에 다소 정반대의 방법이다. 분할과 정복 분할과 정복 패러다임은 다음의 세 단계로 이루어진 일반적인 용어로 설명될 수 있다. 분할(Divide): 배열이 적어도 2개의 원소를 갖고 있다면 배열로부터 피봇(pivot)이라고 불리는 특정한 원소 x를 선택한다. 일반적으로 배열의 마지막 원소를 피봇 x로 선택한다. 배열로 부터 모든 원소를 삭제하여 이들을 세 개의 배열에 넣는다. 세 배열은 각각 x보다 작은 원소(L), x와 같은 원소(E), x보다 큰 원소(G)가 저장된다. 재귀(Recur): 재귀적으로 시퀀스 L과 G를 정렬한다. 정복(Conquer): 먼저 L의 원소, 다음 E의 원소,.. 2021. 6. 16. [알고리즘] 병합 정렬(Merge Sort) 병합 정렬은 재귀적으로 배열을 분할하여 정렬하고 다시 합병한다. 이를 분할과 정복 패러다임이라고 한다. 분할과 정복 분할과 정복 패러다임은 다음의 세 단계로 이루어진 일반적인 용어로 설명될 수 있다. 분할(Divide): 입력의 크기가 특정한 임계값보다 작다면 간단한 메소드를 사용하여 직접 문제를 풀고, 얻어진 답을 반환한다. 그렇지 않으면, 입력 데이터를 둘 이상의 분리된 부분 집합으로 분할한다. 재귀(Recur): 부분 집합에 연관된 부분 문제를 재귀적으로 푼다. 정복(Conquer): 부분 문제에 대한 답을 구해 본래 문제의 답으로 병합한다. C++ 구현 template void merge_sort(RandomIt first, RandomIt last) { if (first + 1 == last) .. 2021. 6. 16. [자료 구조] 이진 탐색 트리 (Binary Search Tree) 개념 이진 탐색 트리(Binary search tree)는 맵의 엔트리를 저장하기에 훌륭한 자료구조이다. 이진 탐색 트리는 트리의 일종으로 한 엔트리 (k, v)에 대해 다음과 같은 특성을 같는다. k보다 작거나 같은 값을 갖는 노드는 v의 왼쪽 서브 트리에 저장된다. k보다 크거나 같은 값을 갖는 노드는 v의 오른쪽 서브 트리에 저장된다. 이진 탐색 트리는 비어 있는 외부 노드를 어떻게 표현하더라도 순서화된 맵을 표현한다. 즉, 이진 탐색 트리는 부모-자식 간의 관계를 사용하여 그 키의 순서를 계층적으로 표현할 수 있다. 특히 이진 탐색 트리를 중위 순회(Inorder traversal)하면 맵의 키들을 오름차순으로 방문할 수 있다. 추상 데이터 타입(ADT) find(k): 근(root) 노드에서 탐.. 2021. 6. 15. [자료구조] 정렬된 맵 (Ordered Map) 개념 정렬된 맵(Ordered Map)은 맵의 엔트리들을 전체 순서(total order)에 따라 정렬하고, 정렬된 순서에 따라 키와 값을 검색한다. 맵의 엔트리들이 정렬되어 있으면, 맵의 ADT의 추가적인 함수들을 효율적으로 구현할 수 있다. 추상 데이터 타입(ADT) firstEntry(): 가장 작은 키값을 가진 엔트리의 iterator을 반환한다. 만약 맵이 비었으면 end를 반환한다. lastEntry(): 가장 큰 키값을 가진 엔트리의 iterator의 반환한다. 만약 맵이 비었으면 end를 반환한다. ceilingEntry(k): k보다 크거나 같은 값을 가지는 키 중 최소값의 iterator을 반환한다. 만약 그러한 값이 없다면, end를 반환한다. floorEntry(k): k보다 작거나.. 2021. 6. 15. [자료구조] 해시 테이블 (Hash Table) 개념 맵을 구현하는 가장 효율적인 방법 중 하나는 해시 테이블을 사용하는 것이다.해시 테이블은 맵 연산을 평균 O(1) 시간에 실행할 수 있다. 해시 테이블은 버켓(bucket) 배열과 해시 함수로 이루어져 있다. 버켓(Bucket) 배열 해시 테이블을 위한 버켓 배열은 크기가 N인 배열 A이다. 여기서 A의 각 셀을 "버켓"으로 생각하고(즉, 키-원소 쌍들을 저장하는 컨테이너) 정수 N은 배열의 용량(capacity)이다. 만약 키들이 [0, N-1] 범위에 잘 분포된 정수라면, 버켓 배열만으로 충분하다. 키 k를 갖는 원소 e는 단순히 버켓 A[k]에 삽입된다. 만약 키가 [0, N-1] 범위에 있는 유일한 정수라면, 각 버켓은 최대 하나의 엔트리를 저장한다. 따라서 버켓 배열의 검색, 삽입, 그리고.. 2021. 6. 14. 이전 1 2 3 4 5 6 다음 반응형
