hado-dev-log 📚

깊이 우선 순회 (Depth First Traversal) 중위 순회 (in-order travelsal) : 왼쪽 서브트리를 순회한 뒤 노드 x를 방문, 그리고 나서 오른쪽 서브트리를 순회 전위 순회 (pre-order travelsal) : 노드 x를 방문한 후에 왼쪽 서브트리를 순회, 마지막으로 오른쪽 서브트리를 순회 후위 순회 (post-order traversal) : 왼쪽 서브트리를 순회, 오른쪽 서브트리를 순회 후 마지막으로 노드 x를 방문 class Node: def __init__(self, item): self.data = item self.left = None self.right = None def inorder(self): traversal = [] if self.left: trav..

이진 트리는 트리에 포함되는 모든 노드의 차수가 2 이하인 트리를 말한다. 즉 모든 노드는 자식이 없거나 (리프노드의 경우), 하나만 있거나 아니면 둘 있는 세 경우 중 하나에 해당한다. 이진 트리의 추상적 자료구조 연산의 정의 size() - 현재 트리에 포함되어 있는 노드의 수를 구함 depth() - 현재 트리의 깊이 (또는 높이; height)를 구함 순회 (traversal) 이진 트리의 자료구조 구현 # 노드 클래스 # 이진트리의 구현 - 노드(node) class Node: def __init__(self, item): self.data = item self.left = None self.right = None # 트리 클래스 # 이진 트리의 구현 - 트리(tree) class BinaryT..

트리(tree)는 데이터의 검색과 탐색에 아주 널리 이용되는 자료구조로서 데이터베이스 시스템 또는 검색 엔진 등에서 아주 많이 이용된다. 트리는 순환하는 길이 없는 그래프(graph)이고, 정점(node)와 간선(edge)을 이용하여 데이터의 배치 형태를 추상화한 자료구조이다. 트리의 용어 이해 이진 트리 (binary trees) 모든 노드의 차수가 2 이하인 트리를 말한다. 이진트리는 재귀적으로 정의할 수 있는데 빈트리(empty tree)이거나 루트 노드 + 왼쪽 서브트리 + 오른쪽 서브트리 (단, 이때 왼쪽과 오른쪽 서브트리 또한 이진트리)이면 이진트리이다. 포화 이진 트리 (full binary tree) 모든 레벨에서의 노드들이 모두 채워져 있는 이진트리를 말한다. 포화 이진 트리는 높이가 K..

기존의 큐는 선입선출, 즉 FIFO (First-In First Out)방식이 적용이 된다. 우선순위 큐는 이 방식을 따르지 않고 원소들의 우선순위에 따라 꺼내는 자료구조이다. 대표적인 응용 예로는 운영체제에서 CPU 스케줄러를 구현할 때 현재 실행할 수 있는 작업들 중 가장 우선순위가 높은 것을 골라 실행하는 알고리즘을 들 수 있다. 우선순위 큐의 구현 우선순위 큐를 구현할 때 서로 다른 두가지 방식이 가능하다. 큐에 원소를 넣을 때 (enqueue할 때) 우선순위 순서대로 정렬해 두는 방법 큐에서 원소를 꺼낼 때 (dequeue할 때) 우선순위가 가장 높은 것을 선택하는 방법 두가지 방법 중 1번이 더 유리하다. 만약 큐에 데이터 원소들이 우선순위가 상관없이 늘어서 있다고 하면 우선순위가 가장 높은 ..

큐의 활용 자료를 생성하는 작업과 그 자료를 이용하는 작업이 비동기적으로(asynchronously) 일어나는 경우 자료를 생성하는 작업이 여러 곳에서 일어나는 경우 자료를 이용하는 작업이 여러곳에서 일어나는 경우 자료를 생성하는 작업과 그 자료를 이용하는 작업이 양쪽 다 여러 곳에서 일어나는 경우 자료를 처리하여 새로운 자료를 생성하고, 나중에 그 자료를 또 처리해야 하는 작업의 경우 환형 큐(Circular Queue) 정해진 개수의 저장 공간을 빙 돌려가며 이용 큐가 가득차면 더이상 원소를 넣을 수 없으니 큐가 가득 찼는지 비어있는지 판단하기 위해서는 큐의 길이를 기억하고 있어야한다. 환형 큐의 추상적 자료구조 구현 환형 큐를 구현하는데에도 선형 배열을 이용하거나 연결리스트를 이용할 수 있지만 여기..

드디어 큐! 스택과 더불어 매우 빈번하게 이용되는 자료구조이다. 큐는 자료(data element)를 보관할 수 있는 선형구조로 선형배열, 연결 리스트, 스택과 비슷하지만 스택과는 반대인 특성을 가지고 있다. 큐는 넣을 때에는 한 쪽 끝에서 밀어 넣어야(enqueue연산)하고 꺼낼 때에는 반대 쪽에서 뽑아 꺼내는(dequeue연산) 선입선출(FIFO; First-In First-Out)의 특성을 가지고 있다. 큐의 동작 큐의 추상적 자료구조 구현 1. 배열(array)을 이용하여 구현 python 리스트와 메서드들을 이용 2. 연결 리스트(linked list)를 이용하여 구현 이전에 구현한 양방향 연결 리스트 이용 연산의 정의 size() - 현재 큐에 들어있는 데이터 원소의 수를 구함 isEmpty(..

후위 표기 수식 계산 문제 설명 인자로 주어진 문자열 expr 은 소괄호와 사칙연산 기호, 그리고 정수들로만 이루어진 중위 표현 수식입니다. 함수 solution() 은 이 수식의 값을 계산하여 그 결과를 리턴하도록 작성되어 있습니다. 이 함수는 차례로 splitTokens(), infixToPostfix(), 그리고 postfixEval() 함수를 호출하여 이 수식의 값을 계산하는데, splitTokens() - 강의 내용에서와 같은 코드로 이미 구현되어 있습니다. infixToPostfix() - 지난 강의의 연습문제에서 작성했던 코드를 수정하여, 문자열이 아닌 리스트를 리턴하도록 작성합니다. postfixEval() - 이번 강의의 연습문제입니다. 함수의 내용을 완성하세요. 즉, 두 개의 함수 in..

중위 표기법 ( infix notation ) 연산자가 피연산자들의 사이에 위치 ( A + B ) * ( C + D ) 후위 표기법 ( postfix notation ) 연산자가 피연산자들의 뒤에 위치 A B + C D + * 중위 표현식 -> 후위 표현식 괄호의 처리 여는 괄호는 스택에 push, 닫는 괄호를 만나면 여는 괄호가 나올 때 까지 pop한다. 연산자를 만났을 때, 여는 괄호 너머까지 pop하지 않도록 하려면 여는 괄호의 우선순위는 가장 낮게 설정해야한다. 알고리즘 설계 연산자의 우선순위 설정은 파이썬 사전을 활용하여 prec를 생성한다. 중위 표현식을 왼쪽부터 한 글자씩 읽어서 피연산자이면 그냥 출력, '('이면 스택에 push, ')'이면 '('이 나올 때까지 pop해서 출력한다. 연산자..