본문 바로가기

전체 글103

[자료구조] 13. 탐색 탐색이란? 탐색키: 항목과 항목을 구별해주는 키 정렬되지 않은 배열에서의 탐색 순차탐색(sequential search) : 정렬되지 않은 sequence에서 처음부터 마지막까지 순차적으로 하나씩 검사하는 방법 --> O(n) 정렬된 배열에서의 탐색 이진탐색(binary search) : 정렬된 배열의 중앙에 있는 값을 조사하여, 찾고자 하는 항목이 그 값보다 작은지 큰지 판단하여, 탐색의 범위를 반으로 줄여가며 탐색한다. --> O(log(n)) 색인 순차탐색(indexed sequential search) : 인덱스 테이블을 먼저 검사하여, 탐색키가 속한 범위를 알아낸 후, 순차탐색한다. 보간탐색(interpolation search) : 배열[0]과 배열[n-1] 값을 통해 탐색키가 존재할 위치를 .. 2023. 12. 14.

[자료구조] 12. 정렬 선택정렬(selection sort) : 정렬되지 않은 곳에서 비교하여, 가장 작은 애와 배열의 맨 앞의 애를 교환한다. - 시간복잡도: O(n^2) - unstable sort - in-place sort 비교연산: 정렬되지 않은 곳에서 제일 작은 애 이동연산: 교환 --> unstable sort 삽입정렬(insertion sort) : 정렬되지 않은 곳의 맨 앞의 애를, 정렬된 곳에서 비교하여 적절한 자리에 삽입한다. - 시간복잡도: 최악의 경우는 O(n^2), 최선의 경우는 O(n); 대부분 정렬되어 있으면 매우 효과적이다. - stable sort - in-place sort key값에 정렬되지 않은 부분의 맨 앞의 애를 넣는다. --> 공간복잡도: O(1): in-place sort 비교연산:.. 2023. 12. 14.

[자료구조] 11. 그래프(2) 최소비용 신장트리(MST: Minimum Spanning Tree) 신장트리(spanning tree): 그래프 내의 모든 정점을 포함하는 트리 (사이클 x) 최소비용 신장트리(MST): 모든 정점들을 가장 작은 비용으로 연결하는 트리 Kruscal의 MST 알고리즘 : 모든 edge를 검사하여, least-weight edge를 찾고, 그 edge가 사이클을 만들지 않으면, 추가한다. => 시간복잡도: O(e*log(e)), 모든 edge들의 weight를 한번에 비교하므로, 희박한 그래프에서 유리하다. Union-Find 알고리즘: 사이클을 만드는지 검사하는 알고리즘 Find: 어떤 두 노드의 root를 찾아낸다. root가 서로 다르다면, 두 노드 사이의 edge는 bridge이므로, 그 edge는.. 2023. 12. 14.

[자료구조] 10. 그래프(1) 그래프 그래프 용어 그래프 정의 무방향 그래프, 방향 그래프 가중치 그래프 부분 그래프 그래프 용어 인접 정점 정점의 차수 진입 차수(in-degree) 진출 차수(out-degree) 경로(path) 단순 경로(simple cycle): 반복되는 정점 없음 사이클(cycle): 시작 정점 = 종료 정점 단순 사이클(simple cycle) 오일러 사이클: 모든 edge 한번씩만 거쳐서 제자리로으로 돌아온다. (단순 사이클 x) 헤밀턴 사이클: 모든 node 한번씩만 거쳐서 제자리로 돌아온다. (단순 사이클) 그래프 연결 정도 연결 그래프 비연결 그래프 완전 그래프: 모든 정점이 연결되어 있는 그래프 그래프의 표현 방법 인접 행렬(adjacent matrix) 인접 리스트(adjacent list) 그래.. 2023. 12. 14.

[네트워크] 5.7 네트워크 관리와 SNMP, NETCONF/YANG 네트워크 관리 SNMP NETCONF YANG Network management는 사실 다소 복잡한 내용이다. 우리는 대략적인 개념만 배운다! What is network management? Components for network management Managing server: 네트워크 전체를 컨트롤하는 서버 Managed device: managing server에 의해 manage되는 장치들 (server, client, router, switch를 포함한다.) Data: managed device 내의 데이터 (= MIB) Network management protocol: managing server가 managed device를 관리하기 위한 프로토콜 (예: SNMP) Network ope.. 2023. 12. 10.

[네트워크] 5.6 인터넷 제어 메시지 프로토콜(ICMP) 이제 SDN에 대한 이야기를 마쳤다. Network management에 대해 이야기해보자. Network management: 네트워크를 모니터링하고 있다가, 네트워크에 문제가 생기면, 이를 해결하는 것! ICMP: Internet Control Message Protocol ▷ host와 router가 네트워크 상태정보를 교환하는 데에 사용된다. Error reporting: router에서 destination host로 데이터를 전송하다가 문제가 생겼을 때, 이를 source host에게 알린다. ping - ping 보낼 때: echo request - ping 받을 때: echo reply --> echo reply가 오면, 그 host가 running 상태임을 알 수 있다. TTL expir.. 2023. 12. 10.

[네트워크] 5.5 SDN control plane SDN (Software Defined Networking) 지금까지 traditional routing에 대해 배웠다. 이제 SDN에 대해 알아보자. Traditional Internet: Per-router Control Plane Traditional routing의 problem: "monolitic" router (하드웨어부터 어플리케이션까지 하나로 묶여 있다.) Solution: "middlebox" Traffic Engineering: Difficult with Traditional Routing Traffic engineering: traffic이 거쳐가는 길을 조정하는 것 --> Traditional routing에서는 traffic engineering이 어렵다. --> SDN: Gen.. 2023. 12. 10.

[네트워크] 5.4 인터넷 서비스 제공업자(ISP) 간의 라우팅: BGP Routing protocols in the Internet: Popular unicast routing protocols Interior (Intra-AS routing) RIP OSPF Exterior (Inter-AS routing) BGP 5.4 인터넷 서비스 제공업자(ISP) 간의 라우팅: BGP: 서로 다른 AS 간의 routing Inter-AS Routing: A Role In Intradomain ForwardingAS1에서 AS1 밖의 router 3b로 datagram을 보내고 싶어 하는 상황을 상상해보자. 이때 AS1이 알아야 할 정보는 두 가지다.3b로 가기 위해서는 어떤 AS로 이동해야 하는가?AS3으로 이동해야 함을 알았다. AS3으로 가기 위해서는 당장 어떤 router로 이.. 2023. 12. 10.

[네트워크] 5.3 인터넷에서의 AS 내부 라우팅: RIP, OSPF Routing protocol이 엄청 다양하네? 이러한 routing algorithm에는 문제가 많다...확장성 문제Administrative autonomy (행정 자치) 문제: 독자성을 보장받고 싶다! --> Autonomous Systems (AS)Hierarchical routing: Autonomous Systems (AS)▷ 하나의 AS 안에서는:동일한 routing policy를 적용한다.Single ownsership 하에 있다.Unique 32-bit integer AS number (ASN)에 의해 식별된다. Internet approach to scalable routing: 실질적으로는 각 AS에 마다 자신만의 고유한 routing protocol을 갖는다. ▶ Routing pr.. 2023. 12. 10.

이전 1 2 3 4 ··· 12 다음

최근글

인기글

전체 방문자

Today :

Yesterday :

티스토리툴바