5장 컴퓨터 과학/Data Structure & Algorithm27 [자료구조] 맵 (Map) 개념 맵(Map)은 원소를 저장하고 그것을 이용하여 빠르게 찾을 수 있도록 한다. 맵은 검색키를 이용하여 정보에 접근한다. 엔트리라 불리는 키-값 쌍(k, v)을 저장하며, 여기서 k는 키이고 v는 연관된 값이다. 각 키는 유일하고 키와 의 연관은 매핑을 정의한다. 추상 데이터 타입(ADT) size(): 맵에 저장된 원소의 개수를 반환한다. empty(): 맵이 비었으면 true를 그렇지 않으면 false를 반환한다. find(k): 키 k를 갖는 엔트리를 찾아 그것을 가리키는 iterator를 반환한다. 그러한 키가 없으면 iterator end를 반환한다. operator[k]: 키 k의 값에 대한 레퍼런스를 생성한다. 그러한 키가 없으면, 키 k를 갖는 새로운 엔트리를 생성한다. insert(pa.. 2021. 6. 14. [알고리즘] 힙 정렬(Heap Sort) 힙을 이용하여 힙 정렬을 할 경우 정렬 시간이 $n\log{n}$으로 크게 감소한다. C++ 구현 #include using namespace std; template void heap_sort(RandomIt first, RandomIt last) { make_heap(first, last); for (RandomIt it = last; it != first; --it) pop_heap(first, it); } algorithm 헤더 파일의 heap과 관련된 함수를 이용하였다. [first, last) 범위의 원소를 오름차순으로 힙 정렬하는 코드이다. 2021. 6. 11. [자료구조] 힙 (Heap) 개념 힙은 우선순위 큐를 효율적으로 구현하기 위한 자료구조로 이진 트리의 일종이다. 성질 힙-순서 특성(Heap-Order Property): 힙 T에서 루트를 제외한 모든 노드 v에 대하여, v에 저장된 키는 v의 부모에 저장된 키보다 크거나 같다.(단, 힙의 정의에 따라 부모 노드에 최대값이 저장될 수도 있다.) 완전(complete) 이진 트리 특성: 만약 레벨 0, 1, 2, ..., h-1들이 가질 수 있는 최대 수의 노드를 포함하고 (즉, 레벨 i는 2i 노드를 포함, 이때 0≤i≤h-1) 레벨 h-1에서 모든 내부 노드는 외부 노드들의 왼쪽에 위치한다면, 높이 h인 이진 트리 T는 완전하다. 힙의 높이(height): T의 높이를 h라 할 때 T의 마지막 노드는 레벨 h에 있으며 같은 레벨의.. 2021. 6. 11. [알고리즘] 선택 정렬(Selection Sort) 선택 정렬은 n개의 원소를 가진 배열에서 i 번째 단계에서 [i, n) 번째 원소 중에 최소값을 구해 i 번째 원소와 위치를 바꾼다. 특성 일반적으로 각 i번째 과정이 끝나면 앞에서 i개의 원소들은 최종 위치에 도달한 것이다. C++ 구현 template void selection_sort(RandomIt first, RandomIt last) { for (RandomIt it1 = first; it1 != last-1; ++it1) { RandomIt min = it1; for (RandomIt it2 = it1+1; it2 != last; ++it2) if (*it2 < *min) min = it2; auto temp = *it1; *it1 = *min; *min = temp; } } template.. 2021. 6. 11. [자료구조] 우선순위 큐 (Priority Queue) 개념 우선순위 큐(priority queue)는 임의의 순서로 입력된 우선순위된 원소들을 저장하고 우선순위에 따라 출력하는 추상 데이터 타입이다. 즉 언제든지 저장된 원소들 중 가장 우선순위가 높은 원소가 삭제된다. 성질 우선순위 큐는 항상 적용될 수 있는 비교 규칙이 필요하다. ≤으로 표기되는 비교 규칙이 항상 적용되기 위해서는 전체 순서(total order) 관계를 만족해야 한다. 전체 순서 관계는 모든 쌍의 두 키에 대하여 다음과 같은 특성을 만족한다. 반사성(Reflexive property): $k \le k$ 비대칭성(Antisymmetric property): 만약 $k_{1} \le k_{2}$ 이고 $k_{2} \le k_{1}$ 일 경우, $k_{1}=k_{2}$ 이행성(Transit.. 2021. 6. 11. 이전 1 2 3 4 5 6 다음 반응형
