Heap

🎄 특별한 이진 트리 완전 이진 트리에서 부모 노드가 자식 노드 값보다 같거나 작은(MinHeap)/큰(MaxHeap) 경우를 만족한다. 현재 남아있는 원소들 중 최대값 or 최솟값을 빠르게 계속 얻고 싶은 경우에 유용 heap만드는 데 O(NlogN) 소요 이후 삽입, 삭제 O(logN) 최소값 or 최대값 탐색 O(1)

• format_list_bulleted 카테고리 없음
• · 2022. 11. 19.
• textsms

Tree

트리 🌲 정점끼리 전부 연결되어 있으면서 사이클이 존재하지 않는 그래프 ⬆️위와 같은 가계도 모양을 생각하면 노드는 가문의 각 구성원이며 왜 상위 노드를 부모 노드, 하위 노드가 자식 노드라고 불리는지 쉽게 이해할 수 있다. 이 예시로 트리 용어들을 일상적으로 비유해 본다면 루트 노드는 가문의 선조, 차수는 각 구성원에서 뻗어나간 가지 수로 몇 명의 자식이 있는지, 깊이는 현재 구성원이 선조로부터 몇 세대 내려왔는지, 높이는 마지막 후손의 깊이이다. 이진 트리 🌲 자식 수가 최대 2개인 트리 이진트리 탐색 전위 탐색: 부모 - 좌 - 우 중위 탐색: 좌 - 부모 - 우 후위 탐색: 좌 - 우 - 부모 이진탐색트리 왼쪽 방향에 있는 노드들은 전부 부모 보다 값이 작아야 함 우측 방향에 있는 노드들은 전부 ..

• format_list_bulleted 카테고리 없음
• · 2022. 11. 19.
• textsms

Linked List

연결 리스트 연결된 데이터를 저장할때 사용합니다. 연결리스트를 구성하는 노드의 구조는 다음과 같습니다. node data link(next) 장점단점 삭제와 삽입 O(1) 길이가 정해지지 않은 데이터를 다룰때 유용 메모리 요구량이 더 크다 원하는 위치 검색할 때 처음부터 다 확인해야한다 배열과 비교 배열연결리스트 삽입/삭제 O(n) O(1) 저장공간 연속한 위치 임의의 위치 탐색 O(1) O(n) 단순 연결 리스트 구현 노드 class Node: def __init__(self, item): self.data = item self.next = None 연결 리스트 class LinkedList: def __init__(self): self.nodeCount = 0 # 노드의 개수 self.head = N..

• format_list_bulleted 카테고리 없음
• · 2022. 11. 19.
• textsms