Data Structure

자바 [JAVA] - 트리(Tree), 이진 트리(Binary Tree)

1. 트리(Tree)란? 자바의 Collection Framework를 학습하며 여러 자료 구조에 대해 이미 살펴본 바 있다. ArrayList, LinkedList, Map, Stack, Queue 등의 내용들이 있었. Map은 조금 다르지만 이 자료 구조들은 기본적으로 공통점이 있다. 바로 선형(Linear) 자료 구조라는 점이다. 선형(Linear) 자료 구조란 무엇인가? 구조에 저장될 데이터들이 순차적으로 저장되는 형태를 의미한다. 간단히 배열을 생각해보면 메모리 공간에 순서대로 나열해서 저장하는 것을 알 수 있다. ArrayList는 배열을 기반으로 하며, LinkedList는 각 데이터를 저장한 노드들이 논리적인 선형으로 이어진 형태인 것이다. Stack, Queue 또한 이러한 구조를 바탕으..

자바 [JAVA] - 힙과 우선순위 큐(Heap, Priority Queue)

해당 포스팅은 '힙'과 '우선순위 큐'에 대한 학습 자료다. 힙과 우선순위 큐를 한 포스팅에 담은 이유는 '우선순위 큐'가 바로 힙 자료구조를 이용하여 구현되기 때문이다. 자료 구조 힙(Heap)이란? 힙은 '최솟값 또는 최댓값을 빠르게 찾아내기 위해 완전이진트리 형태로 만들어진 자료구조'다. 위 문장에서 중요한 키워드 3가지가 있다. 바로 '최솟값 또는 최댓값' , '빠르게', '완전이진트리' 이다. 일단 이 키워드를 이해하기 위해서는 '완전이진트리'를 이해해야 한다. 기본적으로 트리(tree)란 무엇인가? 위와같은 구조를 Tree 구조라고 한다. 위 그림을 거꾸로 보면 나무같이 생겨서 tree구조라고 한다. 여기서 Tree 구조의 각 명칭을 살펴보면 다음과 같다. 부모 노드(parent node) :..

자바 [JAVA] - 그래프(Graph)

그래프란? 객체 사이의 연결 관계를 표현할 수 있는 Cyclic한 자료구조이다. 그래프는 인접행렬(AdjacencyMatrix)과 인접리스트(AdjacencyList)로 표현할 수 있다. 그래프는 정점(Vertex)과 그 사이를 잇는 간선(Edge)으로 이루어진다. G = (V, E)는 정점의 집합 V와 간선의 집합 E라고 할 때, 그래프 G는 V와 E의 집합 (V, E)라는 뜻이다. V(G)는 그래프 G의 정점 집합이고, E(G)는 그래프 G의 간선 집합이다. 간선은 (정점 v, 정점 w)형식이다. 예시) V(G) = {1, 2, 3, 4, 5} => 정접 집합 E(G) = {(1, 2), (3, 1), (3, 2), (4, 1), (5, 2), (5, 4)} => 간선 집 이때, 정점의 위치 정보나 ..

자바[JAVA] - Queue와 Deque

Deque를 알기 위해선 Queue에 대한 이해가 필요하기 때문에 같이 설명 Queue Interface Queue 인터페이스는 선입선출 FIFO(First In First Out)구조를 가진 자료구조다. 시간복잡도는 enqueue O(1) , dequeue O(1) 이며 활용 예시는 Cache구현, 프로세스 관리, 너비우선탐색(BFS) 등이 있다. 먼저 들어온 요소가 먼저 나가는 방식으로, 메소드는 총 6가지가 존재한다. 요소를 추가하는 메소드는 add()와 offer(), 요소를 제거하는 메소드는 remove()와 poll() , 맨 처음 요소를 반환하는 메소드는 peek(), element()가 있다. 그리고 주로 offer(), poll(), peek()을 사용한다. 왜냐하면, 이들 외의 나머지 ..