IT Hyeon's study IT Hyeon's study

이진 탐색 트리는 Binary Search Tree 즉, BST라고 한다각 노드의 자식 노드가 최대 2개인 트리 사용하는 이유는 데이터의 효율적인 정렬검색삽입삭제  모두 가능하게 하는 구조가 있다  자세한 이유 1. 정렬된 데이터의 효율적인 검색 평균 O(log n) 시간 복잡도로 데이터를 검색할 수 있다 2. 동적 데이터 집합 관리데이터가 계속 추가, 삭제되는 동적인 환경에서도 효과적삽입, 삭제도 O(log n)의 시간 복잡도를 가진다 3. 중위 순회를 통한 정렬된 데이터 접근중위순회는 항상 정렬된 순서로 데이터에 접근하게 해준다 정렬된 데이터를 순차적으로 처리할때 유용하다 4. 범위 탐색 및 순차 접근 용이특정 범위의 데이터를 빠르게 검색범위 내의 데이터를 효율적으로 순차적으로 탐색하는데 적합하다 5..

위 이미지를 보면 왼쪽은 그래프이고 오른쪽 세개는 왼쪽에 대한 신장트리이다  그래프 상에서 모든 노드가 사이클 없이 연결된 부분 그래프를 뜻함이러한 부분 그래프는 여러개 존재 할 수 있다여러 개의 부분 그래프 중 모든 정점이 최소 간선의 합으로 연결된 부분 그래프모든 정점을 포함하는 트리그럼 왜? 트리라고 할까-> 트리는 그래프 중에서 특수한 경우에 해당하는 자료구조이다즉, 사이클이 존재하지 않는 방향 그래프이다  사이클?  : 순환 사이클이 존재하는 그래프를 만약 dfs 탐색을 한다고 하자 그러면 계속 무한으로 탐색을 할 것이다 하지만 사이클이 존재하지 않는다면 모두 다 탐색을 하면 끝나겠죠!  최소 신장 트리 (MST, Minimum Spanning Tree)신장 트리중에서 가중치 합이 가장 최소인 ..

말하기에 앞서 우선 그래프는 비선형 자료구조이다   비선형자료구조 데이터를 일렬로 구성하지 않고 자료 순서나 관계가 복잡한 자료구조 하나의 자료 뒤에 여러개의 자료가 존재할 수 있는 형태트리와 그래프가 대표적이고 계층적 구조를 나타내기에 적절하다💡그래프란? 여러 개의 노드(node)와 이 노드들을 연결하는 간선(edge) 으로 관계를 표현한 자료구조이다.정확히는 정점(vertex) 간의 관계를 표현한 조직도 이다. 구성 요소노드(node) : 정점(Vertice) 라고도 하는 데이터가 저장되는 그래프의 기본 원소간선(edge) : 노드 간의 관계를 나타내는 선인접 정점(adjacent Vertex) : 간선에 의해 직접 연결되어 있는 정점 ex) 1 노드 기준으로 인접 정점은 0, 2, 3 이다단순 경..

힙(Heap) 이란? 힙은 데이터에서 최댓값과 최솟값을 빠르게 찾기 위해 고안된 Complete Binary Tree(완전 이진 트리) 이다 우선순위 큐를 위해 만들어진 자료구조 이기도 하다최댓값과 최솟값을 빠르게 찾아내도록 만들어진 자료구조반정렬 성태를 유지 -> 부무 노드의 키 값이 자식 노드의 키 값보다 항상 크거나 작다이진 탐색 트리와는 다르게 중복된 값이 허용 된다 종류최대 힙 (max heap)부모 노드의 키 값이 자식 노드의 키 값보다 크거나 같은 완전 이진 트리key(부모 노드) >= key(자식 노드)최소 힙 (min heap)부모 노드의 키 값이 자식 노드의 키 값보다 작거나 같은 완전 이진 트리key(부모 노드)  💡 왜 사용할까?최솟값이나 최댓값을 찾기 위해 배열을 사용하면 반복문..

- 말하기에 앞서 Queue는 interface 형태로 Collection 클래스를 상속하고 있다 - 자료구조 중에서 선형구조인 큐는 일반 큐와 우선순위 큐로 나뉘어진다  선형구조(Linear Structure), 큐(Queue)💡 선형 구조 - 데이터를 저장하기 위한 기본적인 형태로 데이터가 일렬로 나열 되어 있을 뿐만 아니라 데이터 간에 순서가 있고 논리적으로 이어져 있는 구조를 의미한다 💡 큐 - 큐는 선입선출의 특성을 가지고 있다큐에 대해서 좀 더 자세하게 알고 싶으면 아래 포스팅을 확인하면 된다  https://hyeonni.tistory.com/24 Queue란? from javaQueue 란?  Queue란? 사전적 의미로는 대기줄이다이러한 사전 적 의미 처럼 queue는 차례대로 처리된..

Deque란?- Double-Ended Queue의 줄임말로 큐의 양쪽에서 데이터를 넣고 뺄 수 있는 형태의 자료구조를 의미한다- 다시 말해 기존의 Queue는 한쪽에서 데이터를 넣고 다른 한쪽에서 데이터를 빼는 형태인데 Deque는 둘다 데이터를 넣고 뺄 수 있다는 것이다- Queue와 Stack 을 합쳐 놓은 자료구조라고 생각 하면 된다  - Deque를 이해하려면 일단 Queue를 알아야 한다 - 아래는 Queue를 정리한 포스팅이다  https://hyeonni.tistory.com/24 Queue란? from javaQueue 란?  Queue란? 사전적 의미로는 대기줄이다이러한 사전 적 의미 처럼 queue는 차례대로 처리된다큐는 후입선출(LIFO)인 스택과 다르게 선입선출(FIFO)의 형태를..

Queue 란?  Queue란? 사전적 의미로는 대기줄이다이러한 사전 적 의미 처럼 queue는 차례대로 처리된다큐는 후입선출(LIFO)인 스택과 다르게 선입선출(FIFO)의 형태를 가진다선입선출 말 그대로 먼저 들어오면 먼저 나가는 구조이다 특징- FIFO (First In First Out) 구조 - 큐의 한 쪽 끝은 front (앞)로 정하여 삭제 연산만 수행- 다른 한 쪽 끝은 rear 로 정하여 삽입 연산만 수행- 예를 들어 빨대 형태이다 한쪽으로 들어오고 다른 한쪽으로 나간다  사용법, 예제import java.util.Queue;import java.util.LinkedList;Queue queue = new LinkedList(); // T 타입 queue 선언- 일단 java.util.Q..