CS

[네트워크] 1. 네트워크 기초 (쉽게 배우는 데이터 통신과 컴퓨터 네트워크)

1. 네트워크 기초 01 용어의 정의 1. 네트워크 기초 용어 네트워크 Network 하드웨어적 전송 매체(Transmission Media)를 매개로 서로 연결되어 데이터를 교환하는 시스템의 모음 네트워크 구성요소의 개념 시스템 내부 규칙에 따라 자율적으로 동작하는 대상 물리적 대상뿐만 아니라 소프트웨어적 대상들도 포함 ex. 자동차, 커피 자판기, 컴퓨터, 하드시스크 + 교통 제어 시스템, 운영체제, 프로세스 시스템의 동작에 필요한 욉 ㅜ입력, 내부 정보와 외부 입력의 조합에 따른 출력(시스템 실행의 결과물) 인터넷: 수많은 소규모 네트워크들이 서로 연동되는 반복적인 과정을 거쳐서 형성된 거대 연합체의 네트워크 인터페이스 시스템과 시스템을 연결하기 위한 표준화된 접촉 지점 시스템과 전송 매체의 연결 ..

[데이터베이스 개론] 6. 관계 데이터 연산

06 관계 데이터 연산 01 관계 데이터 연산의 개념 관계 데이터 연산(relatioshipn data operation) : 원하는 데이터를 얻기 위해 릴레이션에 필요한 처리 요구를 수행 데이터베이스 시스템의 구성 요소 중 데이터 언어의 역할 관계 대수 원하는 결과를 얻기 위해 데이터의 처리 과정을 순서대로 기술하는 절차 언어 관계 해석 원하는 결과를 얻기 위해 처리를 원하는 데이터가 무엇인지만 기술하는 비절차 언어 관계 대수 ↔ 관계 해석 어떤 언어로 기술되더라도 다른 언어로 기술 가능 질의(query): 데이터에 대한 처리 요구 02 관계 대수 1. 관계 대수의 개념과 연산자 관계 대수: 원하는 결과를 얻기 위해 릴레이션을 처리하는 과정을 순서대로 기술하는 언어, 연산자들의 집합 관계 대수에서 피연..

[데이터베이스 개론] 5. 관계 데이터 모델

목차 5. 관계 데이터 모델 01 관계 데이터 모델의 개념 1. 관계 데이터 모델의 기본 용어 열: 속성 고객아이디 CHAR(20) 고객 이름 CHAR(20) 나이 INT 등급 CHAR(10) 직업 CHAR(10) 적립금 INT attribute 행: tuple apple 김현준 20 gold 학생 1000 BANANA 정소화 25 vip 간호사 2500 하나의 개체에 관한 데이터를 릴레이션(relation) 하나에 담아 데이터베이스에 저장 속성 릴레이션의 열 서로 다른 이름을 이용해 구별 릴레이션: 파일 관리 시스템의 파일, 속성: 파일의 필드에 대응 투플(tuple) 릴레이션의 행 개체의 인스턴스 도메인 속성 하나가 가질 수 있는 모든 값의 집합 관계 데이터 모델에서는 더 분해할 수 없는 원자 값만 ..

[알고리즘] 유니온-파인드 (Union-Find) (자바 Java)

목차 유니온 파인드 (Union-Find) 서로소 집합(Disjoint-sets) 서로 중복 포함된 원소가 없는 집합들 → 교집합이 없다 집합에 속한 하나의 특정 멤버를 통해 각 집합들을 구분, 이를 대표자(representative)라고 함 연산 Make-Set(x): 원소 x로만 구성된 집합을 만든다 Find-Set(x): 원소 x를 가진 집합을 알아낸다 Union(x, y): 원소 x를 가진 집합과 원소 y를 가진 집합을 하나로 합친다 표현 방법 연결 리스트, 트리 1. 연결 리스트 같은 집합의 원소들은 하나의 연결리스트로 관리 연결리스트의 맨 앞의 원소를 집합의 대표원소로 삼음 각 원소는 집합의 대표원소를 가리키는 링크를 갖는다 2. 트리 하나의 집합을 하나의 트리로 표현 자식 노드가 부모노드를 ..

[알고리즘] 최단 경로 알고리즘 - 다익스트라(Dijkstra), 벨만-포드 (Bellman-Ford) (자바/Java)

목차 최단 경로 간선의 가중치가 있는 그래프에서 두 정점 사이의 경로들 중 간선의 가중치의 합이 최소인 경로 하나의 시작 정점에서 끝 정점까지의 최단 경로 다익스트라 (dijkstra): 음의 가중치 허용x 벨만-포드(Bellman-Ford) : 음의 가중치 허용o 모든 정점들에 대한 최단 경로 플로이드-워샬(Floyd-Warshall) 알고리즘 1. Dijkstra 알고리즘 시작 정점에서 거리가 최소인 정점을 선택해 나가면서 최단 경로를 구하는 방식 탐욕 기법을 사용 - 프림 알고리즘과 유사 시작 정점(s)에서 끝 정점(t)까지의 최단 경로에 정점 x가 존재 이때 최단 경로는 s에서 x까지의 최단 경로와 x에서 t까지으 ㅣ최단 경로로 구성됨 s→t = s→x + x→t 시간복잡도 : O(ElogV) 과..

[알고리즘] 최소 신장 트리(MST, Minimum Spanning Tree) (자바/Java)

목차 최소 신장 트리 (MST) 신장트리: 그래프의 모든 정점과 간선의 부분 집합으로 구성되는 트리 최소신장트리: 신장 트리 중에서 사용된 가중치의 합이 최소인 트리 특징 무방향 가중치 그래프 그래프의 가중치 합이 최소여야 한다 N개의 정점을 가지는 그래프에 대해 반드시 N-1개의 간선을 사용 사이클을 포함하면 안된다. 크루스칼 알고리즘 간선을 하나씩 선택해서 MST를 찾는 알고리즘 최초, 모든 간선을 가중치에 따라 올므차순으로 정렬 가중치가 가장 낮은 간선부터 선택하면서 트리를 증가 사이클이 존재하면 다음으로 가중치가 낮은 간선 선택 (사이클 존재: 대표가 같으면 사이클(Find-Set)) n-1개의 간선이 선택될 때까지 2)를 반복 Kruskal(G) { A

[알고리즘] 최장 공통 부분 수열 (Longest Common Subsequence LCS)

목차 LCS (Longest Common Subsequence) 최장 공통 부분 수열 LCS의 길이 찾기 $$ x_m = y_n 이면 LCS(X_m, Y_n) = LCS(X_{m-1}, Y_{n-1})+1 $$ $$ x_m \neq y_n 이면 LCS(X_m, Y_n) = max(LCS(X_{m-1}, Y_{n}), LCS(X_{m}, Y_{n-1})) $$ https://velog.io/@emplam27/알고리즘-그림으로-알아보는-LCS-알고리즘-Longest-Common-Substring와-Longest-Common-Subsequence 문제 예시 9251번: LCS C[i-1][j] = A의 i-1번째, B의 j번째까지의 LCS Xi와 Yj가 같지 않다면 새로운 값을 추가할 수 없으니, 이전의 LC..

[데이터베이스 개론] 4. 데이터 모델링

목차 4. 데이터 모델링 01 데이터 모델링과 데이터 모델의 개념 데이터 모델링: 현실 세계에 존재하는 데이터를 컴퓨터 세계의 데이터베이스 옮기는 변환 과정 추상화(abstraction): 데이터베이스에 저장하여 관리할 만한 가치가 있는 중요 데이터를 찾아내는 과정 현실 세계 → (개념적 모델링) → 개념 세계 → (논리적 모델링) → 컴퓨터 세계 개념적 모델링: 현실 세계에서 중요 데이터를 추출하여 개념 세계로 옮기는 작업 논리적 모델링: 개념 세계의 데이터를 데이터베이스에 저장할 구조를 결정하고 이 구조를 표현하는 작업 데이터 모델: 데이터 모델링의 결과물을 표현하는 도구 데이터 구조 개념적 데이터 모델-현실 세계를 개념 세계로 추상화했을 때 어떤 요소로 이루어져 있는지를 표현하는 개념적 구조 논리적..

[데이터베이스 개론] 3. 데이터베이스 시스템

목차 03 데이터베이스 시스템 01 데이터베이스 시스템의 정의 데이터베이스에 데이터를 저장하고, 저장된 데이터를 관리하여 조직에 필요한 정보를 생성해주는 시스템 데이터베이스: 데이터를 저장해두는 곳, 저장된 데이터의 집합 데이터베이스 관리 시스템: 데이터베이스에 저장된 데이터를 관리 데이터베이스 시스템: 데이터베이스와 데이터베이스 관리 시스템을 이용해 조직에 필요한 정보를 제공하는 ‘전체 시스템’ → 데이터베이스 시스템의 핵심 구성 요소 = 데이터베이스, 데이터베이스 관리 시스템 +사용자, 데이터 언어, 컴퓨터 등 02 데이터베이스의 구조 1. 스키마 schema 데이터베이스에 저장되는 데이터 구조와 제약조건을 정의 ex. 고객- 고객번호(INT), 이름(CHAR(10)), 나이(INT), 주소 (CHA..

[데이터베이스 개론] 2. 데이터베이스 관리 시스템

목차 데이터베이스 관리 시스템 01 데이터베이스 관리 시스템의 등장 배경 과거-파일 시스템을 이용 파일 시스템 장점: 별도의 구매비용x 응용 프로그램마다 파일을 따로 유지 문제점 같은 내용의 데이터가 여러 파일에 중복 저장 응용 프로그램이 데이터 파일에 종속적 데이터 종속성: 사용하는 파일의 구조를 변경하면 응용 프로그램도 함께 변경해야 한다 데이터 파일에 대한 동시 공유, 보안, 회복 기능이 부족하다 응용 프로그램을 개발하기 쉽지 않다 02 데이터베이스 관리 시스템의 정의 데이터베이스 관리 시스템(DBMS: DataBase Management System) 정의: 파일 시스템의 데이터 중복과 데이터 종속 문제를 해결하기 위해 제시된 소프트웨어 조직에 필요한 데이터를 데이터베이스에 통합하여 저장하고 이에..