Data Structure (5) Graph (그래프) 📌그래프란 : 실제 세계의 현상이나 사물을 정점(Vertex)(또는 노드(Node))와 간선(Edge)로 표현하기 위해 사용 📌용어 노드 Node: =정점(Vertex),그래프에서의 위치, 간선 Edge: 노드들을 연결한 선. 위치 간의 관계를 표시 (link, branch라고 표현하기도 함.) 인접 정점 Adjacent Vertex: 간선으로 직접 연결되어 있는 정점(노드) +기타 정점의 차수 Degree: 무방향 그래프에서 하나의 정점에 인접한 정점의 수 진입 차수 In-Degree: 방향그래프에서 외부에서 오는 간선의 수 진출 차수 Out-Degree: 방향그래프에서 외부로 향하는 간선의 수 경로 길이 Path Length: 경로를 구성하기 위해 사용된 간선의 수 단순 경로 Simple Path: .. Data Structure - Heap (힙) | Python 구현 Heap은 이진트리의 변형된 자료구조라고 할 수 있는데, 최댓값 최솟값을 빠르게 찾아야 할 때 많이 사용된다. 📌Heap : 데이터에서 최대값과 최소값을 빠르게 찾기 위해 고안된 완전 이진 트리 (Complete Binary Tree) 트리를 기반으로 변형된 구조! 완전 이진 트리(Complete Binary Tree): 노드를 삽입할 때 최하단 왼쪽 노드부터 차례대로 삽입하는 트리 힙을 사용하는 이유 우선순위 큐와 같이 최댓값 또는 최솟값을 빠르게 찾아야 하는 자료구조 및 알고리즘 구현 등에 활용됨. array vs. heap : 배열에서 최댓값/최솟값을 탐색하는데 걸리는 시간복잡도는 $O(n)$, 힙에서 최댓값/최솟값을 찾는데 걸리는 시간복잡도는 $O(log n)$ 📌Heap 구조 최대값을 구하기 위.. Data Structure (3) Hash Table (해시 테이블) 📌Hash 구조 Hash Table: key에 data(value)를 저장하는 데이터 구조 ex) Python의 Dictionary : key와 value를 가지고 있는 데이터 타입으로, key값을 통해 value를 바로 꺼낼 수 있음 (Python에서는 hash구현 없이 바로 dictionary 사용하면 됨) 보통 미리 hash table의 크기만큼 배열 생성 후 사용 (공간과 탐색 시간을 맞바꾸는 기법) 📌용어 hash: random 값을 고정 길이로 변환하는 것 (단방향 암호화 기법으로, 해시 알고리즘을 이용하여 고정된 길이의 암호화된 문자열로 변환) hash table: hashing function: key에 대해 산술 연산을 이용해 데이터 위치를 찾을 수 있는 함수, 즉 임이이 길이의 데이터를.. Data Structure (2) Tree (트리) 📌트리 node와 branch를 이용해서, cycle을 이루지 않도록 구성한 데이터 구조 트리 중 binary tree(이진 트리) 형태의 구조는 탐색(search) 알고리즘 구현에 많이 사용됨 In computer science, a tree is a widely used abstract data type that simulates a hierarchical tree structure, with a root value and subtrees of children with a parent node, represented as a set of linked nodes. A tree data structure can be defined recursively as a collection of nodes (sta.. Data Structure(1) Linked List (연결 리스트) 📌Linked List (연결 리스트) linked list는 떨어진 곳에 존재하는 데이터들을 포인터로 '연결'해서 관리하는 data structure 장점(배열의 단점 극복): 비연속적 데이터를 포인터로 연결하기 때문에 메모리를 미리 할당받을 필요가 없음 배열은 연속적으로 연결된 공간에 데이터를 나열하기 때문에 특정한 연결된 공간을 미리 할당받아야 함 단점: 각 데이터마다 다음 노드를 가리키는 주소(포인터)도 같이 저장해야하므로 저장공간 효율↓ 첫 노드(head)부터 쭈우우-욱 검색해야 해서 연결 정보를 찾는 시간이 필요하여 데이터에 접근하는데에 시간이 소요 (배열은 index로 바로 접근 가능) 중간에 데이터를 추가/삭제할 때, 추가적 작업이 필요 📌일반(간단한) linked list .. 이전 1 다음
