본문 바로가기

Data Structure & Algorithm/자료구조7

[자료구조] Directed Graph References Data Structrue : A Pseudocode Approach with C Contents Graph Directed Graph Graph 그래프는 정점(vertex, vertices)라고 불리는 노드(node)들과 이 정점들을 연결해주는 간선(edge)로 이루어진 자료구조입니다. 아래 그림에서 A, B, ..., E, F에 해당하는 것들을 정점(vertex)라고 부르고, 이 vertex 사이의 선을 간선(edge)라고 합니다. 그리고 그래프는 여러 종류가 있지만, 위 그림처럼 크게 directed graph, 방향을 가지는 그래프와 undirected graph, 방향을 가지지 않는 그래프로 분류할 수 있습니다. 즉, 간선(edge)가 방향을 가지느냐 가지지 않느냐로 나누어 .. 2021. 10. 4.
[자료구조] Binary Search Tree(BST) - 참조 문헌 및 사이트(Reference) Data Structure : A Pseudocode Approach with C Data Structure and Algorithm in C++ 이번 글에서는 BST, 이진 탐색 트리에 대해서 알아보겠습니다. 이진 탐색 트리는 이진 트리이면서, 아래와 같은 성질을 갖고 있습니다. 1. 루트 노드의 왼쪽 서브트리의 모든 Key는 루트 노드의 Key보다 작다. (All of left subtree = root) 3. 각 서브트리는 그 자체로 이진 탐색 트리이다. 여기서 Key는 노드의 데이터가 될 수도 있고, 다른 기준이.. 2020. 9. 9.
[자료구조] 우선순위큐(priority queue), 힙(heap) - 참조 문헌 및 사이트(Reference) Data Structure : A Pseudocode Approach with C Data Structure and Algorithm in C++ 이번 글에서는 우선순위큐(Priority Queue)에 대해서 알아보겠습니다. 우선순위큐도 C++ STL 헤더에서 제공하는 컨테이너이며, 큐와 동일하게 push, pop, top이라는 연산이 있습니다. 다만, 일반 큐와는 다르게 동작합니다. 큐에서는 제일 먼저 들어왔던 데이터가 제일 먼저 삭제가 되었지만, 우선순위큐에서는 우선순위가 현재 우선순위큐 안에서 우선순위가 가장 높은 데이터가 먼저 삭제가 됩니다. 만약 값이 클수록 우선순위를 갖는 우선순위큐에 [ 8 78 19 45 23 56 32 ] 의 순서로 데이터를 삽.. 2020. 9. 4.
[자료구조] 트리(Tree) - 참조 문헌 및 사이트(Reference) Data Structure : A Pseudocode Approach with C Data Structure and Algorithm in C++ 이번 글에서는 비선형(non-linear) 자료구조인 트리(Tree)에 대해서 알아보겠습니다. 나중에 그래프에 대해서도 글을 쓰겠지만, 트리는 그래프에 속하는 자료구조입니다. 트리는 위 그림과 같이 생겼습니다. 트리는 노드(node)라고 불리는 요소들과 방향성이 있는 브랜치(branch)로 구성되어 있으며, 이 브랜치는 각 노드를 연결시켜 주는 역할을 합니다. 노드와 연결된 브랜치의 수는 노드의 degree(차수)라고 하며, 만약 노드를 향하는 브랜치라면 indegree, 노드에서 나오는 브랜치라면 outdegree.. 2020. 9. 3.
[자료구조] Queue(큐), Deque(덱) - 참조 문헌 및 사이트(Reference) Data Structure : A Pseudocode Approach with C Data Structure and Algorithm in C++ 이번 글에서는 선형 리스트이며, 한쪽에서는 데이터의 삽입이 이루어지고, 반대편쪽에서는 데이터의 삭제만 이루어지는 큐(Queue)와 양쪽 끝에서 모두 데이터의 삽입과 삭제가 가능한 덱(Double-End Queue)에 대해서 알아보겠습니다. Queue 큐 우선 큐부터 알아보도록 하겠습니다. 큐의 기본 컨셉은 위 그림과 같습니다. rear라는 한쪽 끝에서는 insert만 이루어지고, front라는 다른 한쪽 끝에서는 remove만 이루어집니다. 즉, 스택과는 반대로 FIFO(First in First out) 구조를 가.. 2020. 9. 1.
[자료구조] Stack(스택) - 참조 문헌 및 사이트(Reference) Data Structure : A Pseudocode Approach with C Data Structure and Algorithm in C++ 코드는 깃허브를 참조 : https://github.com/junstar92/DataStructure_Algorithm/tree/master/Data_Structure/Stack 스택(Stack)은 데이터의 삽입과 삭제가 오로지 top이라고 불리는 한쪽 끝에서 이루어지는 선형 리스트이며, LIFO(Last In First Out)의 특성을 갖는 자료구조로 나중에 들어온 데이터가 먼저 삭제됩니다. 아래와 같은 구조를 갖습니다. 스택은 배열과 리스트로 구현이 가능하며, 보통 맨 위에 있는 값만 알 수 있으며 맨 위에 새.. 2020. 8. 31.
[자료구조] 리스트(List), 배열(Array), 연결리스트(Linked List) - 참조 문헌 및 사이트(Reference) Data Structure : A Pseudocode Approach with C Data Structure and Algorithm in C++ 리스트 List 리스트는 자료구조(Data Structure)에서 기본이 되는 추상자료형(Abstract Data Type:ADT)으로, sequential한 data의 집합입니다. 즉, 선형적으로 순서가 있는(ordered) 값들의 집합이라고 보면 되겠습니다. 여기서 ADT란 간단하게 data의 정의와 그 data에 대한 연산이 정의된 가상의 자료구조를 의미하며, 그 연산에는 data의 삽입/삭제/탐색 등이 있습니다. 리스트는 배열(Array)이나 연결리스트(Linked List)로 구현이 가능합니다. 배열은 프로.. 2020. 8. 28.
​

티스토리툴바