Computer Sience/Data Structure5 [PriorityQueue] 우선순위 큐 + Heap 목차 설명 + 시간 복잡도Heap 설명Heap의 삽입 순서Heap (삽입)Insert SimulationHeap FindHeap Erase Simulation 자바 PriortyQueue 계층 구조 이진 검색 트리 기반 vs heap 기반참고자료설명 + 시간 복잡도우선순위 큐 = pop을 할 때 가장 먼저 들어온 원소가 나오는 대신 우선순위가 가장 높은 원소가 나오는 큐원소의 추가가 O(lg N)우선순위가 가장 높은 원소의 확인 O(1)우선순위가 가장 높은 원소의 제거가 O(lg N)그냥 배열로 구현을 하면 세 연산의 시간복잡도가 O(1), O(N), O(N)이 되겠지만Heap 구조를 이용하면 O(lg N), O(1), O(lg N)에 가능하다. Heap이진 트리의 모양을 가지는 자료 구조이진 트리 : .. 2024. 5. 11. TreeSet, TreeMap TreeSet, TreeMap - 자바 이진 검색 트리 기반 자료 구조 TreeSetTreeMap이진 검색 트리에 대한 자세한 내용 https://20240228.tistory.com/87 [BinarySearchTree] 이진 검색 트리목차트리 용어 정리이진 트리이진 검색 트리연산(Insert, Delete, Update, Find) 시뮬레이션이진 검색 트리 - 시간 복잡도자가 균형 트리용어 정리정점 : 트리에서의 각 원소루트 : 주어진 트리에서의 120240228.tistory.comTreeSet정렬된 집합 (Set)을 구현한 클래스, 이진 검색 트리 기반중복된 요소 허용 x - SortedSet 인터페이스의 확장요소들이 정렬된 순서로 저장 - SortedSet 인터페이스의 확장내부적으로 레드 -.. 2024. 5. 10. NavigableSet 인터페이스 NavigableSet Java 컬렉션 프레임워크에서 제공하는 인터페이스SortedSet 인터페이스의 확장정렬된 집합(Set)에 대한 탐색 및 탐색 기반의 연산 지원TreeSet은 NavigableSet 인터페이스를 구현하여 네비게이션 기능 제공public interface NavigableSet extends SortedSetNavigableSet 계층 구조 NavigableSet 메서드 정리 lower(E e) : 주어진 요소 e 보다 작은 요소 중에서 가장 큰 요소를 반환한다.floor(E e) : 주어진 요소 e 와 같거나 작은 요소 중에서 가장 큰 요소를 반환ceiling(E e) : 주어진 요소 e 와 같거나 큰 요소 중에서 가장 작은 요소를 반환higher(E e) : 주어진 요소 e 보다 .. 2024. 5. 10. [BinarySearchTree] 이진 검색 트리 목차트리 용어 정리이진 트리이진 검색 트리연산(Insert, Delete, Update, Find) 시뮬레이션이진 검색 트리 - 시간 복잡도자가 균형 트리용어 정리정점 : 트리에서의 각 원소루트 : 주어진 트리에서의 1번 정점리프 : 제일 말단에 위치해서 아래로 뻗은게 없는 정점간선 : 정점을 연결하는 선부모 - 자식 관계 : 간선으로 연결된 위 아래의 관계서브 트리 : 어떤 한 정점에 대해 그 밑에 있는 정점과 간선만을 모은 트리트리의 높이 : 위 아래로 뻗어있는 정도이진 트리 (Binary Tree)각 노드의 자식이 2개 이하인 트리이진 검색 트리 (Binary Search Tree)왼쪽 서브트리의 모든 값은 부모의 값보다 작고 오른쪽 서브트리의 모든 값은 부모의 값보다 큰 이진 트리 왜 이진 검색 .. 2024. 5. 9. [Hash] 해시 목차해시?충돌?충돌회피(Chaining)충돌회피(OpenAddressing)OpenAddressing (Linear Probing)OpenAddressing (Quadratic Probing)OpenAddressing (Double Hashing)해시해시 자료구조 : 키(Key)에 대응하는 값(Value)을 저장하는 자료구조 이러한 테이블을 해시 테이블이라고 한다.이렇게 해시 함수를 이용해서 해시 테이블을 구현하면 삽입(put), 삭제(remove), 검색(get) 등 모든 연산이 O(1)에 동작한다.충돌 충돌 현상 설명카드 번호 0000 0000 0000 5135 : kim 을 삽입이때 카드 번호 9999 9999 9999 5135 는 누구의 카드 번호인가 질문그럼 Kim이라고 대답한다.Kim의 카드 .. 2024. 5. 9. 이전 1 다음
