트라이(Trie)란?트라이는 문자열을 저장하고 효율적으로 탐색하기 위한 트리형태의 자료구조이다.노드의 계층 구조로 구성되며, 각 노드가 문자열의 한 문자 또는 키의 일부를 나타낸다.문자열을 저장할 때, 공통된 접두사는 공유하도록 설계되어 공간 효율성이 높다.   트라이의 구조 루트 노드: 트리의 시작점으로, 문자열 집합에 공통된 접두사가 없는 최상위 노드.자식 노드: 한 문자씩 연결되며, 문자열의 경로를 형성.종료 표시: 단어가 끝날 때 해당 노드에 플래그 또는 값을 설정. (위 그림에서는 빨간 원이 그 역할을 함) 예시) 문자열 ["cat", "car", "dog"]를 트라이에 저장한 경우 (root) / \ c d / \ \ a..

B트리 (B-Tree)정의B트리는 자가 균형 다진 트리(M-ary tree)이다. 즉, 모든 리프의 노드가 같은 depth 를 가지며, 내부 노드가 여러 자식을 가질 수 있다.m은 B트리의 차수이다. 각 노드는 최대 m개의 자식을 가질 수 있다.ㄴ 3차 B트리라고 한다면, m은 3이고 최대 3개의 자식을 가질 수 있다는 것.  구조와 속성루트 노드: (트리가 비어있지 않을 때) 2개 이상, m개 이하의 자식을 가진다. 내부 노드: ⌈m/2⌉개 이상, m개 이하의  자식을 가진다.리프노드: 모든 리프 노드는 동일한 레벨에 있다. 균형 유지노드의 키: 각 노드는 ⌈m/2⌉개 이상, m-1개 이하의 키를 가진다. 정렬된 상태를 유지하고 있어 효율적 탐색이 가능하다.  장단점장점자동으로 균형을 유지하여 검색, ..

완전이진트리(Complete Binary Tree)란?완전이진트리는 이진트리의 일종으로 최대 2개의 자식노드를 가질 수 있다.마지막 레벨을 제외한 모든 레벨이 꽉 차있어야 한다.마지막 레벨은 왼쪽부터 채워져 있어야 한다.완전 이진트리의 예올바른 예틀린 예마지막 레벨을 제외한 모든 레벨이 꽉 채워져 있음.마지막 레벨은 왼쪽부터 채워져 있음.마지막 레벨을 제외한 모든 레벨이 꽉 채워져 있음.하지만 노드 2의 오른쪽 자식이 비워져있음.  완전이진트리 특성노드의 개수: 레벨 h에 있는 노드의 최대 개수는 2^h이다.예를 들어, 루트 레벨(레벨 0)에는 최대 1개의 노드가 있고, 레벨 1에는 최대 2개의 노드, 레벨 2에는 최대 4개의 노드가 있을 수 있다.트리의 높이: 노드의 개수가 n인 완전 이진 트리의 ..

이진탐색트리란?이진탐색트리(Binary Search Tree, BST)는 이진 트리의 일종으로 데이터를 효율적으로 저장, 검색, 삽입 및 삭제할 수 있도록 설계된 자료구조이다. 이진탐색트리는 다음과 같은 특징을 가지고 있다.각 노드가 최대 두개의 자식 노드를 가지고 있다.왼쪽 서브트리의 모든 노드의 값은 루트 노드의 값보다 작다.오른쪽 서브트리의 모든 노드의 값은 루트 노드의 값보다 크다.중복 요소는 허용하지 않는다.왼쪽 및 오른쪽 서브트리도 각각 이진탐색트리여야 한다.  이진탐색트리의 연산탐색 (Search)root 노드부터 탐색 시작현재 위치의 값과 비교하여 찾고자 하는 key 가 작으면 왼쪽 서브트리로, 오른쪽 서브트리로 재귀.일치하는 값을 찾을 때까지 절차 반복.리프노드에 도달할 때 까지 검색 값..

트리(tree)란?트리는 계층적 구조를 가지는 비선형 자료구조이다. 순환(Cycle)이 없는 연결 구조이다.트리는 루트(Root) 노드에서 시작하여, 자식(Child) 노드로 연결되는 노드들로 구성된다.각 노드는 자식 노드를 가질 수 있으며, 노드 간 연결은 부모-자식 관계를 나타낸다. 또한, 부모 노드는 한개만 가질 수 있다.노드의 개수가 N이면, 간선의 수는 항상 N-1개이다.   트리의 구성  루트(Root): 트리의 최상단 노드이다. 트리는 루트 노드에서 시작된다.노드(Node): 트리의 각 요소를 나타낸다. 각 노드는 데이터와 자식 노드에 대한 포인터를 포함한다.부모(Parent): 특정 노드의 바로 위에 있는 노드이다.자식(Child): 특정 노드 바로 아래에 있는 노드이다.리프(Leaf): ..

해시(Hash)란?해시는 임의의 크기를 가진 데이터를 고정된 크기의 값으로 변환하는 함수 또는 알고리즘이다.이 과정을 통해 생성된 고정 크기의 값을 '해시 값'이라고 한다.  해시 관련 용어 정리해시 (Hash)임의의 값을 고정 길이로 변환해시 테이블 (Hash Table)키 값의 연산에 의해 직접 접근 가능한 데이터 구조해시 함수 (Hash Function)Key에 대해 산술 연산을 이용해 데이터 위치를 찾을 수 있는 함수해시 값 (Hash Value) / 해시 주소(Hash Address)Key를 해시 함수로 연산해서 해시 값을 알아내고,이를 기반으로 해시 테이블에서 해당 Key에 대한 데이터를 일관성 있게 찾을 수 있음해시 버킷 (Hash Bucket) / 해시 슬롯 (Hash Slot)버킷 : 각..

큐란?큐는 FIFO(First In First Out) 원칙을 따르는 선형 데이터 구조이다. 즉, 삽입된 순서대로 삭제가 처리된다.   큐 연산 주요 연산인 enqueue, dequeue 외에도 peek(front), empty, size 등의 연산이 있다.enqueue: 큐의 뒤(rear) 끝에 새로운 데이터를 추가하는 연산dequeue: 큐의 앞(front) 끝에서 데이터를 제거하고 반환하는 연산front 또는 peek: 큐의 앞에 있는 데이터를 제거하지 않고 반환하는 연산empty: 큐가 비어 있는지 확인하는 연산size: 큐에 있는 데이터의 개수를 반환하는 연산   큐 구현큐도 스택과 마찬가지로 배열이나 연결 리스트를 사용하여 구현할 수 있다.데이터 크기 예측 가능한 경우         ->  ..

스택이란?LIFO(Last In First Out) 구조를 갖는 자료구조를 말한다. 즉, 나중에 삽입된 데이터가 먼저 삭제되는 구조이다.데이터를 일시적으로 저장할 때 매우 유용한 선형 데이터 구조이다.   스택 연산스택에는 push, pop과 같은 주요 연산과 peek(top), empty, size 등의 연산을 가질 수 있다. push: 스택의 맨 위에 데이터를 삽입하는 연산pop: 스택의 맨 위에 있는 데이터를 삭제하고 반환하는 연산peek 또는 top: 스택의 맨 위에 있는 데이터를 삭제하지 않고 반환하는 연산empty: 스택이 비어 있는지를 확인하는 연산size: 스택에 있는 데이터의 개수를 반환하는 연산   구현스택은 배열이나 연결리스트를 사용하여 구현할 수 있다.데이터 크기 예측 가능한 경우 ..

배열(Array)배열은 동일한 데이터 타입의 요소들이 연속된 메모리 공간에 저장된 자료 구조이다.특징 : 배열 선언 시 크기가 고정된다.한번 결정된 크기는 변경할 수 없다.인덱스를 사용하여 요소에 빠르게 접근할 수 있으며, 인덱스는 0부터 시작한다.배열 안의 모든 요소가 동일한 데이터 타입을 가진다.연속된 메모리 공간에 할당 된다. Java에서 배열 다루기// 배열 만들기int[] arr1;// 배열 만들면서 크기 지정int[] arr2 = new int[5];// 배열 만들면서 크기+값 지정int[] arr3 = {1, 2, 3, 4, 5};// arr3 배열에서 index 0인 요소에 접근System.out.println(arr3[0]); // 1   Java의 Arrays 클래스Java에서 배열 자..