'Data Structure' 카테고리의 글 목록

[Data Structure] 그래프와 트리

Data Structure 2022. 3. 14. 09:13

그래프의 특징 노드와 노드를 연결하는 간선을 하나로 모아놓은 자료구조 방향 그래프 (Directed) 와 무방향 그래프 (Undirected) 로 나뉜다. 사이클 (Cycle) 이 있을 수도 있고, 자체 간선 (Self-loop) 도 있을 수 있다. 루트 노드, 부모-자식의 개념이 없다. 순회 방법은 BFS, DFS가 있다. 간선의 수가 제한되어있지 않다. 그래프 용어 정점 (vertex) : 위치 (node) 간선 (edge) : 위치 간의 관계. 노드를 연결하는 선 (link) 인접 정점 (adjacent vertex) : 간선에 의해 직접 연결된 정점 정점의 차수 (degree) : 무방향 그래프에서 하나의 정점에 인접한 정점의 수 진입 차수 (in-degree) : 방향 그래프에서 정점으로 들어오..

[Data Structure] 큐 (Queue)

Data Structure 2022. 2. 13. 19:08

안녕하세요! 이번에는 Queue에 대해서 포스팅해보려고 합니다! 1. Queue란? Queue는 한쪽 끝에서만 원소의 추가가 이루어지고, 다른 한쪽 끝에서만 원소의 제거가 이루어지는 순차화된 리스트입니다. 원소의 추가가 이루어지는 쪽을 rear, 원소의 제거가 이루어지는 쪽을 front라고 합니다. 즉, rear로 원소가 들어오고, front로 원소가 나간다고 생각하시면 됩니다. Queue는 가장 먼저 들어온 원소가 가장 먼저 나오기 때문에 FIFO (First-In-First-Out) 구조입니다. Queue 또한 Stack과 마찬가지로 원소의 추가/제거 시간복잡도는 O(1)입니다. 제일 앞과 뒤에 있는 원소를 확인하는 시간복잡도 또한 O(1)입니다. 그리고 Queue의 제일 앞과 뒤를 제외한 나머지 원..

[Data Structure] 스택 (Stack)

Data Structure 2022. 2. 9. 02:34

안녕하세요! 오늘은 Stack에 대해서 포스팅해보려고 합니다! 1. Stack이란? Stack은 값을 한쪽 끝에서만 추가하거나 삭제할 수 있는 것으로, LIFO (Last-In-First-Out) 구조입니다. 새로운 원소를 아래부터 차례대로 하나씩 쌓는 것으로, 원소를 지울 때에는 제일 위에 있는 원소가 제일 먼저 지워집니다. 그렇기 때문에 가장 나중에 들어온 원소가 먼저 나가겠죠? 그래서 Stack은 LIFO 구조입니다. 제일 위에 있는 원소를 top element, 제일 아래에 있는 원소를 bottom element라고 합니다. 즉, Stack은 top의 위치에서만 원소의 삽입과 제거가 이루어지는 순차화된 리스트입니다. Stack이 뭔지 알아봤으니, 이제 Stack의 성질에 대해서 알아보도록 할게요!..

[Data Structure] Linked List (Feat. Array)

Data Structure 2022. 1. 12. 23:44

배열 (Array)이란? 원소들이 메모리에 연속적으로 저장된 자료구조 인덱스로 배열의 원소를 바로 찾을 수 있다. 배열의 특징 O(1)에 n번째 원소를 확인하고, 변경할 수 있다. 추가적으로 소모되는 메모리의 양, 즉 오버헤드가 거의 없다. 메모리 상에 데이터들이 붙어있기 때문에, Cache hit rate가 높다. 메모리 상에 연속적으로 구간을 잡아야하므로, 할당에 다소 제약이 있다. 배열의 첫번째, 마지막 인덱스 이외의 인덱스에 새롭게 원소를 추가하거나 제거할 때, 원소들을 새롭게 배치해야하기 때문. ㅤ 연결 리스트 (Linked List)란? 메모리 상에 연속적이지 않은 데이터들을 링크로 연결해놓은 자료구조 연결 리스트는 노드로 이루어져있는데, 노드는 data (데이터), link (링크)로 이루어..

ABOUT ME

🍎 🍎

티스토리툴바