오구리의 DevLog

복습하기 위해 학부 수업 내용을 필기한 내용입니다. 이해를 제대로 하지 못하고 정리한 경우 틀린 내용이 있을 수 있습니다. 그러한 부분에 대해서는 알려주시면 정말 감사하겠습니다. ▶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 라인은 아래 그림과 같이 하나의 링크의 대역폭을 공유한다. 왼쪽의 링크는 전송 스트림을 멀티플렉서로 유도하여 단일 스트림(다대일)으..

복습하기 위해 학부 수업 내용을 필기한 내용입니다. 이해를 제대로 하지 못하고 정리한 경우 틀린 내용이 있을 수 있습니다. 그러한 부분에 대해서는 알려주시면 정말 감사하겠습니다. ▶Contents Signals Signal Impairment Digital Transmission Analog Transmission Multiplexing Transmission Media ▶Analog Transmission 디지털 전송은 바람직하지만 low-pass 채널(0부터 시작하는 채널)이 필요하다. bandpass 채널(0부터 시작하지 않는 채널)이 있는 경우 아날로그 전송이 유일한 선택이다. 디지털 데이터를 bandpass 아날로그 신호로 변환하는 것은 디지털-아날로그 변환이다. low-pass 아날로그 신호를..

복습하기 위해 학부 수업 내용을 필기한 내용입니다. 이해를 제대로 하지 못하고 정리한 경우 틀린 내용이 있을 수 있습니다. 그러한 부분에 대해서는 알려주시면 정말 감사하겠습니다. ▶Contents Signals Signal Impairment Digital Transmission Analog Transmission Multiplexing Transmission Media ▶Digital Transmission 컴퓨터 네트워크는 한 지점에서 다른 지점으로 정보를 보내도록 설계되었다. 이 정보는 전송을 위해 디지털 신호 또는 아날로그 신호로 변환되어야 한다. 첫 번째 선택인 디지털 신호로의 변환(digital to digital 변환)에 대해 논의한다. 두 번째 선택인 아날로그 신호로의 변환(analog t..

우선 나는 컴퓨터학부에 재학 중인 3학년 학생이다. 개발자나 서버 전문가에 비하면 관련 지식이 턱없이 부족한 건 사실이다. 하지만 이번 일에 관해서 많이 찾아보고 조사해봤다. 그래서 학부생 입장에서 이번 사태에 대해서 글을 써보자고 한다. 물론, 개인적인 의견이고 간혹 틀린 부분이 있을 수도 있다. 그런 부분이 보인다면 알려주시면 감사할 것 같다. 어제부터 어느 정도 복구되고 있는지 틈틈이 찾아보고 있다. 오늘 아침 수업을 갈 때는 어제 밤보다 많은 부분들을 복구했다. 하지만 아직까지 갈길이 먼 거 같다. 카카오 하면 전 국민이 사용한다고 해도 과언이 아닐 것이다. 전 국민 중에서 카카오톡을 사용 안 하는 사람은 얼마나 될까? 지난 4월, 앱 분석 서비스 와이즈 앱, 리테일, 굿즈가 조사한 바로는 카카오..

복습하기 위해 학부 수업 내용을 필기한 내용입니다. 이해를 제대로 하지 못하고 정리한 경우 틀린 내용이 있을 수 있습니다. 그러한 부분에 대해서는 알려주시면 정말 감사하겠습니다. ▶Contents Signals Signal Impairment Digital Transmission Analog Transmission Multiplexing Transmission Media ▶Performance 지금까지, 네트워크를 통해 데이터(신호)를 전송하는 도구와 데이터가 어떻게 동작하는지 알아봤다. 네트워킹에서 한 가지 중요한 문제는 네트워크의 성능이다. (얼마나 좋냐?) Bandwidth(대역폭) 네트워크 성능을 측정하는 한 가지 특성은 대역폭이다. ex. 2.10 가입자 회선의 대역폭은 음성 또는 데이터의 경우..

복습하기 위해 학부 수업 내용을 필기한 내용입니다. 이해를 제대로 하지 못하고 정리한 경우 틀린 내용이 있을 수 있습니다. 그러한 부분에 대해서는 알려주시면 정말 감사하겠습니다. 이전에 썼던 관계형 대수와 이어서 작성하는 글입니다. 2022.10.15 - [컴퓨터공학/데이터베이스] - [데이터베이스] 관계형 대수 [데이터베이스] 관계형 대수 복습하기 위해 학부 수업 내용을 필기한 내용입니다. 이해를 제대로 하지 못하고 정리한 경우 틀린 내용이 있을 수 있습니다. 그러한 부분에 대해서는 알려주시면 정말 감사하겠습니다. ▶관계 dhalsdl12.tistory.com ▶외부 합집합 (Outer Union ∪+) 합병 가능하지 않은 두 릴레이션에 대해 모든 애트리뷰트가 포함되도록 확장된 형태의 릴레이션으로 만드..

복습하기 위해 학부 수업 내용을 필기한 내용입니다. 이해를 제대로 하지 못하고 정리한 경우 틀린 내용이 있을 수 있습니다. 그러한 부분에 대해서는 알려주시면 정말 감사하겠습니다. ▶관계형 대수 (Relational Algebra) 릴레이션을 처리하기 위한 연산자들의 집합 연산의 피연산자가 모두 릴레이션이고 연산 결과 또한 릴레이션이다. 집합 연산자 합집합 (Union ∪) 교집합 (Intersect ∩) 차집합 (Difference -) 곱집합 (Cartesian Product X) 순수 관계형 연산자 실렉트 (Select) 프로젝트 (Project) 조인 (Join) 디비전 (Division ÷) ▶집합 연산자 곱집합(카티션 프로덕트)을 제외하고는 피연산자인 두 릴레이션은 서로 합병 가능해야 한다. 합..

복습하기 위해 학부 수업 내용을 필기한 내용입니다. 이해를 제대로 하지 못하고 정리한 경우 틀린 내용이 있을 수 있습니다. 그러한 부분에 대해서는 알려주시면 정말 감사하겠습니다. ▶관계형 데이터 모델 1970년에 IBM의 E.F.Codd에 의해 처음 제안되었다. 외형적으로는 단순한 테이블의 구조로 표현하지만, 내부적으로는 릴레이션과 수학적인 이론을 기초로 하고 있다. 학생(Student) 테이블 테이블 : 릴레이션 (relation) 테이블의 열 (또는 필드) : 애트리뷰트 (atrribute) 테이블의 행 (도는 레코드) : 튜플 (tuple) "20181234", "김철수" : 애트리뷰트의 값 (value) 더 이상 분해할 수 없는 원자 값(atomic value)만을 허용한다. 도메인 (domain..

복습하기 위해 학부 수업 내용을 필기한 내용입니다. 이해를 제대로 하지 못하고 정리한 경우 틀린 내용이 있을 수 있습니다. 그러한 부분에 대해서는 알려주시면 정말 감사하겠습니다. ▶B - 트리 차수가 m인 B - 트리의 특성 비어있거나 높이가 1 이상인 m - 원 탐색 트리(m-way search tree)이다. 루트와 리프를 제외한 노드는 최소 ⌈ m/2 ⌉, 최대 m개의 서브 트리를 갖는다. 루트는 리프가 아닌 이상 적어도 두 개의 서브 트리를 갖는다. 모든 리프는 같은 레벨에 있다. 리프가 아닌 노드의 키 값의 수는 그 노드의 서브 트리 수 보다 하나 적다. 각 리프 노드는 최소 ⌈ m/2 ⌉ - 1개, 최대 m - 1개의 키 값을 갖는다. 한 노드 안에 있는 키 값들은 오름차순을 유지한다. htt..

복습하기 위해 학부 수업 내용을 필기한 내용입니다. 이해를 제대로 하지 못하고 정리한 경우 틀린 내용이 있을 수 있습니다. 그러한 부분에 대해서는 알려주시면 정말 감사하겠습니다. ▶Taylor Series 도함수 평균값 정리는 함수 f(x)와 그 첫 번째 도함수가 xi에서 xi+1까지의 구간에서 연속된다면, f(xi)와 f(xi+1)를 연결하는 선과 평행한 f'(ξ)로 지정된 기울기를 갖는 함수 위에 적어도 하나의 점이 존재한다. 도함수 근사치의 오차는 단계 크기에 비례해야 한다. 단계 크기를 절반으로 줄이면 도함수의 오차를 절반으로 줄일 수 있을 것이다. 차이가 줄어들수록 차이가 줄어들 것이다. 또한 충분히 작은 h 값에서 오차는 h^2에 비례해야 한다. 즉, 오차가 절반으로 줄어들면 오차는 4분의 1..

복습하기 위해 학부 수업 내용을 필기한 내용입니다. 이해를 제대로 하지 못하고 정리한 경우 틀린 내용이 있을 수 있습니다. 그러한 부분에 대해서는 알려주시면 정말 감사하겠습니다. ▶직접 저장장치 탐구 시간(seek time) 헤드가 원하는 트랙(실린더)까지 이동하는 데 걸리는 시간 회전 지연시간(rotational delay) 그 트랙에서 원하는 레코드(섹터 또는 블록 )가 헤드 밑에 회전하여 올 때까지 기다리는 시간 탐구 시간이 회전 지연시간 보다 훨씬 길다. ▶데이터의 저장 데이터 접근시간(data access time) 탐구 시간 + 회전 지연시간 + 데이터 전송시간 탐구 시간이 가장 많은 시간을 차지해서, 줄이면 빨라진다. 데이터베이스의 중요한 성능 개선의 초점 디스크 접근 횟수(I/O, 헤드 움..

복습하기 위해 학부 수업 내용을 필기한 내용입니다. 이해를 제대로 하지 못하고 정리한 경우 틀린 내용이 있을 수 있습니다. 그러한 부분에 대해서는 알려주시면 정말 감사하겠습니다. ▶Contents Signals Signal Impairment Digital Transmission Analog Transmission Multiplexing Transmission Media ▶Signal Impairment 신호가 전송 매체를 통과하지만, 이는 완벽하지 않다. 결함으로 인해 신호가 손상됨 매체의 시작 부분의 신호가 매체의 끝 부분의 신호와 동일하지 않음을 의미한다. 전송된 것은 수신된 것이 아니다. 3가지 손상 원인: attenuation(감쇠), distortion(왜곡) 및 noise(소음) 아주 정확히..