본문 바로가기

CS110

이진 탐색 트리(BST, Binary Search Tree) 특정 자료구조를 사용했을 때의 시간 복잡도나 내부적으로 어떻게 동작하는 지 구체적으로 알고 있는 것도 중요하다는 것을 이번에 뼈저리게 느꼈다 이진 탐색 트리는 이진 트리로 만들어진 탐색을 위한 자료구조이다. 4가지 조건을 가진다. 1. 이진 탐색 트리의 4가지 조건 1) 모든 노드의 키는 유일하다. 2) 왼쪽 서브트리의 모든 키는 루트 노드의 키보다 작다 3) 오른쪽 서브트리의 모든 키는 루트 노드의 키보다 크다 4) 서브트리도 이진탐색트리이다. 2. 이진 탐색트리의 동작 방식 1) 탐색(Search) 위의 이진 탐색 트리에서 14라는 키 값을 찾는다고 생각하면 루트노드 10과 비교했을 때, 14가 더 큼으로 오른쪽 서브 트리로 이동 오른쪽 서브 트리의 루트노드 17과 비교했을 때, 14가 더 작음으로 .. 2020. 5. 23.
LRU Cache 캐시란 속도가 빠른 장치와 속도가 느린 장치 간의 병목현상을 줄이기 위한 범용 메모리로, 지역성을 이용해 사용할 데이터를 예측해 저장한다 쉽게 말하면 사용했던 데이터를 속도가 빠른 저장장치에 저장해놓고, 다음에 참조할때 캐시 메모리를 이용해 빠르게 참조하는 방식이다 LRU는 Least Recently Used의 약자로 가장 최근에 참조되지 않은 데이터가 교체시점에서 먼저 나가는 방식이다. 컴퓨터 구조 전공 수업에서 배운 내용은 아래와 같았다 A, B, C, D 순으로 데이터가 참조되었다면 참조비트는 아래와 같고 A B C D 1 2 3 4 캐시 메모리가 가득 찬 상태에서 캐시 메모리에 있는 데이터 A를 다시 참조할 경우 A B C D 4 1 2 3 캐시 메모리에 없는 데이터 E가 참조될 경우 교체가 일어.. 2020. 5. 22.
[데이터베이스] 07. SQL 1. SQL 관계 데이터베이스를 위한 표준 질의어로 비절차적 데이터 언어. 1) 데이터 정의어(DDL) : 테이블 생성/변경/제거 2) 데이터 조작어(DML) : 데이터 삽입/수정/삭제/검색 3) 데이터 제어어(DCL) : 데이터 접근 및 사용권한 부여/취소 2. 데이터 정의 테이블 생성/변경/제거 1) 테이블 생성 CREATE TABLE 테이블이름 ( /* 속성 정의 부분. 데이터 타입을 정의하고 널값의 허용여부와 default값을 설정 */ 속성이름 데이터타입 [NOT NULL] [DEFAULT 기본값] /* 기본키 */ PRIMARY KEY (속성리스트) /* 대체키 */ UNIQUE (속성리스트) /* 외래키. 참조무결성제약조건을 위해 참조하는 테이블 이름, 삭제, 변경 시 제약조건을 명세 */ .. 2020. 4. 9.
[알고리즘] 크루스칼(Kruskal) 알고리즘 크루스칼 알고리즘이란? 크루스칼 알고리즘은 그리디 알고리즘을 적용해 그래프의 모든 노드를 최소 비용으로 연결해 최소 비용 신장 트리(MST, Minimum Spanning Tree)를 구하는 알고리즘이다. 그리디 알고리즘 https://dheldh77.tistory.com/52 [알고리즘] Greedy Algorithm(탐욕 알고리즘) Greedy Algorithm[탐욕 알고리즘]이란? 각 단계에서 가장 최선의 선택지(가장 큰, 가장 작은 등)를 고르는 것. Greedy 알고리즘은 구현이 쉽다는 장점이 있지만, 항상 최선의 답을 구하는 것은 아니다. Greedy Alg.. dheldh77.tistory.com 신장 트리(Spanning Tree) 그래프 내의 모든 정점을 포함하는 트리로 모든 정점들을 연.. 2020. 4. 5.
[운영체제] 운영체제 운영체제 1)운영체제의 개념 - 자원의 관리와 보호, 사용자 인터페이스 제공, 하드웨어 인터페이스 제공 등을 하는 시스템 소프트웨어 2) 운영체제의 역할 - 자원 관리(효율성) - 자원 보호(안정성) - 하드웨어 인터페이스(디바이스 드라이버) 제공(확장성) - 소프트웨어 인터페이스(GUI) 제공(편리성) 2. 운영체제의 구조 1) 커널과 인터페이스 (1) 커널 - 프로세스 관리, 메모리 관리, 저장 장치 관리 등 운영체제의 핵심기능을 모아놓은 것 (2) 인터페이스 - 커널에 사용자의 명령을 전달하고 실행결과를 사용자에게 다시 알려주는 역할 2) 시스템 호출과 디바이스 드라이버 (1) 시스템 호출(System call) - 운영체제는 커널 모드와 사용자 모드로 나누어져 있음 - 커널 모드에서 자원에 접근하.. 2020. 3. 30.
[데이터베이스] 06. 관계 데이터 연산 1. 관계 데이터 연산 관계 데이터 모델에서 연산은 원하는 데이터를 얻기 위해 릴레이션에 필요한 처리 요구를 수행하는 것. 데이터 언어의 역할. 데이터 언어 유용성 검증에 사용될 수 있으며, 데이터 언어가 관계 데이터 연산을 모두 기술할 수 있을 때, 관계적으로 완벽하다고 말할 수 있으며 유용성이 검증된다. 2. 관계 대수 관계 데이터 연산에서 데이터의 처리 과정을 순서대로 기술하는 절차적 언어. 폐쇄특성(릴레이션이 피연산자일 때 결과도 릴레이션) 1) 일반 집합 연산자 릴레이션이 튜플의 집합이라는 개념을 이용. 피연산자가 2개 필요. 합집합, 교집합, 차집합은 합병 가능(두 릴레이션의 차수와 대응하는 속성의 도메인이 같음)해야함 a. 합집합 - 릴레이션R 또는 릴레이션S에 속하는 튜플로 릴레이션 구성(.. 2020. 3. 30.
[데이터베이스] 05. 관계 데이터 모델 1. 관계 데이터 모델의 개념 1) 관계 데이터 a. 릴레이션(relation) - 하나의 개체에 대한 데이터 b. 속성(attribute) - 릴레이션의 열 c. 튜플(tuple) - 릴레이션의 행, 개체의 인스턴스 d. 도메인(domain) - 속성 하나가 가질 수 있는 모든 값의 집합. 원자값. 무결성 확인 e. 차수(degree) - 전체 속성의 개수 f. 카디널리티(cardinality) - 전체 튜플의 개수 2) 릴레이션과 데이터베이스의 구성 a. 릴레이션 스키마 - 릴레이션 논리적구조. 릴레이션 내포 [릴레이션 이름(속성1, 속성2, ...., 속성n)] b. 릴레이션 인스턴스 - 한 시점에 릴레이션에 존재하는 튜플의 집합, 릴레이션 외연 c. 데이터베이스 스키마 - 데이터베이스는 여러개의 .. 2020. 3. 30.
[데이터베이스] 04. 데이터 모델링 1. 데이터 모델링과 데이터 모델의 개념 1) 데이터 모델링 현실 세계에 존재하는 데이터를 컴퓨터 세계의 데이터베이스로 옮기는 과정 a. 개념적 모델링(conceptual modeling) - 현실세계에 존재하는 데이터를 개념적 세계로 옮기는 것 b. 논리적 모델링(logicl modeling) - 개념적세계의 데이터를 데이터베이스에 저장할 논리적 구조로 표현 2) 데이터 모델 데이터 모델링의 결과물을 표현하는 도구로 데이터 구조, 연산, 제약조건으로 구성 a. 개념적 모델 - 개념적 모델링을 통해 개념적 구조로 표현하는 도구, 개체-관계 모델 a. 논리적 모델 - 논리적 모델링을 통해 논리적 구조로 표현하는 도구, 관계 데이터 모델 2. 개체 - 관계 모델 개체와 개체 간의 관게를 이용해 현실 세계를 .. 2020. 3. 27.
[데이터베이스] 03. 데이터베이스 시스템 1. 데이터베이스 시스템(DBS, DataBase System) 정의 데이터베이스에 데이터를 저장, 관리하여 필요한 정보를 생성해주는 시스템 2. 데이터베이스 구조 1) 스키마(Schema) 데이터의 구조와 제약조건을 정의 2) 3단계 데이터베이스 구조 데이터베이스 구조를 3단계로 나누고 각 단계별로 추상화를 제공함으로써 데이터의 저장, 유지와 관련된 복잡한 내용을 숨기고 사용자에게 필요한 데이터만 제공 a. 외부 단계(External level) - 사용자 관점, 외부 스키마 b. 개념 단계(Conceptual level) - 조직 전체 관점, 데이터/관계/제약조건/보안 정책 정의, 개념 스키마 c. 내부 단계(Internal level) - 저장장치 관점, 저장장치에 저장되는 방법 정의, 내부 스키마.. 2020. 3. 27.
[데이터베이스] 02. 데이터베이스 관리시스템 1. 데이터베이스 관리시스템의 등장배경 파일 시스템 - 데이터를 파일로 관리하는 소프트웨어 파일 시스템의 문제점 - 데이터 중복성, 데이터 종속성, 동시 공유/회복/보안의 부족 2. 데이터베이스 관리시스템(DBMS, DataBase Management System) 1) 정의 : 데이터를 데이터베이스에 통합하여 저장하고 관리하는 소프트웨어 2) 기능 정의 기능 : 데이터베이스의 구조 정의, 수정 조작 기능 : 데이터를 삽입, 삭제, 수정, 조회 연산 제어 기능 : 일관성과 무결성의 유지, 보안 및 회복 제어 3. 데이터베이스 관리시스템의 장단점 1) 장점 : 중복의 최소화, 데이터 독립성, 동시 공유, 보안, 데이터 무결성, 표준화, 회복 2) 단점 : 비용, 백업과 회복의 복잡함, 중앙관리로 인한 취약.. 2020. 3. 26.
[데이터베이스] 01. 데이터베이스 기본 개념 1. 데이터와 정보 1) 데이터(Data) - 현실세계에서 단순한 관찰이나 측정으로 얻은 값 또는 사실 2) 정보(Information) - 데이터를 의사결정에 사용될 수 있도록 가공처리한 결과물 3) 정보처리(Information Processing) - 데이터에서 정보를 추출하는 과정 4) 정보시스템(Information System) - 데이터를 수집하고 저장했다가 필요할 때마다 처리해 유용한 정보를 만들어주는 수단 2. 데이터베이스의 정의 데이터베이스는 여러사용자가 공유할 수 있도록 통합하여 저장된 운영데이터의 집합 1) 공유데이터(shared data) 2) 통합데이터(intergrated data) 3) 저장데이터(stored data) 4) 운영데이터(operational data) 3. 데.. 2020. 3. 26.
[자료구조] ProrityQueue(우선순위큐) - Java Collections Framework PriorityQueue(우선순위큐) 일반적으로 Queue(큐)는 선입선출(FIFO, First In First Out)의 성격을 가지고 있는 자료구조이지만, 우선순위 큐는 들어오는 순서에 상관없이 우선순위가 높은 원소부터 빠져나가는 자료구조이다. 운영체제의 CPU 스케줄링 중 우선순위 스케줄링이 우선순위 큐를 이용한 예이다. java Collections Framework에서 우선순위큐의 자세한 사용법은 아래 코드를 참조하자 package algorithm; import java.util.*; public class priorityQueue { public static void main(String[] args) { PriorityQueue q = new PriorityQueue(); // 데이터 저장.. 2020. 3. 23.