Computer Science/Data Structure4 Graph (그래프) ✅ Graph (그래프)란? 노드(node)와 간선(edge)으로 이루어진 자료 구조 Graph 종류 그래프는 방향성에 따라 무방향 그래프(Undirected Graph), 방향 그래프(Directed Graph)로 나눌 수 있다. 1. 무방향 그래프 (Undirected Graph) 간선을 통해서 양 방향으로 갈 수 있다. 정점 A와 정점B를 연결하는 간선은 (A, B)와 같이 정점의 쌍으로 표현한다. (A, B) = (B, A) 동일 2. 방향 그래프 (Directed Graph) 간선에 방향성이 존재한다. A ➡ B로만 갈 수 있는 간선은 로 표현한다. 는 와 다름 Graph 용어 노드(node) 위치라는 개념 (node라고도 부름) 간선(edge) 위치 간의 관계 즉, 노드를 연결하는 선 인접 정.. 2021. 1. 24. Hash Table (해시 테이블) ✅ Hash Table (해시 테이블)란? 해시 테이블은 Key-Value로 데이터를 저장하는 자료구조 중 하나로 빠르게 데이터를 검색할 수 있는 자료구조다. 해시 테이블이 빠른 검색속도를 제공하는 이유는 내부적으로 배열(버킷)을 사용하여 데이터를 저장하기 때문이다. 해시 테이블은 각각의 Key에 해시함수를 적용해 배열의 고유한 index를 생성하고, 이 index를 활용해 값을 저장하거나 검색하게 된다. 해시 테이블(hash table) key-value를 넣으면 해시함수를 거쳐 인덱스로 변환 후 저장하는 자료구조 해시함수(hash function) key를 (저장소의) index로 바꾸는 함수 해싱(hashing) 해시함수를 통해 key를 index로 바꾸는 작업 해시값(hash value) inde.. 2021. 1. 23. Linked List (연결 리스트) ✅ Linked List (연결 리스트)란? 각 노드가 데이터와 링크를 가지고 한 줄로 연결되어 있는 방식으로 데이터를 저장하는 자료 구조 노드 Data : 값을 저장 Link : 다음 주소를 가리키는 공간 위 그림과 같이 노드는 Data를 저장하는 공간과 다음 주소를 가리키는 공간이 필요하다. 사용자가 입력하는 정보를 Data공간에 담고 노드가 추가될 때마다 Link를 통해 다음 노드와 연결하는 것이다! 좀더 자세히 알아보자! Linked List(연결리스트)는 노드로 연결되어있다고 했다. 하지만 각 노드는 연속된 공간에 저장되어 있지 않고 메모리의 여러 부분에 분포되어 있다. 그래서 각 노드에 다음 노드의 주소를 저장함으로써 다음 노드를 탐색할 수 있다. (예를 들면 전화를 하면 각 부서로 연결해주는.. 2021. 1. 22. Stack&Queue ✅ 자료 구조(Data Structure)란? 자료 구조 자료(Data)의 집합을 의미 자료에 대한 처리를 효율적으로 수행할 수 있도록 자료를 구분하여 정의 목적 자료를 더 효율적으로 저장하고, 관리하기 위해 사용 잘 선택된 자료구조는 실행시간을 단축시켜주거나 메모리 용량의 절약을 이끌어 낼 수 있다. ✅ 스택(Stack)이란? 스택(stack)이란 간단하게 말해 쌓아올린다는 것을 의미한다. 따라서 스택 자료구조는 쌓아 올린 형태의 자료구조를 뜻한다. 특징 같은 구조와 크기의 자료를 정해진 방향으로만 쌓을 수 있고, top으로 정한 곳을 통해서만 접근할 수 있다. 즉, 자료가 들어오고 나갈 수 있는 곳이 한 곳이고, 한 번에 하나의 데이터만 처리할 수 있다. 이를 LIFO(Last In, First Ou.. 2021. 1. 20. 이전 1 다음
