DailyStudyNote

'어서와! 자료구조와 알고리즘은 처음이지?' 이진트리의 넓이 우선 순회(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) - 데..

'어서와! 자료구조와 알고리즘은 처음이지?' 후위 표기 수식 계산 → 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. 수식 끝까지..