오구리의 DevLog

복습하기 위해 학부 수업 내용을 필기한 내용입니다. 이해를 제대로 하지 못하고 정리한 경우 틀린 내용이 있을 수 있습니다. 그러한 부분에 대해서는 알려주시면 정말 감사하겠습니다. 지난 글에 이어서 작성해 보도록 하겠습니다. 2022.11.23 - [컴퓨터공학/데이터베이스] - [데이터베이스] 데이터베이스 설계 [데이터베이스] 데이터베이스 설계 복습하기 위해 학부 수업 내용을 필기한 내용입니다. 이해를 제대로 하지 못하고 정리한 경우 틀린 내용이 있을 수 있습니다. 그러한 부분에 대해서는 알려주시면 정말 감사하겠습니다. ▶설계 dhalsdl12.tistory.com ▶논리적 설계(logical design) 개념적 설계에서 생성된 개념적 데이터 스키마로부터 목표 DBMS가 처리할 수 있는 스키마를 생성하는..

복습하기 위해 학부 수업 내용을 필기한 내용입니다. 이해를 제대로 하지 못하고 정리한 경우 틀린 내용이 있을 수 있습니다. 그러한 부분에 대해서는 알려주시면 정말 감사하겠습니다. ▶설계 개요 데이터베이스 개발 생명 주기(life cycle) 데이터베이스 설계 단계 요구사항 분석을 기초로 데이터 베이스 구조를 작성하는 과정이다. 문제가 발생되면 피드백을 받아 적절한 단계로 되돌아가 다시 시작한다. 데이터베이스 설계 시 고려사항 무결성(integrity) 변경 연산 후에도 제약조건 만족 일관성(consistency) 데이터 간, 응답 간의 일치 회복(recovery) 장애 발생 시 일관된 상태로 복구 보안(security) 불법 접근의 방지 효율성(efficiency) 응답 시간/저장 공간 최소화 생산성 향..

복습하기 위해 학부 수업 내용을 필기한 내용입니다. 이해를 제대로 하지 못하고 정리한 경우 틀린 내용이 있을 수 있습니다. 그러한 부분에 대해서는 알려주시면 정말 감사하겠습니다. 2022.11.22 - [컴퓨터공학/알고리즘2] - [알고리즘2] Undirected and Directed Graphs [알고리즘2] Undirected and Directed Graphs 복습하기 위해 학부 수업 내용을 필기한 내용입니다. 이해를 제대로 하지 못하고 정리한 경우 틀린 내용이 있을 수 있습니다. 그러한 부분에 대해서는 알려주시면 정말 감사하겠습니다. ▶Content dhalsdl12.tistory.com ▶구현된 API 정리 class Digraph: # Digraph 객체를 저장하는 클래스 def revers..

복습하기 위해 학부 수업 내용을 필기한 내용입니다. 이해를 제대로 하지 못하고 정리한 경우 틀린 내용이 있을 수 있습니다. 그러한 부분에 대해서는 알려주시면 정말 감사하겠습니다. ▶Contents Undirected Graph Directed Graph Web Crawling Topological Sort Strongly-Connected Component ▶Undirected Graph 간선에 방향성이 없는 그래프이다. 특정 조건을 만족하는 (모든 간선이 양방향) Digraph의 집합이다. 따라서 Digraph의 부분 집합이다. Undirected Graph 알고리즘 조건에 맞는 일부 경우에만 동작하는 알고리즘이므로 상대적으로 간단하다. ex. connected components 구하는데 DFS를 그..

복습하기 위해 학부 수업 내용을 필기한 내용입니다. 이해를 제대로 하지 못하고 정리한 경우 틀린 내용이 있을 수 있습니다. 그러한 부분에 대해서는 알려주시면 정말 감사하겠습니다. 지난 글에 이어서 작성해 보도록 하겠습니다. 2022.11.12 - [컴퓨터공학/데이터베이스] - [데이터베이스] 데이터베이스 정규화 [데이터베이스] 데이터베이스 정규화 복습하기 위해 학부 수업 내용을 필기한 내용입니다. 이해를 제대로 하지 못하고 정리한 경우 틀린 내용이 있을 수 있습니다. 그러한 부분에 대해서는 알려주시면 정말 감사하겠습니다. ▶잘못 dhalsdl12.tistory.com ▶비정규 릴레이션 기본키 : {학번, 과목 코드} 학번과 과목 코드의 조합으로 학생이 등록한 과목의 성적을 식별할 수 있다. 한 학생은 한..

복습하기 위해 학부 수업 내용을 필기한 내용입니다. 이해를 제대로 하지 못하고 정리한 경우 틀린 내용이 있을 수 있습니다. 그러한 부분에 대해서는 알려주시면 정말 감사하겠습니다. ▶잘못 설계된 데이터베이스 같은 학번이 나타날 때마다 학년 애트리뷰트 값도 똑같이 중복적으로 나타난다. ▶이상(anomaly) 현상 검색할 때는 상관없고, 변경(삭제, 삽입, 갱신)할 때 이상현상이 나타난다. 삭제 이상(deletion anomaly) 학번 3654 고영준 학생이 과목 'CO234'의 등록을 취소할 때 => 4학년이라는 정보도 함께 삭제된다. 연쇄 삭제(triggered deletion)에 의해 정보가 영원히 손실되는 현상이다. 삽입 이상(insertion anomaly) 학번이 7654, 학년이 3인 학생을 삽..

복습하기 위해 학부 수업 내용을 필기한 내용입니다. 이해를 제대로 하지 못하고 정리한 경우 틀린 내용이 있을 수 있습니다. 그러한 부분에 대해서는 알려주시면 정말 감사하겠습니다. 지난 글에 이어서 작성해 보도록 하겠습니다. 2022.11.11 - [컴퓨터공학/데이터베이스] - [데이터베이스] SQL - Structured Query Language2 [데이터베이스] SQL - Structured Query Language2 복습하기 위해 학부 수업 내용을 필기한 내용입니다. 이해를 제대로 하지 못하고 정리한 경우 틀린 내용이 있을 수 있습니다. 그러한 부분에 대해서는 알려주시면 정말 감사하겠습니다. 지난 글 dhalsdl12.tistory.com ▶삽입 SQL 삽입 SQL은 이중 모드 (dual mode..

복습하기 위해 학부 수업 내용을 필기한 내용입니다. 이해를 제대로 하지 못하고 정리한 경우 틀린 내용이 있을 수 있습니다. 그러한 부분에 대해서는 알려주시면 정말 감사하겠습니다. 지난 글에 이어서 작성해 보도록 하겠습니다. 2022.11.10 - [컴퓨터공학/데이터베이스] - [데이터베이스] SQL - Structured Query Language [데이터베이스] SQL - Structured Query Language 복습하기 위해 학부 수업 내용을 필기한 내용입니다. 이해를 제대로 하지 못하고 정리한 경우 틀린 내용이 있을 수 있습니다. 그러한 부분에 대해서는 알려주시면 정말 감사하겠습니다. ▶SQL 개 dhalsdl12.tistory.com ▶SQL 데이터 조작어 검색 ☞ 중첩 질의문(nested ..

복습하기 위해 학부 수업 내용을 필기한 내용입니다. 이해를 제대로 하지 못하고 정리한 경우 틀린 내용이 있을 수 있습니다. 그러한 부분에 대해서는 알려주시면 정말 감사하겠습니다. ▶SQL 개요 SQL은 관계형 데이터베이스의 표준 언어로써 모든 주요 제품에서 채택되고 있다. SQL의 특징 데이터 정의어, 데이터 조작어, 데이터 제어어 등 모든 기능 제공한다. 대화형 질의어와 Java, C 등 고급 프로그래밍 언어 내에 SQL이 삽입된 형태로 사용이 가능하다. ▶SQL 데이터 정의어 테이블을 생성하고 정의하거나 새로운 애트리뷰트를 추가/제거할 수 있다. 또한 뷰 생성/제거, 인덱스 생성/제거를 할 수 있다. CREATE TABLE 수강( 학번 INTEGER NOT NULL, 과목코드 CHAR(5) NOT N..

복습하기 위해 학부 수업 내용을 필기한 내용입니다. 이해를 제대로 하지 못하고 정리한 경우 틀린 내용이 있을 수 있습니다. 그러한 부분에 대해서는 알려주시면 정말 감사하겠습니다. import copy import random from queue import PriorityQueue class Board: def __init__(self, tiles): self.n = len(tiles) self.tiles = copy.deepcopy(tiles) self.twinBoard = None # Compute Hamming distance self.hammingDistance = 0 goal = 0 for rowId, row in enumerate(tiles): for colId, t in enumerate(r..

복습하기 위해 학부 수업 내용을 필기한 내용입니다. 이해를 제대로 하지 못하고 정리한 경우 틀린 내용이 있을 수 있습니다. 그러한 부분에 대해서는 알려주시면 정말 감사하겠습니다. ▶Contents Binary Heap을 사용한 PQ의 구현 Priority Queue 사용 애플리케이션 공통적인 특성 Slider Puzzle and A* Search with PQ ▶Priority Queue insert() 1. complete binary tree 형태를 유지한다. 2. heap order를 유지한다. 3. ~logN 시간에 새 원소를 추가한다. insert(k)하는 새 값을 k라고 할 때, k를 tree 가장 마지막에(배열 끝에) 추가한다. k를 부모 노드와 비교해 heap-order(부모 >= 자식) ..

복습하기 위해 학부 수업 내용을 필기한 내용입니다. 이해를 제대로 하지 못하고 정리한 경우 틀린 내용이 있을 수 있습니다. 그러한 부분에 대해서는 알려주시면 정말 감사하겠습니다. ▶Collinear Points 4개 이상 점 연결하는 maximal한 직선을 모두 찾는 코드이다. N개 점의 (x, y) 좌표가 입력으로 주어졌을 때, 4개 이상 점을 연결하는 maximal한 직선을 모두 찾으면 된다. ▶Collinear Points 탐지방법 하나하나 비교하면서 하는 Brute Force방식을 사용할 수 있다. 하지만 시간 복잡도 측면에서 좋지 못한 코드가 된다. 정렬을 활용한 더 효율적인 방법을 사용하면 된다. 각 점 p에 대해, p가 다른 모든 점과 이루는 기울기를 계산해, 기울기를 key로 정렬한다. 정..

복습하기 위해 학부 수업 내용을 필기한 내용입니다. 이해를 제대로 하지 못하고 정리한 경우 틀린 내용이 있을 수 있습니다. 그러한 부분에 대해서는 알려주시면 정말 감사하겠습니다. ▶Contents Bottom-up Merge Sort Sorting Complexity Stability of Sorting Quick Select Duplicate Keys and 3-way Partitioning ▶Merge Sort 인접한 두 조각끼리 Merge(정렬된 순서로 병합)을 반복한다. 총 N개 원소를 병합한다면, 이들을 순서에 맞게 차례로 결과 배열에 옮겨 담으므로 ~N회 작업이 필요하다. 이러한 작업을 ~log(N)회 반복해야 한다. 입력 데이터 크기가 N이라면 결과를 옮겨 담을 ~N의 추가 공간도 필요하다...

복습하기 위해 학부 수업 내용을 필기한 내용입니다. 이해를 제대로 하지 못하고 정리한 경우 틀린 내용이 있을 수 있습니다. 그러한 부분에 대해서는 알려주시면 정말 감사하겠습니다. ▶Open Method bracketing method (아래 그림 6.1a) bracketing method와 다르게, open method는 x 하나만 있거나 또는 반드시 근을 괄호로 묶지 않는 두 개의 시작 값만 필요한 공식을 기반으로 한다. 때때로 계산이 진행됨에 따라 근으로부터 분리되거나 멀어진다(아래 그림 6.1b). 그러나, 개방형 방법들이 수렴될 때(아래 그림 6.1c), 그들은 보통 bracketing method보다 훨씬 더 빠르다. ▶Simple Fixed-Point Iteration f(x) = 0 → x ..

복습하기 위해 학부 수업 내용을 필기한 내용입니다. 이해를 제대로 하지 못하고 정리한 경우 틀린 내용이 있을 수 있습니다. 그러한 부분에 대해서는 알려주시면 정말 감사하겠습니다. ▶False-Position Method 비록 bisection이 근을 결정하는 데 완벽하게 유효한 기술이지만, "brute-force" 접근법은 상대적으로 비효율적이다. bisection의 단점은 xl에서 xu까지의 간격을 같은 반으로 나눌 때 f(xl)와 f(xu)의 크기를 고려하지 않는다는 것이다. 예를 들어, f(xl)가 f(xu)보다 0에 훨씬 가깝다면, 루트는 xu보다 xl에 더 가까울 가능성이 높다. step 1 근이 있다고 추측되는 lower xl과 upper xu를 범위로 지정한다. f(xl) * f(xu) < ..

복습하기 위해 학부 수업 내용을 필기한 내용입니다. 이해를 제대로 하지 못하고 정리한 경우 틀린 내용이 있을 수 있습니다. 그러한 부분에 대해서는 알려주시면 정말 감사하겠습니다. ▶Roots of Equations 방정식의 근을 구하는 가장 심플한 방법 : Trial and Error (시행착오)-> 비효율적이고 엔지니어링 관행의 요구 사항에 적합하지 않다. 정의에 따르면, y = f(x)가 주어진 함수는 fi = i차 다항식 x인 형태로 표현될 수 있다면 algebraic이다.(algebraic function : 대수 함수) 다항식은 일반적으로 n = 다항식의 순서와 a의 = 상수로 표현되는 대수 함수의 단순한 클래스이다. 대수 함수 (algebraic function)f2(x) = 1 - 2.37x..

복습하기 위해 학부 수업 내용을 필기한 내용입니다. 이해를 제대로 하지 못하고 정리한 경우 틀린 내용이 있을 수 있습니다. 그러한 부분에 대해서는 알려주시면 정말 감사하겠습니다. ▶관계형 해석 (Relational Calculus) 관계형 대수는 원하는 정보를 어떻게 유도하는 가를 기술하는 절차적이다. 관계형 해석은 원하는 정보가 무엇이라는 것만 선언하는 비절차적인 특성을 가지고 있다. 관계형 해석과 관계형 대수는 동등하다. 관계형 해석과 관계형 대수는 서로 변환 가능하다. 관계형 해석의 두 가지 표현 방법 튜플 관계형 해석 도메인 관계형 해석 ▶튜플 관계형 해석 (Tuple Relational Calculus) 튜플 해석식의 구성 요소 튜플 변수 또는 범위 변수 R(t) t는 R의 튜플 변수이고, 취하..

복습하기 위해 학부 수업 내용을 필기한 내용입니다. 이해를 제대로 하지 못하고 정리한 경우 틀린 내용이 있을 수 있습니다. 그러한 부분에 대해서는 알려주시면 정말 감사하겠습니다. ▶Contents Introduction Data Link Control Media Access Protocols Link Layer Addressing ▶Data-Link Control (DLC) data link control(DLC)는 두 인접 노드 간의 통신 절차를 다룬다. DLC 기능에는 framing 및 error control가 포함된다. ▶Framing 데이터 링크 계층은 비트를 프레임에 패킹해야 한다. 우편 시스템은 일종의 framing을 실행한다. 편지를 봉투에 넣는 간단한 동작은 한 정보를 다른 정보와 분리한..

복습하기 위해 학부 수업 내용을 필기한 내용입니다. 이해를 제대로 하지 못하고 정리한 경우 틀린 내용이 있을 수 있습니다. 그러한 부분에 대해서는 알려주시면 정말 감사하겠습니다. ▶Contents Introduction Data Link Control Media Access Protocols Link Layer Addressing ▶Introduction ▶Nodes and Links 데이터 링크 계층에서의 통신은 노드 간 통신이다. 인터넷의 한 지점에서 데이터 단위가 다른 지점에 도달하려면 여러 네트워크(LAN 및 WAN)를 통과해야 한다. 이러한 LAN 및 WAN은 라우터에 의해 연결된다. 일반적으로 두 엔드 호스트와 라우터를 노드로, 그 사이의 네트워크를 링크라고 부른다. 아래 그림은 데이터 유닛의..

복습하기 위해 학부 수업 내용을 필기한 내용입니다. 이해를 제대로 하지 못하고 정리한 경우 틀린 내용이 있을 수 있습니다. 그러한 부분에 대해서는 알려주시면 정말 감사하겠습니다. ▶Contents Signals Signal Impairment Digital Transmission Analog Transmission Multiplexing Transmission Media ▶Multiplexing 미디어의 대역폭이 장치의 대역폭 요구보다 클 때마다 링크를 공유할 수 있다. 멀티플렉싱은 여러 신호를 동시에 전송할 수 있는 기술 세트이다. multiplexed system에서 n 라인은 아래 그림과 같이 하나의 링크의 대역폭을 공유한다. 왼쪽의 링크는 전송 스트림을 멀티플렉서로 유도하여 단일 스트림(다대일)으..