전체 글103 [네트워크] 5.2 라우팅 알고리즘 ▶ 라우팅 알고리즘: 송신자부터 수신자까지 라우터의 네트워크를 통과하는 최소비용 경로를 찾는 것 ▶ Global vs. Decentralized Global(link-state 알고리즘): 네트워크 전체에 대한 완전한 정보를 가지고 출발지와 목적지 사이의 최소 비용 경로를 계산한다.Decentralized(distance-vector 알고리즘): 최소 비용 경로의 계산이 라우터들에 의해 반복적이고 분산된 방식으로 수행된다. ▶ Static vs. DynamicStatic: 경로 계산 cost가 변하지 않는다. --> route 계산을 자주 할 필요가 없다.Dynamic: 상황에 따라 경로 계산 cost가 바뀐다. --> route 계산을 자주 해야 한다. (임계치를 넘으면, route 계산을 한다.) 5.. 2023. 12. 10. [네트워크] 5.1 개요 Ch5. 네트워크 계층: 제어 평면 Traditional control plane: 하나의 router 안에 control plane과 data plane이 모두 들어 있고, forwarding table을 통해 목적지 기반 forwarding을 한다. SDN control plnae: data plane과 control plane이 분리되어 있고, router(data plane)에서 CA를 통해 control plane의 remote controller로 네트워크 정보를 제공하면, control plane에서 flow-based flow table을 각각의 router에게 내려보낸다. Flow table을 통해 일반화된 forwarding을 한다. 2023. 12. 10. [자료구조] 1205 (2) 14. 해싱 14. 해싱 해싱이란? 추상 자료형 사전 해싱의 구조 해시함수 개방 주소법 체이닝 해싱의 성능 분석 14.1 해싱이란? : 키(key: 저장할 값) --> 해시함수 --> 해시 값 해시 테이블의 구조 나쁜 해시함수 - 예 출처: 이화여자대학교 이숙영교수님 자료구조 2023. 12. 7. [자료구조] 1205 (1) 13. 탐색 (sorting) 탐색이란? 정렬되지 않은 배열에서의 탐색 정렬된 배열에서의 탐색 이진 탐색 트리 AVL 트리 2-3 트리 13.4 이진탐색 트리 (BST: Binary Search Tree) ▶ 이진탐색 vs. 이진탐색 트리 : 근본적으로 같은 원리에 의한 탐색 구조이다. 이진탐색(binary search): 자료들이 순차적으로 저장되어 있다. --> 삽입/삭제가 비효율적이다. 이진탐색 트리(binary search tree): 삽입/삭제가 빠르다. (삽입: leaf에서!) Q. 이진탐색의 경우 자료들이 순차적으로 저장되어 있어서 삽입이 비효율적이다. 이진탐색 트리의 경우 항상 leaf에서 삽입을 하기 때문에 삽입이 효율적이다. 그런데 삭제의 경우, 이진탐색과 이진탐색 트리 모두 정렬된 배.. 2023. 12. 7. [자료구조] 1201 (2) 13. 탐색 13. 탐색 (searching) 탐색이란? 정렬되지 않은 배열에서의 탐색 정렬된 배열에서의 탐색 이진 탐색 트리 AVL 트리 2-3 트리 13.1 탐색이란? : 여러 개의 자료 중에서 원하는 자료를 찾아내는 작업 탐색키(search key): 항목과 항목을 구별해주는 키 13.2 정렬되지 않은 배열에서의 탐색 순차 탐색(sequential search) 순차 탐색(sequential search) : 정렬되지 않은 sequence, si를 처음부터 마지막까지 순차적으로 하나씩 검사하는 방법 개선된 순차 탐색 : 리스트 끝에 탐색키를 저장한다. --> 탐색에 실패하면, 키 값의 인덱스를 반환한다. (개선된 거 아님...) 13.3 정렬된 배열에서의 탐색 이진 탐색(binary search) 색인 순차탐색.. 2023. 12. 6. [자료구조] 1201 (1) 12. 정렬 정렬이란? 선택 정렬 삽입 정렬 버블 정렬 셸 정렬 합병 정렬 퀵 정렬 히프 정렬 기수 정렬 정렬 알고리즘의 비교 12.9 기수 정렬 (Radix Sort) : 레코드를 비교하지 않고 정렬을 수행한다. 시간 복잡도: O(dn) --> n*log(n)을 능가하는 빠른 정렬 방법! - d: 자릿수 : 낮은 자릿수 먼저 분류한 다음, 순서대로 읽어서 다시 높은 자릿수를 분류한다. --> 뒷자리가 정렬되었기 때문에, 앞자리 정렬로 전체 정렬이 가능하다. 버킷(추가 공간): 큐로 구현한다. factor: 몇 번째 자릿수를 추출할지 결정한다. 12.10 정렬 알고리즘의 비교 출처: 이화여자대학교 이숙영교수님 자료구조 2023. 12. 5. [자료구조] 1128 12. 정렬 정렬이란? 선택 정렬 삽입 정렬 버블 정렬 셸 정렬 합병 정렬 퀵 정렬 히프 정렬 기수 정렬 정렬 알고리즘의 비교 12.6 합병 정렬 : 리스트를 두 개의 균등한 크기로 분할하고, 분할된 부분 리스트를 정렬한다. 분할: Data set 크기가 1이 될 때까지 분할한다. 합병: 비교하여, 정렬한다. **합병 시, sorted 배열(임시 추가 공간)을 list 배열(원래 공간)로 복사해야한다! : 분할된 두 배열을 비교하여, 작은 것을 새로운 배열에 넣는다. (Shorted 배열) 추가 공간이 필요하다. (in-place 아님!) **엔트리 개수가 짝수 개인 경우, mid 계산 주의!! Stable sorting Not in-place (임시 추가 공간 필요하다.) 시간 복잡도: O(n*log(.. 2023. 12. 5. [자료구조] 1124 12. 정렬 정렬이란? 선택 정렬 삽입 정렬 버블 정렬 셸 정렬 합병 정렬 퀵 정렬 히프 정렬 기수 정렬 정렬 알고리즘의 비교 12.1 정렬이란? 정렬 알고리즘 분류 (1) 단순하지만 비효율적인 방법 vs. 복잡하지만 효율적인 방법 (2) 내부 정렬 vs. 외부 정렬 우리는 내부 정렬만을 다룬다. Space complexity: 새로운 공간이 필요한가? (3) 안정성 (stability) : 나중에도 순서가 유지될 애들은 처음부터 순서를 유지하면서 정렬하는가? ▶ Stable sort: 삽입정렬 (insertion sort): 정렬되지 않은 곳에서 정렬된 곳으로 삽입한다. (정렬된 곳에서 비교한다.) 버블정렬 (bubble sort): 2개의 레코드를 비교해서 순서를 바꾼다. 따라서 한 단계마다 가장 큰.. 2023. 12. 2. [자료구조] 1121 (2) - 12. 정렬 12. 정렬 정렬이란? 선택 정렬 삽입 정렬 버블 정렬 셸 정렬 합병 정렬 퀵 정렬 히프 정렬 기수 정렬 정렬 알고리즘의 비교 12.1 정렬이란? : 데이터들을 특정 순서(오름차순, 내림차순 등)로 정리하는 것 정렬의 대상 : 일반적으로 정렬시켜야 될 대상은 레코드(record)이다. 정렬 알고리즘 개요 출처: 이화여자대학교 이숙영교수님 자료구조 2023. 11. 28. 이전 1 2 3 4 5 ··· 12 다음
