DailyStudyNote

힙(Heaps) 힙(Heap) 이란 ? 완전 이진 트리(Complete Binary Tree)로 부모 노드의 값이 항상 자식 노드들의 값보다 크거나(Max Heap), 작아야(Min Heap) 한다. 힙은 우선순위 큐를 구현하거나, 힙 정렬을 하는 데 사용된다. 루트 노드에 있는 값이 최대값, 혹은 최소값이며, 자식 노드들의 값의 위치는 기본적인 조건만 맞추면 된다. 최대 힙(Max heap) 원소 삭제 1. 루트 노드 제거: → Max heap의 경우 최대 값 제거 → Min heap의 경우 최소 값 제거 2. 트리의 마지막 자리 노드를 임시로 루트 노드 자리에 배치 3. 자식 노드들 과의 값 비교 하며 아래로 이동 → 자식 노드들 중 더 큰 값 기준으로 이동 최대 힙(Max heap) 원소 삭제 - ..

이진 탐색 트리(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..

'어서와! 자료구조와 알고리즘은 처음이지?' 큐의 활용 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) - 데..

'어서와! 자료구조와 알고리즘은 처음이지?' 후위 표기 수식 계산 → Stack() ✔ 알고리즘 설계 1. 후위 표현식을 왼쪽 부터 한 글자씩 읽어서 피 연산자이면 스택에 push 2. 연산자를 만나면 스택에서 pop → (1) , 또 pop → (2) (2) 연산 (1) 을 계산 후 이 결과를 스택에 push 3. 수식의 끝에 도달하면 스택에서 pop() → 계산 결과 [ 문1. 후위 표현 수식 계산 ] ''' 1. for 문 돌면서 피 연산자인 경우 스택에 push 2. 연산자 만나면 스택에서 pop --> 1 pop --> 2 (2) 연산자 (1) 을 계산 후 이 결과를 스택에 push 3. 수식의 끝에 도달하면 스택에서 pop ''' class ArrayStack: def __init__(self..

'어서와! 자료구조와 알고리즘은 처음이지?' 중위표기법과 후위표기법 1) 중위 표기법 ✔ 연산자가 피 연산자들의 사이에 위치 (A+B) * (C+D) 2) 후위 표기법 ✔ 연산자가 피 연산자들의 뒤에 위치 AB+CD+* 3) 중위 표현식 → 후위 표현식 : 스택(Stack) 이용 알고리즘 설계 1. 연산자의 우선순위 설정 prec = { '*' : 3, '/' :3, '+' : 2, '-' :2, '(' :1 } 2. 중위 표현식을 왼쪽부터 한 글자 씩 읽어서 피연산자 이면 그냥 출력 3. '(' 이면 스택에 push, ')' 이면 '('이 나올 때까지 스택에서 pop 출력 4. 연산자이면 스택에서 그 보다 높거나 같은 우선 순위 것들을 pop 출력, 현재 만난 연산자는 스택에 push 3. 수식 끝까지..