목록Data structure (18)

YYYEJI

[DS] 트리(Tree)에서 이진트리(Binary Tree)로 변환하는 방법

Left_Child-Right_Sibling이란? 트리(tree)를 이진트리(binary tree)로 변형하는 규칙입니다. left child와 right sibling을 기억해 주세요! 트리(tree) → 이진트리(binary tree) 아래의 트리(tree)를 이진트리(binary tree)로 변형해 보도록 하겠습니다. 처음에는 root(ⓐ)를 하나 그려줍니다. root node의 left child는 ⓑ 노드이고, root(ⓐ) 노드의 sibling(형제)은 없기 때문에 아래와 같이 그려집니다. ⓑ 노드의 left child는 ⓔ 노드이고, sibling(형제)는 ⓒ 노드입니다. ⓔ 노드의 child는 없고 sibling은 ⓕ 노드이며, ⓒ 노드의 child도 없고 sibling은 ⓓ 노드이므로 아..
Data structure 2022. 12. 29. 17:09
[DS] 트리(Tree)와 이진트리(Binary Tree)란?

트리(Tree)란? 트리(Tree)는 node로 이루어진 계층적 종속관계를 표현하는 비선형 자료구조입니다. - Root라는 특별한 node가 존재 - root와 연결된 n(>=0)개의 subtree로 구성 - subtree도 각각의 tree임 - 사이클(cycle)이 존재할 수 X 트리(Tree) 관련 용어(Terminology) Node - tree에서 data를 저장하는 기본 단위 원소 Root - 가장 상위에 있는 한 개의 node Branch - node와 node간의 연결 (parent - child) - branch로 연결된 두 node의 관계 Sibling - 동일한 parent를 갖는 nodes Degree - node의 차수 Degree of a node - node subtree의 개수..
Data structure 2022. 12. 29. 17:05
[DS] 연결리스트(Linked list)를 이용한 큐(Queue) 구현

↓↓↓ 연결 리스트(Linked list)와 큐(queue) 먼저 공부하기 ↓↓↓ https://yyyeji.tistory.com/364 [DS] 큐(Queue)란? 큐(Queue)란? FIFO(First in First out)특성을 가지는 linear list입니다. Linear list의 한 쪽 끝(rear)위치에서 insert가 이뤄지고 다른 끝(front)에서 delete가 일어납니다. 그림과 같이 array를 사용해서 queue를 구현 yyyeji.tistory.com https://yyyeji.tistory.com/365 [DS] 연결 리스트(Linked List)란? Array를 사용한 list 표현에는 고정된 크기, 연속된 공간에 필요, 중간 원소 추가/삭제가 비효율적이라는 단점이 존재합..
Data structure 2022. 12. 29. 04:46
[DS] 연결리스트(Linked list)를 이용한 스택(Stack)

↓↓↓ 연결 리스트(Linked list)와 스택(stack) 먼저 공부하기 ↓↓↓ https://yyyeji.tistory.com/360 [DS] 스택(Stack)이란? 스택(Stack)이란? LIFO(Last in First out) 특성을 가지는 linear list입니다. Linear list의 한쪽 끝위치(TOP)에서 Push와 Pop이 이뤄집니다. (즉, stack에서 pop을 하면 그 원소가 가장 마지막에 넣은 원소입니다.) Sta yyyeji.tistory.com https://yyyeji.tistory.com/365 [DS] 연결 리스트(Linked List)란? Array를 사용한 list 표현에는 고정된 크기, 연속된 공간에 필요, 중간 원소 추가/삭제가 비효율적이라는 단점이 존재합니..
Data structure 2022. 12. 29. 04:24
[DS] 연결 리스트(Linked List)란?

Array를 사용한 list 표현에는 고정된 크기, 연속된 공간에 필요, 중간 원소 추가/삭제가 비효율적이라는 단점이 존재합니다. 이러한 단점을 개선한 자료 구조가 연결 리스트(Linked list)입니다. 연결 리스트(Linked List)란? 데이터(data)와 포인터(pointer)를 포함하는 노드(node)가 한 줄로 연결되어 있는 자료 구조입니다. Linked list를 구현하기 위한 ADT 정의 class node { public: string name; double score; node *link; void set_data(string s, double d); }; 데이터와 포인터를 포함한 node 클래스를 만들어줍니다. 포인터는 node 클래스를 가르키기 때문에 node type으로 정의합..
Data structure 2022. 12. 29. 03:16
[DS] 큐(Queue)란?

큐(Queue)란? FIFO(First in First out)특성을 가지는 linear list입니다. Linear list의 한 쪽 끝(rear)위치에서 insert가 이뤄지고 다른 끝(front)에서 delete가 일어납니다. 그림과 같이 array를 사용해서 queue를 구현하면 rear와 front가 모두 증가하는 형식으로 변화가 이뤄집니다. 그렇게 되면 언젠가는 rear가 array 끝 위치에 도달하게 될 것이고 원소를 더 이상 추가하지 못하게 됩니다. 즉 공간 사용이 너무 효율적이지 못하게 되는거죠. 그래서 나온 해결 방안이 circular queue입니다. Circular queue에도 문제점은 있습니다. full과 empty를 구분하는 방법이 모호해지기 때문입니다. 그래서 마지막 남은 한..
Data structure 2022. 12. 29. 01:49
[DS] Stack 응용 (infix, prefix, postfix)

수식을 표현하는데 3가지 표현이 있습니다. 수식(expression)의 표현 수식의 표현은 2진수 연산자(binary operator)를 표함하는 수식에서 연산자(operator)와 피연산자(operand)의 위치에 따라 결정됩니다. infix → a+b prefix → +ab postfix → ab+ infix - 두 피연산자(operand) 사이에 연산자(operator)가 위치한 수식 prefix - 두 피연산자(operand) 앞에 연산자(operator)가 위치한 수식 postfix - 두 피연산자(operand) 뒤에 연산자(operator)가 위치한 수식 prefix와 postfix를 알아야 하는 이유 우리에게는 infix가 익숙하지만 컴퓨터는 prefix와 postfix가 유리합니다. 수식..
Data structure 2022. 12. 28. 19:52
[DS] 스택(Stack)이란?

스택(Stack)이란? LIFO(Last in First out) 특성을 가지는 linear list입니다. Linear list의 한쪽 끝위치(TOP)에서 Push와 Pop이 이뤄집니다. (즉, stack에서 pop을 하면 그 원소가 가장 마지막에 넣은 원소입니다.) Stack을 구현하기 위한 ADT 정의 #include using namespace std; #define SIZE 100 class stack{ int list[SIZE]; int top; public: stack(); void push(int a); int pop(); bool stack_full(); bool stack_empty(); }; stack - stack을 생성한 초기 empty 상태 push - stack에 원소 한 개 ..
Data structure 2022. 12. 28. 04:12
이전 Prev 1 2 3 Next 다음