KNOWLEDGE17 [Database] 데이터 모델 데이터 모델 : 현실 세계의 정보들을 컴퓨터에 표현하기 위해 단순화, 추상화해 표현한 개념적 모형. 데이터베이스 설계 과정에서 데이터의 구조(스키마)를 논리적으로 표현하기 위해 사용되는 도구. 데이터 모델 구성 요소: 개체, 속성, 관계 개체(Entity): DB에 표현하려는 개념. 속성으로 구성됨. 특징 파일 시스템의 레코드에 대응. 정보 제공 역할. 영속적으로 존재하는 개체의 집합. 다른 개체와 하나 이상의 관계 맺음. 유일한 식별자에 의해 식별 가능 예시) 교수 개체는 속성(교수번호, 성명, 전공, 소속)으로 구성. 개체 타입(레코드 타입): 속성(으로만 기술된 개체의 정의) 개체 인스턴스: 하나의 개체 나타내는 것. 한 줄. 개체 세트: 개체 인스턴스의 모음 개체 선정 방법 자료 흐름도(DFD)를.. 2022. 11. 21. [Data Structure] 문자열과 해시: String, Hash, Trie, KMP String string : 문자들로 구성된 배열. s[0], s[1], ..., s[n-1], [\n0] Substring(부분문자열): S의 i번~j번의 연속된 글자로 구성된 문자열: s[i...j] cf)Subsequence(부분 수열): 문자열의 일부 글자가 원래 순서 유지하며 나열된 형태. 연속적이진 않지만 중간중간 뽑아내서 나열. prefix(접두사): S의 0번 글자부터 a번 글자까지 구성된 부분 문자열 suffix(접미사): S의 a번 글자부터 끝까지로 구성된 부분 문자열 Hash 임의 길이의 데이터(ex. 문자열)를 고정된 길이의 데이터(ex. 정수)로 매핑하는 함수 해싱(hashing): 키(key, 매핑 전 데이터)를 값(hash value, 매핑 후 데이터)으로 매핑 해시테이블이라는.. 2022. 7. 6. [Data Structure] B Tree, B+ Tree B Tree 이진트리의 확장 버전 더 많은 수의 자식을 가질 수 있게 일반화시킨 트리구조 모든 leaf노드들이 같은 레벨을 가질 수 있도록 자동으로 균형을 맞춤 정렬된 순서 보장, 멀티레벨 인덱싱을 통한 빠른 검색 → 데이터베이스와 파일 시스템에서 널리 사용 규칙 노드는 최대 M개 부터 M/2개 까지의 자식을 가질 수 있다. 노드에는 최대 M-1 개부터 [M/2]-1 개의 키가 포함될 수 있다. 노드의 키가 x개라면 자식의 수는 x+1개다. 최소차수: 자식 수의 하한값. 최소차수가 t라면 M = 2t-1을 만족 EX. 최소차수 t가 2라면, 3차 B트리이며, key의 하한은 1개이다. 탐색 루트 노드부터 하향식으로 검색 찾고자하는 값 k가 key들 사이에 있다면 거기의 자식 노드로 내려감 리프노드까지 갔.. 2022. 7. 5. [Data Structure] Binary Search Tree 이진 탐색 트리 (Binary Search Tree) 트리 자료구조 중 가장 간단한 형태. 이진 탐색이 동작할 수 있도록 고안된, 효율적 탐색이 가능한 자료구조 탐색, 삽입, 삭제가 모두 가능 이진트리(탐색 $O(logN)$) + 연결리스트(삽입, 삭제 $O(1)$) 중복된 노드 없음 이진 탐색 트리 핵심 연산 검색 트리의 높이가 h일 때 O(h) 삽입 삽입 위치까지 찾아가는 연산 O(h)+ 삽입 연산 O(1) -> O(h) 삭제 자식이 없는 노드인 경우 그냥 삭제 자식이 1개인 노드인 경우 자식 노드의 값으로 대체 자식이 2개인 노드인 경우 왼쪽 서브 트리의 최대값 or 오른쪽 서브 트리의 최소값 중 하나로 대체 이진 탐색 트리의 특징 부모 노드보다 왼쪽 자식 노드가 작음 부모 노드보다 오른쪽 자식 노.. 2022. 7. 3. [Data Structure] Tree, Binary Tree (+heap) 트리 노드(정보의 단위. 어떤 정보를 가지고 있는 개체)와 노드의 연결(간선, edge)로 표현. 그래프 자료구조의 일종. DB 시스템이나 파일 시스템 같은 곳에서 많은 양의 데이터 관리 위한 목적으로 사용 연결된 정보 저장하는 인접리스트로 구현 비선형 자료구조, 계층적 자료구조 Connected acyclic (undirected) graph 방향성이 존재하지 않고 사이클이 없는 연결 그래프 트리 자료구조의 특징 부모 노드와 자식 노드의 관계로 표현 형제: 부모 노드가 같은 두 노드의 관계 조상/자손: 부모/자식 노드들의 집합 루트 노드: 최상단 노드 단말 노드: 최하단 노드. 리프 노드. 서브 트리: 트리에서 일부를 떼어낸 것. 일부 떼도 트리 구조. 포레스트: 트리가 여러 개! 포레스트는 트리가 아.. 2022. 7. 2. [Data Structure] 선형 자료구조: Stack, Queue, Priority Queue, Deque 자료구조 추출되는 데이터 스택 가장 나중에 삽입된 데이터 큐 가장 먼저 삽입된 데이터 우선순위 큐 가장 우선순위가 높은 데이터 스택 LIFO 방식 (Last In First Out, 나중에 들어온게 먼저 나감, 후입선출), 선입후출 박스 쌓기에 비유. 아래(왼쪽)부터 위(오른쪽)로 점점 올리고 맨 위부터 뺌 원소의 삽입/삭제가 한쪽 끝(top)에서만 이루어짐 유한 순서 리스트 append(): 리스트 가장 뒤쪽(오른쪽)에 데이터 삽입 pop(): 리스트 가장 뒤쪽(오른쪽)에서 데이터 꺼냄 큐 FIFO 방식 (First In First Out, 먼저 들어온게 먼저 나감) 줄서기에 비유. 먼저 온 사람이 먼저 들어감. 원소의 삽입 및 삭제가 양쪽 끝에서 일어남 (front, rear) rear에는 삽입(en.. 2022. 7. 1. 이전 1 2 3 다음
