반응형 자료구조및알고리즘35 (Pyhton/Heap) 힙 (Heap) Heap :이진 트리의 한 종류 루투 노드가 언제나 최댓값, 최솟값 완전 이진 트리여야함 (레벨 k-2 까지는 모든 노드가 2개의 자식을 가진 포화 이진트로 , k-1 에서는 노드가 순차적) maxheap, minheap 이진탐색트리와의 비교 1, 완전한 크기순인가 >> 아니다 2. 빠르게 검색할 수 있는가 >> 아니다 >> 3. 부가 제약조건? >> 완전이진트리 여야함 최대힙 (Max Heap) __init__() : 빈 최대힙 생성 insert(item) - 새로운 원소 삽입 remove() 최대 원소를 반환 (root node) >> 동시에 삭제 표현 (배열 이용) 왼쪾 자식의 번호 : 2*m , 오른쪽은 2*m +1 부모 m // 2 노드 마지막 노드에서만 삭제/추가 가능 insert 구현 cla.. 2022. 12. 16. (Python/이진트리) 이진트리(3) 이진 탐색트리: 모든 노드에 대해서 왼쪽 트리에 있는 데이터는 모두 현재 노드의 값보다 작고 오른쪽 노드는 반대 인 이진트리 힙큐랑은 다르다 힙큐는 맨 위 노드가 최솟값 노드 배열 이용/ 이진트리 이용 이진트리 : 장점 : 데이터 원소의 추가, 삭제가 용이 단점: 공간 소요가 큼 거의 O(logn) 임 노드는 키와 밸류를 가지고있음. insert (key, data) - 추가 remove(key) - 삭제 lookup(key) - 찾기 inorder() - 키 순서대로 데이터 나열 min(),max() -최소 최대 원소 삽입 구현 (insert) class Node: def __init__(self, key, data): self.key = key self.data = data self.left = No.. 2022. 12. 6. (Python/이진트리)이진트리(2) 2) 넓이 우선 순회 원칙 - 수준이 낮은 노드를 우선으로 방문 - 같은 수준의 노드들 사이에는 부모 노드 방문순서에 따라 방문 왼쪽이 오른쪽보다 우선 dfs 와 유사 재귀적 비효율 한 노드를 방문할때 나중에 방문할 노드들은 순서대로 기록해둬야함 >> 큐(queue) 사용 스택에 a ,b, c 순서로 들어가고 내려갈 자식노드가 없으면 큐에스 팝해주고 하는식 구현 문제 import queue class ArrayQueue: def __init__(self): self.data = [] def size(self): return len(self.data) def isEmpty(self): return self.size() == 0 def enqueue(self, item): self.data.append(it.. 2022. 12. 1. (Python/이진트리)이진트리(1) size() - 노드의 수 depth() 트리의 깊이 traversal : 순회 Node 는 Data ,leftchild, rightchild 를 가진다. 순회 종류: 1.깊이 우선순회 중위 순회 : 가운데 자기자신 left > 자신 > right 전위 순회 : 자기자신 먼저 후위 순회 : 자기자신이 맨 마지막 D에 입장에서 생각했을때 자기자신 D를 맨 마지막에 방문하고 그 다음 B에 left , right, 자신 순서니깐 D 다음에 B가 아닌 E 부터 방문한다. 1-1 depth 구현 class Node: def __init__(self, item): self.data = item self.left = None self.right = None def size(self): l = self.left.siz.. 2022. 12. 1. (Python/Queue) 우선순위 큐 큐가 FIFO 방식을 따르지 않고 원소들의 우선순위에 따라 큐에서 빠져나오는 방식 heapq 를 사용하면 맨 앞에 최솟값이라 heapq 를 사용하면 좋다. 활용 운영체제 cpu 스케줄러 구현 방법: 1. enqueue 할때 우선순위 유지 (더 유리) 2.Dequeue 할때 우선순위 높은 것을 선택하는 방법 선형 배열 보다 연결리스트 이용하는것이 더 유리(시간적) class Node: def __init__(self, item): self.data = item self.prev = None self.next = None class DoublyLinkedList: def __init__(self): self.nodeCount = 0 self.head = Node(None) self.tail = Node(No.. 2022. 11. 23. (Python/Queue) CircularQueue (환형큐) 큐의 활용: 1. 자료를 생성하는 작업과 그 자료를 이용하는 작업이 비동기적으로 일어나는 경우. 2. 자료를 생성하는 작업이 여러곳에서 일어나는 경우. 3. 자료를 이용하는 작업이 여러곳에서 일어나는 경우. 4.자료를 생성하는 작업과 그 자료를 이용하는 작업이 양쪽 여러곳에서 일어나는 경우 5. 자료를 처리하여 새로운 자료를 생성하고 나중에 그 자료를 또 처리해야 하는 작업의 경우 CircularQuueu(환형큐) 꺼내는곳 front 넣는곳 rear 라고 칭함 큐가 가득차면 원소를 넣을 수 없음 dequeue 가 가지고 있는 내장함수 + isFull() 큐에 데이터 원소가 꽉 차있는지 확인 enqueue, dequeue, peek 구현 class CircularQueue: def __init__(self.. 2022. 11. 23. 이전 1 2 3 4 5 6 다음 반응형
