Java/자료구조

[Java DataStructure] Priority Queue(우선순위 큐)란?

Priority Queue(우선순위 큐)란? 일반적으로 큐는 FIFO(First In First Out)의 구조로 동작하지만, 우선순위 큐는 데이터의 우선순위를 먼저 결정하고 그 순서로 나가는 자료구조이다. Priority Queue의 특징 1. 우선순위를 기준으로 데이터를 꺼낸다. 2. 내부 구조가 힙으로 구성되어 있어서 시간 복잡도가 O(NlogN)이다. 3. 우선순위를 기준으로 루트 노드를 정하고 꺼낼때 루트 노드가 나온다. 4. Comparator 인터페이스를 오버라이딩하여 우선순위를 재정의할 수 있다. Priority Queue 객체 선언 import java.util.PriorityQueue; // 오름차순 PriorityQueue pq = new PriorityQueue(); // 내림차순 ..

[Java DataStructure] Graph

Graph란? 여러개의 점들이 서로 복잡하게 연결되어 있는 관계를 표현한 자료구조이다. Java의 Collections를 사용하여 프로그래밍 방식으로 그래프를 나타낼 수 있다. 그래프를 생성하는 가장 일반적인 방법은 인접 행렬 또는 인접 목록과 같은 그래프 표현 중 하나를 사용하는 것 구조 및 용어 정점(vertex) : 정점 (vertex): 노드(node)라고도 하며 데이터가 저장되는 그래프의 기본 원소 간선 (edge): 정점 간의 관계 (정점을 이어주는 선) 인접 정점 (adjacent vertex): 하나의 정점에서 간선에 의해 직접 연결되어 있는 정점 가중치 그래프 (weighted Graph): 연결의 강도가 얼마나 되는지 적혀져 있는 그래프 비가중치 그래프 (unweighted Graph)..

[Java DataStructure] Tree

Tree란? 하나 이상의 데이터에 무방향으로 연결된 계층적 비선형 자료구조이다. 구조 및 용어 루트(root) : 트리 구조 중 최상위에 존재하는 노드 (1을 가리킴) 노드(node) : 트리에서 각각의 구성 요소 레벨(level) : 트리에서 각각의 층을 나타내는 단어(루트 노드 : 0) 형제 노드(sibling) : 같은 레벨의 노드 간선(edge) : 노드와 노드를 연결하는 선 부모 노드(parent node) : 한 노드를 기준으로 바로 상위에 존재하는 노드 자식 노드(child node) : 한 노드를 기준으로 바로 하위에 존재하는 노드 높이(heigh) : 트리 중 최고 레벨 리프(Leaf) : 트리 구조의 끝 지점이고, 자식 노드가 없는 노드 Binary Search Tree 이진 트리(Bi..

[Java DataStructure] Stack&Queue

자료구조란? 데이터를 체계적으로 저장하여 데이터를 활용을 유리하게 한다. 무수한 상황에서 데이터를 효율적으로 다룰 수 있는 방법을 모두 모아, 자료구조라는 이름을 붙였다. 특정한 상황에 놓인 문제를 해결하는 데에 특화되어 있고, 적합한 자료구조를 적용하여 빠르고 정확하게 문제를 해결할 수 있다. Stack 데이터(data)를 순서대로 쌓고, 하나씩 넣고 뺄 수 있으며, 입출력 방향이 하나로 같다. Stack 자료구조의 정책을 LIFO(Last In First Out) 혹은 FILO(First In Last Out)이라고 부르기도 한다. Stack에 데이터를 넣는 것을 'PUSH', 데이터를 꺼내는 것을 'POP'이라고 한다. 실사용의 예시로, 브라우저의 뒤로가기, 앞으로가기 기능을 구현할 때 사용한다. ..