트라이(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개 이하의 키를 가진다. 정렬된 상태를 유지하고 있어 효율적 탐색이 가능하다.  장단점장점자동으로 균형을 유지하여 검색, ..

트랜잭션(Transaction)이란?DBMS에서 일련의 연산을 논리적인 작업 단위로 묶어 처리하는 개념. 여러 작업을 하나의 단위로 처리.데이터베이스의 무결성 유지를 위함.무결성 : 데이터의 정확성, 일관성, 유효성을 유지하는 것예시) 은행 시스템계좌 A에서 계좌 B로 돈을 이체할 때, A의 잔고 감소와 B의 잔고 증가가 하나의 트랜잭션으로 처리되어야 한다.만약 하나라도 실패하면 전체 트랜잭션이 롤백되어야 한다.    트랜잭션의 특성 (ACID)Atomicty / All or nothing (원자성)트랜잭션의 연산은 모두 성공하거나 모두 실패해야한다.Consistency (일관성)트랜잭션이 수행 결과는 항상 일관되어야 한다.Isolation (고립성/독립성)트랜잭션이 수행되는 동안 다른 트랜잭션의 작업이..

완전이진트리(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)버킷 : 각..

Key의 목적⭐️고유 식별자테이블 내 레코드(행)을 식별하거나 특정 속성에 대해 고유한 값을 유지하는데된다.⭐️효율적인 관리와 검색인덱스를 통해 키를 사용하여 데이터를 빠르게 검색할 수 있다.데이터 모델링특히, 관계형 데이터베이스에서 키를 사용하여 테이블 간의 관계를 정의하고 데이터 모델을 설계할 수 있다.  Key의 종류 기본 키 (Primary Key)각 레코드를 고유하게 식별하는데 사용되는 하나 이상의 속성(attribute)의 집합이다.기본 키는 고유해야하며, Null 값을 가질 수 없다. 후보 키 (Candidate Key)테이블 내의 각 레코드를 고유하게 식별할 수 있는 속성 또는 속성의 집합입니다.하나의 테이블에는 여러 후보 키가 있을 수 있으며, 그 중 하나가 기본 키로 선택된다. 대체 키..

데이터베이스란?일정한 규칙이나 규약을 통해 구조화되어 저장되는 데이터 모음.다양한 형태와 구조로 존재하며 사용자나 애플리케이션이 데이터를 효율적으로 저장하고 검색할 수 있도록 설계되어 있다. 데이터 무결성:데이터베이스는 데이터의 일관성과 정확성을 유지하는 데 도움을 준다.데이터 보안:사용자 접근 권한을 설정하여 민감한 데이터를 보호할 수 있다.효율적인 데이터 관리:대량의 데이터를 효율적으로 저장하고 검색할 수 있다.데이터 중복 최소화:데이터베이스는 데이터 중복을 줄이고 저장 공간을 절약하는 데 기여한다.    주요 설계 개념엔티티(Entity)데이터베이스에서 관리해야 할 대상이나 객체를 모델링한 것.DB내에서 하나의 고유하게 식별될 수 있는 속성들을 가짐.실 세계의 사물, 개념, 사람 등을 나타낼 수 있..