hyejun CSlog

4.3 인터넷 프로토콜(IP) : IPv4, 주소체계, IPv6 등IPv4 fragmentation, reassembly네트워크 링크에는 링크 수준 프레임이 전송할 수 있는 최대 데이터 양인 MTU(최대 전송단위) 가 있다.경로에 따라 다른 링크유형 , 다른 MTU라우터에서 대용량 IP 데이터그램 분할('fragment')하나의 데이터그램 -> 여러 개의 데이터그램(조각)'IP header'을 사용하여 전송 계층에 도달하기 전에 router가 아닌 최종 목적지 "host"에서만 재조립됨.IP헤더비트는 관련 조각 식별, 순서 지정에 사용IP4 fragmentation at routerQ. MTU가 700바이트인 링크로 2400바이트의 데이터그램을 전송한다고 가정해보자. 원본 데이터그램에 식별번호 422가 ..

14.1 해싱이란?선형탐색이나 이진탐색은 모두 키를 저장된 키값과 반복적으로 비교함으로써 탐색하고자 하는 항목에 접근-> 최대 가능한 시간 복잡도가 O(로그n)에 그친다. 어떤 응용에서는 더 빠른 탐색 알고리즘 요구해싱은 O(1)의 시간 안에 탐색 끝마칠수도 있다.키에 산술적인 연산 적용 -> 항목이 저장돼있는 테이블의 주소를 계산한여 항목에 접근. 해시테이블: 키에 대한 연산에 의해 직접 접근 가능한 구조해싱: 해시테이블 이용한 탐색14.2 추상자료형 사전사전 : (키,값)쌍의 집합. 키와 관련된 값을 동시에 저장하는 자료구조. (키,값)쌍을 저장할 수도 있고 삭제할수도 있으며 키를 가지고 값을 검색할 수 있다. map이나 table로 불리기도 한다.키 : 사전의 단어처럼 항목과 항목을 구별시켜주는 것..

*시험 : 교재문제+ 교수님이 올려주신 기출문제13.1 탐색이란? 탐색: 기본적으로 여러 개의 자료 중 원하는 자료를 찾는 작업- 탐색키와 데이터로 이루어진 여러 개의 항목 중 원하는 탐색키 갖고 있는 항목 찾는 것사용되는 자료구조 : 배열, 연결리스트, 트리, 그래프 .......가장 기초적인 방법: 배열 사용하여 자료 저장하고 찾기, but 탐색성능을 향상하고자 한다: 이진트리처럼 보다 진보된 방법으로 자료를 저장하고 찾아야 한다.탐색의 단위 : 항목(숫자 or 구조체...) - 항목과 항목을 구별시켜주는 탐색키 존재 13.2 정렬되지 않은 배열에서의 탐색순차탐색 : 탐색 방법 중 가장 간단하고 직접적인 탐색방법. 정렬되지 않은 배열의 항목들을 처음부터 마지막까지 하나씩 검사하여 원하는 항목 찾기탐색..

* 챕터목표 : data plane을 중심으로 network layer service의 원리 이해 4.1 네트워크 계층 개요network layer service models (transport 계층의 서비스 모델은 p2p, client-server가 있었다.)forwarding 대 routing (네트워크 계층의 핵심기능-transport 계층의 mux, demux처럼-여러개의 기능: flow control, congestion control, reliable data transfer... *transport 계층은 end system에만 올라가는 protocal 계층. network 계층부터는 network core의 router에도 탑재가 되게 되는 프로토콜 )라우터(network core에 있는 ..

12.1 정렬이란?정렬: 물건을 크기순으로 오름차순이나 내림차순으로 나열하는 것정렬시켜야 될 대상: 레코드, 레코드는 필드라는 단위로 나뉘어진다.키: 레코드와 레코드를 식별해주는 역할을 하는 필드 = 레코드들을 키값의 순서로 재배열최적 알고리즘은 존재하지 않으므로 이들 방법 중에서 현재 환경에서 가장 효율적인 정렬 알고리즘을 선택해야 한다.효율성의 기준: 정렬 위해 필요한 비교연산의 횟수와 이동연산의 횟수(빅오표기법 이용)횟수는 자료의 초기화 여부에 의존적, 이동횟수와 비교횟수가 서로 비례하지 x숫자와 숫자 비교는 시간 별로 안 걸림, 문자열과 문자열 비교하는 것은 상당히 시간 걸림, 숫자이동보다 큰 구조체 이동하려면 많은 시간 걸림 > 잘 맞춰서 적절한 정렬 알고리즘 선택해야 함.정렬 알고리즘의 효율성..

11.1 최소 비용 신장 트리신장트리: 그래프내 모든 정점을 포함하는 트리트리의 특수한 형태 : 모든 정점 연결, 사이클 포함 x그래프에 있는 n개의 정점을 정확히 (n-1)개의 간선으로 연결. 하나의 그래프에는 많은 신장트리 존재.깊이 우선이나 너비 우선탐색 때 사용한 간선들 표시하면 신장트리 만들 수 있음.그래프의 최소연결부분 그래프(간선의 수가 가장 적음)n개의 정점 갖는 그래프는 최소 (n-1)개 간선 가져야 함,(n-1)의 간선으로 연결돼있으면 필연적으로 트리형태>신장트리통신네트워크 구축에 많이 사용최소비용신장트리네트워크에 있는 모든 정점들을 가장 적은 수의 간선과 비용으로 연결신장트리 중 사용된 간선들의 가중치 합이 최소.각 링크의 구축 비용은 똑같지 x -> 각 링크(간선)에 비용 붙여서 링..

10.1 그래프란?그래프: 객체사이 연결관계 표현하는 자료구조 (ex. 지하철노선도), 선형리스트나 트리(트리도 그래프의 종류이긴 함)의 구조보다 복잡. 인접행렬이나 인접리스트로 메모리에 표현되고 처리될 수 있음.  10.2 그래프의 정의와 용어정점과 간선들의 유한집합수학적으로는 G=(V,E)와 같이 표시.V(G)는 그래프 G의 정점들의 집합, E(G)는 그래프 G의 간선들의 집합정점 vertex (=노드 node) : 여러가지 특성을 가질 수 있는 객체,간선 edge (링크 link): 이러한 정점들 간 관계  무방향 그래프와 방향 그래프무방향그래프 : 간선을 통해서 양방향으로 갈 수 있음을 나타냄, (A,B)=(B,A) 방향그래프: 간선에 방향성 존재. 간선을 통하여 한쪽 방향으로만 갈 수 있음을 나..

에너지(Energy)에너지/일=(에너지/작용) x (작용/일) 1. 역학 - 힘과 운동중력(질량), 추진력(단위시간당 배출하는 기체의 양과 속력), 양력(물체를 위로 띄우는 힘, 속도에 비례, 모양이 중요), 항력(이동 시 앞의 공기가 가로막는 힘, 속도에 비례) 운동이란? 변위: 물체의 위치 변화량속도, 속력 가속도시간벡터 :크기와 방향 : 좌표와 성분 :  내적은 교환법칙 성립, 외적은 교환법칙 성립하지 않음, 내적은 2차원에서도 정의 가능, 외적은 3차원에서만 정의 가능벡터에 대한 수학적 고찰벡터장(vector field) :중력장:전기장:자기장:벡터공간 (vector space):단위벡터, 기저벡터차원사영자유낙하운동 : 질량에 상관없이 지상에 도달하는 시간은 같음(중력이 질량에 비례하여 모든 물체..

9.1 우선순위 큐 추상 데이터 타입[우선순위 큐] 데이터들이 우선순위 갖고있고 우선순위 높은 데이터가 먼저 나간다.0개 이상의 요소 모임(각 요소는 우선순위값 갖고 있음)최소 우선순위 큐: 가장 우선순위 낮은 요소가 먼저 삭제최대 우선순위 큐: 가장 우선순위 높은 요소가 먼저 삭제  9.2 우선순위 큐의 구현방법1. 배열 사용정렬 안 된 배열 사용:삽입 - 배열의 맨 끝에 새로운 요소 추가> 시간복잡도 O(1)삭제 - 가장 우선순위가 높은 요소를 찾아야 한다. > 정렬 안 돼 있으므로 처음부터 끝까지 모든요소 스캔 > 시간복잡도 O(n)+요소 삭제된 다음 뒤에 있는 요소를 앞으로 이동시켜야 한다.정렬된 배열 사용: 삽입- 위치 찾기 위해 순차탐색, 이진탐색 이용> 삽입위치 뒤의 요소 이동시켜서 빈자리 ..

3.1 Transport-layer sevices기본적인 목적: network 계층에서 host to host를 deliver해준다면 목적지 host까지 온 후 목적지 process 찾아갈 수 있어야 한다.서로 다른 호스트에서 실행되는 앱 프로세스 간의 논리적 통신 제공(application 프로세스 간 end-to-end communication)전송프로토콜은 end systems(hosts)에서만 실행발신자는 앱 메시지를 내려받은 후 segment로 분할하여 네트워크 계층으로 전달(네트워크 계층에서 목적지 호스트 찾아감)수신자(목적지 호스트)는 segment를 메시지로 재조립하여 앱 계층으로 전달(그대로 보관해서)인터넷 어플리케이션에 사용할 수 있는 두 가지 transport 프로토콜 : TCP, U..