자료구조 (22) 썸네일형 리스트형 5-5강 - Heap (힙) 6. Heap 0) Priority Queue 우선 순위가 가장 높은(혹은 낮은) 원소를 먼저 삭제한다. 1> linear list으로 구현 - isEmpty : O(1) - top : O(n) - push : O(1) - pop : O(n) 2> max heap으로 구현 - isEmpty : O(1) - top : O(1) - push : O(logn) - pop : O(logn) 1) Heap의 정의 1> max heap (자식 node가 존재할 때) 각 node의 key value이 그 자식의 key value보다 작지 않은 tree max heap은 complete binary tree이면서 max tree이다. 2> basic operation - Creation of an empty heap .. 5-4강 - Threaded Binary Trees (스레드 이진 트리) 5. Threaded Binary Trees inorder 기반 0) 기존 Binary Tree의 문제점 1> Null link가 실제 pointer보다 더 많다. ∵node의 개수가 n개이면 전체 link의 개수는 2n이고 Null link는 n+1개이다. (by Discrete Mathematics) 2> 그래서 Null link를 thread라는 다른 node를 가리키는 pointer로 대체 (thread : Null link가 아무 node도 가리키지 못해서 다른 node를 가리키는 pointer로 변경) 1) thread 1> thread 규칙 - ptr->left_child == NULL => ptr inorder predecessor에 대한 pointer로 대체 (left_child을 방문하.. 5-3강 - Binary Tree Traversals (이진 트리 순회) 이 부분은 예시 동영상과 함께 보며 문제를 푸는 것이 좋다. 0) 이진 트리 순회에 대한 소개 1> 전제 : tree의 모든 node를 한 번씩만 방문한다. 2> linear order의 필요성 1> 완전한 순회를 위해서 linear order가 필요하다. 2> 그리고 이 순서가 subtree(child들)에도 동일하게 적용되어야 한다. 3> 기호 L : left child로 pointer로 이동 R : right child로 pointer로 이동 V : node 방문 4> order의 종료 LVR : inorder traversal (중위 순회) VLR : preorder traversal (전위 순회) LRV : postorder traversal (후위 순회) VRL, RVL, RLV 1) Inor.. 5-2강 - Binary Trees (이진 트리) 이전 5-1강에서 저희는 어떠한 tree든지 binary tree로 표현할 수 있다고 배웠습니다. https://intelligentcm.tistory.com/155 2. Binary Trees 0) binary tree에 대한 소개 1> binary tree의 특징 - 모든 tree는 binary tree로 표현할 수 있다. - 모든 node의 degree 그래서 Binary Tree는 Tree와 다른 객체입니다. (Binary Tree는 [1] empty tree가 가능하며 [2] subtree를 구분합니다.) 2> 다른 binary tree (binary tree은 left와 right를 구분한다.) 3> special tree (skewed tree, complete binary tree) - (.. 5-1강 - Trees 1. Trees 1) 정의 1> 1개 이상의 node로 이루어진 finite set 2> root 3> root을 제외한 나머지 node들은 disjoint set(subtree) T_1, ... , T_n으로 분할(partition)할 수 있다. (위의 그림에서도 맨 위의 root와 그 아래 3개의 subtree가 존재한다.) 2) tree의 용어 (뿌리가 위부터 자라서 아래는 잎이 있는 나무의 구조를 연상한다.) 1> node : 정보를 가지며 다른 node와 연결된 branch를 가지는 tree의 기본 단위 2> degree of node : 해당 node의 subtree 개수 3> degree of tree : 해당 tree의 node 개수 4> leaf : degree가 0인 node (=ter.. 3-5강 - Multiple Stack and Queue (다중 스택, 다중 큐) 7. Multiple Stack and Queue 1) 개념 1> 정의 : 하나의 array 안에 여러 개의 stack(queue)를 구현 2> idea : m개의 원소를 가진 array를 n개의 stack이 들어갈 수 있게 n등분한다. 2) 구현 1> 선언 - MEMORY_SIZE : array의 size - MAX_STACKS : stack의 최대 개수 + 1 (boundary[0] ~ boundary[n]까지 넣어야하니까) - element memory[MEMORY_SIZE] : array 선언 - int top[MAX_STACKS] : memory(array)를 n등분하는 index - int boundary[MAX_STACKS] : memory(array)를 n등분하는 index - int n .. 3-4강 - Evaluation of Expressions (수식의 계산) 6. Evaluation of Expressions 1) Expressions (수식) 0> 예시 - ((rear+1 == front ) || ((rear == MAX_QUEUE_SIZE-1) && !front)) - x = a/b-c+d*e-a*c 1> 수식의 구성 요소 - operators (연산자) - operands (피연산자) - parentheses (괄호) 2> 연산 순서에 영향을 미치는 요인 : precedence hierarchy, associativity, 괄호 - 어떤 언어든 연산자의 연산 순서를 결정하는 precedence hierarchy가 존재한다. - precedence가 같을 경우 associativity을 따져본다. (left-to-right vs right-to-left).. 3-3강 - Mazing Problem (미로 문제) cf> 미로는 stack의 좋은 응용이 될 것이다. 5. Mazing Problem 1) 미로 표현 방법 1> 미로 구조 - 미로 전체는 Two-dimensional array로 표현한다. ( maze[R][C] ) - 그리고 이동 가능한 길을 0, 벽을 1로 표현한다. - 미로 경계를 표현하기 위해 ( maze[R+2][C+2] ) 행과 열을 2개씩 더 확보하고 경계 부분을 1로 표시한다. - 미로의 입구는 [1][1]이며 미로의 출구는 [R][C]이다. 2> 이동 방향 - 기본적으로 8개 방향으로 이동 가능하다. x방향과 y방향을 가지는 구조체 생성 8개의 구조체(원소)를 가지는 구조체 array 생성 - 하지만 [row][col] 주변에 경계 혹은 벽이 있을 경우 이동 가능한 방향이 적어질 수 있다.. 이전 1 2 3 다음
