공부한 내용 기록하기 공부한 내용 기록하기

1. 트라이란?트라이(Trie)는 문자열 검색을 위한 트리 기반의 자료구조로, 문자 하나하나를 노드로 저장하여 문자열 전체를 구성하는 구조다. 주로 사전(Dictionary) 구조, 자동완성 기능, 접두사 검색 등에 사용된다.Trie는 공통 접두사를 공유함으로써 공간을 절약하고, 문자열 검색을 효율적으로 수행할 수 있다.2. 트라이의 구조루트(Root): 공통된 시작 지점을 의미하며, 일반적으로 빈 값노드(Node): 각 문자 하나를 표현간선(Edge): 부모 → 자식 문자로의 연결끝 표시(End Flag): 해당 노드가 문자열의 끝을 나타내는 플래그예: "cat", "car", "dog" (root) / \ c d / \ a ..

1. 맵이란?맵(Map)은 키(Key)와 값(Value)의 쌍으로 데이터를 저장하는 자료구조다. 각 키는 고유하며, 이를 통해 해당 값에 빠르게 접근할 수 있다. 자바에서는 HashMap, TreeMap, LinkedHashMap 등 다양한 구현체가 존재하며, 대부분 O(1) 또는 O(log n)의 빠른 조회 성능을 제공한다.2. 맵의 특징키는 중복 불가, 값은 중복 가능키를 통해 값을 빠르게 조회 가능키의 해시 함수를 기반으로 내부적으로 데이터 저장3. 맵의 구현 방식3.1 HashMap (해시 기반)가장 일반적인 Map 구현체빠른 접근: O(1) 평균키의 순서는 보장되지 않음3.2 TreeMap (이진 탐색 트리 기반)키를 오름차순으로 정렬접근 시간: O(log n)범위 기반 조회에 적합3.3 Lin..

1. 집합(Set)이란?집합(Set)은 중복되지 않는 데이터의 모음을 저장하고 관리하는 자료구조다. 수학의 집합 개념과 유사하게, 동일한 값이 두 번 이상 저장되지 않는 것이 특징이다. 일반적으로 검색, 삽입, 삭제 연산이 매우 빠르게 수행된다.Java에서는 HashSet, TreeSet, LinkedHashSet 등이 대표적인 집합 자료구조다.2. 집합의 특징중복 없음: 동일한 요소는 한 번만 저장순서 없음 (HashSet 기준)빠른 검색: 평균 O(1) 시간 복잡도 (Hash 기반)3. 집합의 종류와 구현3.1 HashSet (해시 기반)가장 일반적인 Set 구현순서 보장 없음3.2 TreeSet (이진 탐색 트리 기반)자동 정렬 (오름차순)삽입, 삭제, 탐색: O(log n)3.3 LinkedHas..

1. 해시란?해시(Hash)는 키(Key)를 입력받아 고정된 크기의 해시 값(Hash Value)으로 변환하고, 이를 기반으로 데이터를 저장하고 검색하는 자료구조다. 주로 해시 테이블(Hash Table) 형태로 구현되며, 빠른 검색, 삽입, 삭제 성능(O(1))을 제공한다.해시는 데이터베이스, 캐시 시스템, 언어의 딕셔너리 자료형 등 다양한 분야에서 폭넓게 사용된다.2. 해시의 구성 요소키(Key): 데이터를 식별하는 값값(Value): 키에 대응하는 데이터해시 함수(Hash Function): 키를 고유한 해시 값으로 변환하는 함수버킷(Bucket): 해시 값에 따라 데이터를 저장하는 공간3. 해시 함수(Hash Function)좋은 해시 함수는 다음과 같은 특성을 갖는다.빠르게 계산 가능균등 분포:..

1. 그래프란?그래프(Graph)는 정점(Vertex)과 간선(Edge)으로 이루어진 비선형 자료구조로, 사물 간의 관계나 연결 상태를 표현할 때 사용된다. 소셜 네트워크, 지도, 컴퓨터 네트워크 등 복잡한 구조와 상호작용을 모델링하는 데 매우 적합하다.그래프는 방향성, 가중치, 연결성 등에 따라 다양한 형태로 분류된다.2. 그래프의 기본 용어정점(Vertex): 데이터가 저장되는 기본 단위간선(Edge): 정점 간의 연결을 나타내는 선무방향 그래프(Undirected Graph): 간선에 방향이 없는 그래프방향 그래프(Directed Graph): 간선에 방향이 있는 그래프가중치(Weight): 간선에 부여된 값 (예: 거리, 비용 등)3. 그래프의 표현 방법3.1 인접 행렬(Adjacency Matr..

1. 레드-블랙 트리란?레드-블랙 트리(Red-Black Tree)는 균형 이진 탐색 트리(Balanced Binary Search Tree)의 일종으로, 삽입과 삭제 시에도 트리의 높이를 제한하여 효율적인 성능을 유지하는 자료구조다.트리의 각 노드는 레드(Red) 또는 블랙(Black) 색상을 가지며, 특정 규칙을 통해 트리의 균형이 보장된다.2. 레드-블랙 트리의 속성레드-블랙 트리는 다음 다섯 가지 속성을 만족해야 한다:모든 노드는 빨강 또는 검정이다.루트 노드는 검정이다.모든 리프(NIL 노드)는 검정이다.빨강 노드의 자식은 항상 검정이다. (연속된 빨강 노드 없음)어떤 노드에서든 리프 노드까지의 모든 경로에 포함된 검정 노드의 수는 같다.이러한 규칙을 통해 트리의 균형이 보장되고, 최악의 경우에..

1. 힙이란?힙(Heap)은 완전 이진 트리(Complete Binary Tree)의 일종으로, 항상 부모 노드의 값이 자식 노드의 값보다 크거나 작게 유지되는 특성을 가진 자료구조다. 일반적으로 우선순위 큐(Priority Queue)를 구현하는 데 사용된다.힙은 두 가지 형태로 나뉜다:최대 힙(Max Heap): 부모 노드의 값 ≥ 자식 노드의 값최소 힙(Min Heap): 부모 노드의 값 ≤ 자식 노드의 값2. 힙의 특징완전 이진 트리: 노드가 왼쪽부터 채워짐루트 노드가 최댓값 또는 최솟값효율적인 삽입과 삭제 (O(log n))3. 힙의 연산삽입(Insert): 트리의 마지막에 삽입 후, 부모와 비교하며 위로 올림 (Heapify Up)삭제(Delete, Pop): 루트 노드 제거 후 마지막 노드를..

1. 트리란?트리(Tree)는 계층적(hierarchical) 구조를 표현하는 비선형 자료구조로, 노드(Node)와 간선(Edge)으로 구성된다. 트리는 루트(Root) 노드를 중심으로 자식 노드로 확장되며, 순환이 없는 방향 그래프의 일종이다.2. 트리의 기본 용어노드(Node): 데이터를 담는 기본 단위루트(Root): 트리의 시작점이 되는 최상위 노드부모 노드(Parent)와 자식 노드(Child)리프(Leaf): 자식이 없는 노드서브트리(Subtree): 특정 노드를 루트로 하는 트리레벨(Level): 루트에서부터의 깊이높이(Height): 트리의 최대 깊이3. 트리의 종류3.1 일반 트리 (General Tree)자식 노드 수에 제한 없는 트리3.2 이진 트리 (Binary Tree)각 노드가 ..