hyejun CSlog

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..

8.1 트리의 개념 트리: 계층적인 구조를 나타내는 자료구조(계층적인 구조)선형자료구조(리스트, 스택, 큐), 한 개 이상의 노드로 이루어진 유한 집합 노드(node): 트리의 구성요소에 해당하는 A, B, C, D, E , F, G, H, J  A: 루트/ 서브트리에서는 B,C,D가 루트연결선: 간선(edge)A는 B의 부모노드, B는 A의 자식노드, B와C와D는 형제관계조상노드: 임의의 노드 상위에 연결되어 뻗쳐나간 모든 노드 후손노드: 임의의 노드 하위로 연결되어 뻗쳐나간 모든 노드단말노드: 자식노드가 없는 노드 비단말노드노드 차수: 어떤 노드가 갖고 있는 자식노드의 개수트리 차수: 트리가 갖고있는 노드의 차수 중 가장 큰 값트리 레벨: 트리의 각층에 번호 매기기(루트의 레벨이 1, 한 층씩 내려갈..