hyejun CSlog

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) 방향그래프: 간선에 방향성 존재. 간선을 통하여 한쪽 방향으로만 갈 수 있음을 나..

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, 한 층씩 내려갈..

7.1 원형 연결 리스트원형 연결 리스트 : 마지막 노드가 첫 번째 노드 가리키는 리스트(마지막 노드의 링크필드가 null이 아닌 첫번째 노드 주소가 되는 리스트) 장점: 하나의 노드에서 다른 모든 노드로의 접근 가능 - 링크 계속 따라가면 결국 모든 노드 거쳐서 자기 자신으로 되돌아온다. ->노드 삽입,삭제가 단순 연결리스트보다 용이.(삭제나 삽입시 항상 선행노드 가리키는 포인터 필요) 특히 유용한 경우 : 리스트의 끝에 노드 삽입하는 연산이 단순 연결리스트보다 효율적. (단순 연결리스트에서 리스트 끝에 노드 추가하려면 첫 번째 노드에서부터 링크를 따라서 노드의 개수만큼 진행하여 마지막 노드까지 가야함.) 원형연결리스트는 원칙적으로 헤드 포인터만 있으면 된다.   원형리스트의 처음에 삽입 : 새로운 노..

2.1 네트워크 애플리케이션의 원리[네트워크 apps]loss sensitive applications(절대 loss 발생하면 안됨): email, web, text messaging, remote login, P2P file sharingdelay sensiitive applications(loss에는 그다지 sensitive X, delay에 민감): 멀티유저 네트워크 게임, IP너머 통화(skype같은), [스트리밍 저장 비디오(유튜브, 넷플릭스 등), 실시간비디오회의]->bandwidth-sensitive(+용량에도 민감) 이기도 함.+social metworking, internet search ...[네트워크 앱 만들기]다른 end system에서 계속됨 , 네트워크 통신(web server ..

6.1 리스트 추상 데이터 타입 리스트: 순서 또는 위치를 가지는 항목들이 차례대로 저장 (스택과 큐도 리스트의 일종)                                              ㄴ집합과는 다름(집합은 항목간 순서가 없기 때문에)                                                                                                       ㄴ삽입, 삭제, 탐색연산리스트 ADT 구현:  배열(더 간단)과 연결리스트 통해 가능 BUT 크기 고정. 포인터 이용하여  만들수도 있음 배열을 사용한 리스트 구현의 장단점장점: 구현 간단, 속도 빠름단점: 리스트 크기 고정, 동적으로 크기 늘리고 줄이기 힘듦, 남은 공간 없으..

5.1 큐 추상 데이터 타입-먼저 들어온 데이터가 먼저 나가는 구조(선입선출, FIFO) : 뒤에서 새로운 데이터 추가, 앞에서 데이터 하나씩 삭제. *스택은 삽입삭제가 같은 곳에서 일어나지만 큐는 다른 쪽에서 일어남 삽입삭제에 쓰이는 변수: 스택에서는 top이라는 변수 1개 존재, 큐에서는 삽입-rear, 삭제-front 사용 (배열과 연결리스트로 구현) 5.2 선형큐ex. 1차원 배열 쓰는 방법 : (정수저장큐 만든다 가정) 먼저 정수 1차원 배열 정의 - > 삽입, 삭제 위한 변수 front와 rear 만듦ㄴ front 와 rear의 초기값 : -1 (같음) . [실행] 데이터 증가> rear 하나 증가>그 위치에 데이터 저장 삭제할 때도 front 하나 증가> front가 가리키는 위치에 있는 데..

4.1 스택이란? -스택: 뭔가를 쌓아놓은 더미, 후입선출 입출력은 맨 위에서만 일어나고 스택의 중간에서는 데이터를 삭제할 수 없다. 스택 상단 : 입출력이 이루어지는 부분스택 하단: 반대쪽 바닥부분요소: 스택에 저장되는 것공백 스택: 스택에 요소가 하나도 없을 때*자료 출력순서가 입력순서 역순으로 이루어져야 할 경우 유용*함수호출 이후 자신을 호출한 함수로 되돌아갈 때 호출된 역순으로 되돌아가야 하므로 스택 사용(복귀할 주소 기억에 사용) -시스템 스택에는 함수가 호출될때마다 활성레코드가 만들어지며 여기에 복귀주소가 저장된다. (활성레코드에는 프로그램 카운터, 함수호출시 매개변수, 함수 안에서 선언된 지역 변수 같이 생성)  -함수호출 일어나면 항상 시스템 스택에 동일한 방법으로 저장 > 함수가 자기 ..