자료구조

Heap

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

Tree

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

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..