DailyStudyNote

힙(Heaps) 힙(Heap)이란? 이진 트리의 한 종류 (이진 힙-binary heap)이다. 1. 루트(root) 노드가 언제나 최댓값 또는 최솟값을 가진다. 최대 힙(max heap) 최소 힙(min heap) 2. 완전 이진 트리 완전 이진 트리란 각 노드가 최대 2개의 자식 노드를 갖는 트리 형태의 자료구조 로서 마지막 레벨을 제외한 모든 노드는 완전히 채워져 있어야 한다. 최하단 레벨의 노드는 좌측만 노드가 채워져 있거나 좌측과 우측 모두 채워져 있어야 한다. 노드를 삽입할 때는 최하단 좌측 노드부터 차례대로 삽입해야 한다. 최대 힙(max heap)의 추상적 자료 구조 재귀적으로도 정의된다. 즉, 어느 노드를 루트로 하는 서브 트리도 모두 최대 힙 이다. 연산의 정의 __init__(): 빈..

이진 탐색 트리(BST, Binary Search Tree) 이진 탐색 트리 정의 이진탐색 트리란 모든 노드에 대해서, 왼쪽 서브트리에 있는 데이터는 모두 현재 노드 값보다 작고, 오른쪽 서브트리에 있는 데이터는 모든 현재 노드의 값보다 큰 성질을 만족하는 이진트리이다. 왼쪽 및 오른쪽 하위 트리도 각각 이진 탐색 트리이며, 각 노드는 중복된 키를 허용하지 않는다. 연산의 정의 ▶ insert(key, data) : 트리에 주어진 데이터 원소를 추가한다. ▶ remove(key) : 특정 원소를 트리로 부터 삭제한다. ▶ lookup(key) : 특정 원소를 검색한다. ▶ inorder(): 키의 순서대로 데이터 원소를 나열한다. ▶ min(), max(): 최소 키, 최대 키를 가지는 원소를 각각 탐색..

'어서와! 자료구조와 알고리즘은 처음이지?' 이진트리의 넓이 우선 순회(BFS; Breadth First Traversal) 원칙 ✔ 수준(level)이 낮은 노드를 우선으로 방문 ✔ 같은 수준의 노드들 사이에서는 부모 노드의 방문 순서에 따라 방문 ✔ 왼쪽 자식 노드를 오른 쪽 자식 노드보다 먼저 방문 ✔ 한 노드를 방문했을 때, 나중에 방문할 노드들을 순서대로 기록(방문한 노드의 자식 노드 기록) ✔ 큐(Queue) 이용 → 순회 결과: A - B - C - D - E - F - G - H - J 알고리즘 설계 1. traversal 빈 리스트 초기화 2. 빈 트리가 아니면(root != None) root node를 큐에 추가(enqueue) 3. q 가 비어있지 않는 동안, 3.1 node ← q..

'어서와! 자료구조와 알고리즘은 처음이지?' 이진 트리(Binary Tree) 연산의 정의 1. size() - 현재 트리에 포함되어 있는 노드의 수를 구한다. 2. depth() - 현재 트리의 깊이 (또는 높이, height)를 구한다. 3. 순회(traversal) 이진 트리의 구현 - 노드(Node) class Node: def __init__(self, item): self.data = item self.left = None self.right = None 이진 트리의 구현 - 트리(Tree) class BinaryTree: # r 은 node def __init__(self, r): self.root = r 이진 트리의 구현 - size() 재귀적인 방법으로 쉽게 구할 수 있다. class N..

'어서와! 자료구조와 알고리즘은 처음이지?' 트리(Tree) 정점(node)와 간선(edge)을 이용하여 데이터의 배치 형태를 추상화한 자료구조 ✔ 부모의 부모(의 부모의...) - 조상(ancestor) ✔ 자식의 자식(의 자식의...) - 후손(descendant) 트리의 높이(Height) 트리의 높이(height) = 최대수준(level) + 1 트리의 높이는 깊이(depth)라고도 한다. 부분트리(서브트리, SubTree) 노드의 차수(Degree) = 자식(서브트리)의 수 degree 가 0인 노드는 leaf 노드이다. 이진트리(Binary Tree) 모든 노드의 차수가 2 이하인 트리 이진트리는 재귀적으로 정의할 수 있다. ✔ 빈 트리(Empty Tree)이거나 ✔ 루트노드 + 왼쪽 서브트리..

우선순위 큐(Priority Queue) 큐가 FIFO(First-In First-Out) 방식을 따르지 않고, 원소들의 우선순위에 따라 큐에서 빠져나오는 방식 우선 순위 큐 구현 [2가지 방식] 1. Enqueue 할 때 우선순위 순서를 유지하도록 한다. 2. Dequeue 할 때 우선순위 높은 것을 선택한다. → (1) 방식이 더 유리하다. [2가지 구현 방식] 1. 선형 배열 이용 2. 연결 리스트 이용 → (2) 방식이 시간적으로 더 유리하다. 문1. 우선순위 큐의 enqueue 연산 구현 class Node: def __init__(self, item): self.data = item self.prev = None self.next = None class DoublyLinkedList: def ..

'어서와! 자료구조와 알고리즘은 처음이지?' 큐의 활용 1. 자료를 생성하는 작업과 그 자료를 이용하는 작업이 비 동기적으로(asynchronously) 일어나는 경우 2. 자료를 생성하는 작업이 여러 곳에서 일어나는 경우 3. 자료를 이용하는 작업이 여러 곳에서 일어나는 경우 4. 자료를 생성하는 작업과 그 자료를 이용하는 작업이 양쪽 다 여러 곳에서 일어나는 경우 5. 자료를 처리하여 새로운 자료를 생성하고, 나중에 그 자료를 또 처리해야 하는 작업의 경우 환형 큐 정해진 개수의 저장공간을 빙 돌려가며 이용하는 큐 환형 큐의 추상적 자료구조 구현 연산의 정의 1. size() - 현재 큐에 들어있는 데이터 원소의 수를 구한다. 2. isEmpty() - 현재 큐가 비어 있는지를 판단한다. 3. isF..

'어서와! 자료구조와 알고리즘은 처음이지?' 큐(Queue) ✔ 자료를 보관할 수 있는 선형 구조 ✔ 데이터 삽입 시에는 한 쪽 끝에서 밀어 넣어야 한다. → 인큐(enqueue) 연산 ✔ 데이터 꺼낼 시에는 반대쪽에서 꺼내야 한다. → 디큐(dequeue) 연산 ✔ 선입선출(FIFO, First-In First-Out) 특징을 가진다. 큐의 추상적 자료구조 구현 1. 배열(Array)를 이용하여 구현한다. → 파이썬 리스트와 메서드를 이용 2. 연결 리스트(Linked list)를 이용하여 구현한다. → 양 방향 연결리스트를 이용 연산의 정의 1. size() - 현재 큐에 들어있는 데이터 원소의 수를 구한다. 2. inEmpty() - 현재 큐가 비어있는지를 판단한다. 3. enqueue(x) - 데..