방앗간

※ 이진 탐색 트리 (Binary Search Trees) - 원소 삭제하는 과정 1. 키(key)를 이용해 노드를 찾는다. - 해당 키 노드가 없을 경우 삭제할 것도 없음 - 찾은 노드의 부모 노드도 알고 있어야 함 2. 찾은 노드를 제거하고도 이진 탐색 트리 성질을 만족하도록 트리 구조 정리 이와 관련되어 있지만 보다 심화과정을 배우고 싶다면 AVL 트리, Red-black 트리 를 학습하면 좋음

※ 이진 탐색 트리(Binary Search Trees) - 이진 트리의 일종. 왼쪽 서브트리에 있는 데이터는 모두 현재 노드의 값보다 작고 오른쪽 서브트리에 있는 데이터는 모두 현재 노드의 값보다 큰 성질을 만족하는 이진 트리임 정렬된 배열을 이용한 이진 탐색과 비교했을때, 장점으로는 데이터 원소의 추가와 삭제가 비교적 용이 단점으로는 공간 소요가 크다는 점이 있음 데이터 표현 - 각 노드는 (key, value) 한 쌍으로 구성되어 있음 이로 인한 특징은 키를 이용해서 검색이 가능하고 보다 복잡한 데이터 레코드로 확장이 가능함 연산의 정의 - insert(key, data) : 트리에 주어진 데이터 원소 추가 remove(key) : 특정 원소를 트리로부터 삭제 lookup(key) : 특정 원소를 ..

※ 이진트리 - 넓이 우선 순회(Breadth first traversal) - 원칙 : 수준(level)이 낮은 노드를 우선으로 방문 같은 수준의 노드들 사이에서는 부모 노드의 방문 순서에 따라 방문하고 왼쪽 자식 노드를 오른쪽 자식보다 먼저 방문함 => 재귀적 방식과 적합하지 않음 한 노드를 방문했을 때, 나중에 방문할 노드들을 순서대로 기록해 두어야함 => 큐(queue)를 이용해 보자 1. (초기화) traversal node 왼쪽, 오른쪽 자식들을 q에 추가 (존재할 경우만) 4. q가 빈 큐가 되면 모든 노드를 방문한 것으로 생각한다

※ 이진 트리(Binary Trees) : 트리에 포함되는 모든 노드의 차수가 2 이하인 트리를 뜻함 - size() : 현재 트리에 포함되어 있는 노드의 수를 구함 depth() : 현재 트리의 깊이 (또는 높이; height)을 구함 순회 (traversal) - 깊이 우선 순회(depth first traversal) 중위 순회(in-order traversal) 전위 순회(pre-order traversal) 후위 순회(post-order traversal) - 넓이 우선 순회(breadth first traversal)

※ 트리(Trees) - 정점(node)과 간선(edge)을 이용해 데이터의 배치 형태를 추상화한 자료 구조 트리의 높이(height) = 최대 수준(level) + 1 => 깊이(depth)라고도 부름 노드의 차수(Degree) = 자식(서브트리)의 수 이진트리(Binary Tree) = 모든 노드의 차수가 2 이하인 트리, 재귀적으로 정의할 수 있음 ※ 포화 이진 트리(Full Binary Tree) - 모든 레벨에서 노드들이 모두 채워져 있는 이진 트리(높이가 k이고 노드의 개수가 2^k-1인 트리) ※ 완전 이진 트리(Complete Binary Tree) - 높이 k인 완전 이진 트리

※ 우선순위 큐 (Priority Queues) - 큐가 FIFO 방식을 따르지 않고 원소들의 우선순위에 따라 큐에서 빠져나오는 방식임 응용 예시) 운영체제에서 CPU 스케줄러를 구현할 때, 현재 실행할 수 있는 작업 중 가장 우선순위가 높은 것을 골라 실행하는 알고리즘 등...

※ 환형 큐 (Circular Queues) : 정해진 저장 공간을 원 모양으로 돌려가며 이용 - 자료를 생성하는 작업과 그 자료를 이용하는 작업이 비동기적으로(asynchronously) 일어나는 경우 큐를 활용한다 - 자료를 생성하는 작업이 여러 곳에서 일어나는 경우 - 자료를 이용하는 작업이 여러 곳에서 일어나는 경우 - 자료를 생성하는 작업과 그 자료를 이용하는 작업이 양쪽 다 여러 곳에서 일어나는 경우 - 자료를 처리해 새로운 자료 생성하고, 나중에 그 자료를 또 처리해야 하는 작업인 경우 유의점으로는 큐가 가득 차게 될 경우 => 더이상 원소를 넣을 수 없다 이를 위해 큐에 데이터 원소가 가득 차 있는지 확인 할 수 있는 isFull() 연산이 있음

※ 큐 (Queues) :FIFO(선입선출) 특징을 가지는 선형구조 - 스택과 더불어 매우 빈번하게 이용되는 자료구조, 데이터 원소를 한 줄로 늘어세우는 자료 구조 선형(Linear)구조임. 하지만 넣을 때에는 한 쪽 끝에서 밀어 넣어야 하고[인큐(enqueue)연산] 꺼낼 때에는 반대 쪽에서 뽑아 꺼내야 하는 제약이 있음[디큐(dequeue)연산]. 연산의 정의 size() - 현재 큐에 들어 있는 데이터 원소의 수를 구함 isEmpty() - 현재 큐가 비어있는지를 판단 enqueue() - 데이터 원소 x를 큐에 추가 dequeue() - 큐의 맨 앞에 저장된 데이터 원소를 제거 혹은 반환 peek() - 큐의 맨 앞에 저장된 데이터 원소를 반환 (제거하지는 않음)

※ 후위 표기 수식 계산 - A B + C D + * (1), pop -> (2). (2) 연산 (1) 을 계산, 이 결과를 스택에 push 수식의 끝에 도달하게 되면 스택에서 pop -> 이러한 과정을 거쳐 계산 결과가 나옴

※ 수식의 후위 표기법 (Postfix Notation) - 중위 표기법 (infix notation) : 연산자가 피연산자들의 사이에 위치함 [ (A+B) * (C+D) ] - 후위 표기법 (postfix notation) : 연산자가 피연산자들의 뒤에 위치함 [ A B + C D + * ] 예시) [중위] A * B + C > [후위] A B * C + / [중위] A + B * C > [후위] A B C * + ※ 괄호의 처리 여는 괄호는 스택에 push 하고 닫는 괄호를 만나면 여는 괄호가 나올 때 까지 pop ※ 알고리즘의 설계 - 중위 표현식을 왼쪽부터 한 글자씩 읽어서 피연산자라면 그냥 출력 '(' 이면 스택에 push ')' 이면 '('이 나올 때까지 스택에서 pop 출력 연산자라면 스택에..