DataStructure 썸네일형 리스트형 Heap 알아보기 Heap이란?완전 이진 트리(Complete Binary Tree)를 기본으로 한 자료구조로, 부모 노드와 자식 노드 간에 특정한 순서가 존재하는 자료구조입니다. 최대 힙(Max Heap)은 부모 노드가 자식 노드보다 크거나 같고, 최소 힙(Min Heap)은 부모 노드가 자식 노드보다 작거나 같습니다.특징완전 이진 트리 구조를 가짐 (마지막 레벨을 제외한 모든 레벨이 완전히 채워져 있어야 함)배열로 구현 가능 (왼쪽 자식: 2i + 1, 오른쪽 자식: 2i + 2, 부모: (i-1)/2)우선순위 큐 구현에 주로 사용됨힙 정렬(Heap Sort)의 기반이 되는 자료구조시간 복잡도에서의 Heap데이터의 삽입, 삭제, 탐색을 기준으로 살펴보겠습니다.1. 삽입 (add/offer)Java의 PriorityQu.. 더보기 [5] Tree Set 의 개념과 여러 method 들의 시간 복잡도. TreeSet이란? TreeSet은 내부적으로 TreeMap을 사용하는 Set 인터페이스의 구현체입니다. 중복을 허용하지 않고, 데이터가 정렬된 상태로 저장되는 특징을 가지고 있습니다.특징데이터가 정렬된 상태로 저장됨 (오름차순)중복 데이터 허용하지 않음Red-Black Tree 기반의 이진 탐색 트리로 구현됨null 값을 저장할 수 없음시간 복잡도에서의 TreeSet데이터의 조회, 추가, 삭제, 수정을 기준으로 살펴보겠습니다.1. 조회TreeSet의 데이터들은 이진 탐색 트리 구조로 저장되어 있어, 특정 데이터를 찾을 때 O(log N)의 시간이 소요됩니다. Java Collections의 contains 메서드를 보면 다음과 같습니다:public boolean contains(Object o) { .. 더보기 [4] Tree의 개념 및 Tree의 종류별 연산 시간 Tree Data Structure1. 개념Tree는 순환하지 않고 연결된 그래프로, 임의의 두 노드 사이에 하나의 경로만 존재하는 계층적 자료구조입니다.2. 특징루트 노드: 트리의 시작점이 되는 최상위 노드부모-자식 관계: 두 노드가 간선으로 연결되었을 때, 위쪽이 부모, 아래쪽이 자식단순 경로: 두 노드간 경로가 오직 하나만 존재사이클 없음: 순환하지 않는 그래프노드의 개수 = 간선의 개수 + 13. 트리의 종류3.1 이진 트리 (Binary Tree)각 노드가 최대 2개의 자식을 가지는 트리종류:완전 이진 트리: 마지막 레벨을 제외하고 모든 레벨이 채워져 있는 트리포화 이진 트리: 모든 내부 노드가 2개의 자식 노드를 가지는 트리 (리프노드 제외)편향 트리: 한쪽으로만 자식을 가지는 트리균형 트리:.. 더보기 [3] Graph 의 개념과 인접 행렬, 인접 리스트 판단 기준 Graph 란?그래프(Graph)는 정점(Vertex)들의 집합과 이들을 연결하는 간선(Edge)들의 집합으로 구성된 자료구조grpah 를 표현하기 위해서는 대표적으로 두가지 방법이 있습니다. 인접 리스트인접 행렬각각의 Vertex와 연결되어있는 Vertex를 표현하기 위한 방법이고, 두 방식의 구현 방법과 상황별로 어떤 상황에서 어떤 구현방식을 선택해야 하는지 알아볼게요!1. 인접 리스트해당 코드는 다음과 같아요import java.util.LinkedList;public class Graph { private int V; // 정점의 개수 private LinkedList[] adj; // 인접 리스트 // 생성자 @SuppressWarnings("unchecked") .. 더보기 [2] Linked List 직접 구현해보기 -java- Double Linked List 방식을 사용구현할 methodAdd 메서드:addFirst(E element) - 맨 앞에 추가addLast(E element) - 맨 뒤에 추가add(int index, E element) - 지정 위치에 추가Remove 메서드:removeFirst() - 첫 노드 삭제removeLast() - 마지막 노드 삭제remove(int index) - 인덱스로 삭제remove(Object o) - 특정 값을 가진 첫 노드 삭제 ( 커스텀 해도 좋음)get(int index) - 노드 탐색의 기본contains(Object o) - 전체 순회size() - 리스트 관리의 기본clear() - 전체 노드 삭제 처리package linkedList;import java.util... 더보기 [1] Linked List 의 개념과 java Collection 살펴보기 Linked List란?일련의 Node(여기서 Node란, Data와 Pointer를 가지고 있는 기본 단위)들이 다음 노드(또는 이전 노드)를 가리키는 방식으로 서로를 참조하는 선형 자료구조.특징실제로 메모리가 연속하는 건 아님(배열과의 차이). (배열은 처음부터 정적으로 메모리 크기를 할당하고, 그 속에서 해당 자료형의 크기 * N으로 N번째 메모리에 한 번에 접근 가능함) -> 메모리가 각각 독립적인 공간에 존재하고, pointer로 위치를 참조함.동적인 크기를 가짐. 노드의 추가 삭제로, 해당 자료구조의 크기가 동적으로 변함.시간 복잡도에서의 Linked List데이터의 조회, 추가, 삭제, 수정을 기준1. 조회Linked List의 데이터들은 특정 순서를 가지지 않기 때문에, 특정 데이터를 찾기.. 더보기 이전 1 다음
