[컴퓨터 네트워크] 네트워크 계층과 라우팅 네트워크 계층과 라우팅 네트워크 계층의 주된 역할은 데이터 패킷을 전송지에서 수신지까지 보내는 것이다. 송수신 호스트 사이의 패킷 전달 경로를 결정하는 기능을 라우팅(Routing)이라고 한다. 라우팅을 수행하는 장치는 중계 라우터(Intermediate Router)이고, 네트워크 구성 형태에 관한 정보를 관리하는 공간은 라우팅 테이블(Routing Table)이다. 라우팅 테이블은 라우터가 패킷을 경우할 최적의 경로를 찾기 위한 가장 기본적인 도구로, 수신지 주소, 수신지 주소까지 소요되는 비용인 메트릭(Metric), 다음 라우터 혹은 게이트웨이, 그리고 인터페이스에 관한 내용 등이 들어있다. 라우터는 라우팅 테이블에 있는 정보를 참조해 경로를 설정한 후 데이터 패킷을 중계해 서로 다른 네트워크를 .. 2021. 6. 11. [알고리즘] 힙 정렬(Heap Sort) 힙을 이용하여 힙 정렬을 할 경우 정렬 시간이 $n\log{n}$으로 크게 감소한다. C++ 구현 #include using namespace std; template void heap_sort(RandomIt first, RandomIt last) { make_heap(first, last); for (RandomIt it = last; it != first; --it) pop_heap(first, it); } algorithm 헤더 파일의 heap과 관련된 함수를 이용하였다. [first, last) 범위의 원소를 오름차순으로 힙 정렬하는 코드이다. 2021. 6. 11. [자료구조] 힙 (Heap) 개념 힙은 우선순위 큐를 효율적으로 구현하기 위한 자료구조로 이진 트리의 일종이다. 성질 힙-순서 특성(Heap-Order Property): 힙 T에서 루트를 제외한 모든 노드 v에 대하여, v에 저장된 키는 v의 부모에 저장된 키보다 크거나 같다.(단, 힙의 정의에 따라 부모 노드에 최대값이 저장될 수도 있다.) 완전(complete) 이진 트리 특성: 만약 레벨 0, 1, 2, ..., h-1들이 가질 수 있는 최대 수의 노드를 포함하고 (즉, 레벨 i는 2i 노드를 포함, 이때 0≤i≤h-1) 레벨 h-1에서 모든 내부 노드는 외부 노드들의 왼쪽에 위치한다면, 높이 h인 이진 트리 T는 완전하다. 힙의 높이(height): T의 높이를 h라 할 때 T의 마지막 노드는 레벨 h에 있으며 같은 레벨의.. 2021. 6. 11. [알고리즘] 선택 정렬(Selection Sort) 선택 정렬은 n개의 원소를 가진 배열에서 i 번째 단계에서 [i, n) 번째 원소 중에 최소값을 구해 i 번째 원소와 위치를 바꾼다. 특성 일반적으로 각 i번째 과정이 끝나면 앞에서 i개의 원소들은 최종 위치에 도달한 것이다. C++ 구현 template void selection_sort(RandomIt first, RandomIt last) { for (RandomIt it1 = first; it1 != last-1; ++it1) { RandomIt min = it1; for (RandomIt it2 = it1+1; it2 != last; ++it2) if (*it2 < *min) min = it2; auto temp = *it1; *it1 = *min; *min = temp; } } template.. 2021. 6. 11. [자료구조] 우선순위 큐 (Priority Queue) 개념 우선순위 큐(priority queue)는 임의의 순서로 입력된 우선순위된 원소들을 저장하고 우선순위에 따라 출력하는 추상 데이터 타입이다. 즉 언제든지 저장된 원소들 중 가장 우선순위가 높은 원소가 삭제된다. 성질 우선순위 큐는 항상 적용될 수 있는 비교 규칙이 필요하다. ≤으로 표기되는 비교 규칙이 항상 적용되기 위해서는 전체 순서(total order) 관계를 만족해야 한다. 전체 순서 관계는 모든 쌍의 두 키에 대하여 다음과 같은 특성을 만족한다. 반사성(Reflexive property): $k \le k$ 비대칭성(Antisymmetric property): 만약 $k_{1} \le k_{2}$ 이고 $k_{2} \le k_{1}$ 일 경우, $k_{1}=k_{2}$ 이행성(Transit.. 2021. 6. 11. 이전 1 ··· 6 7 8 9 10 11 12 ··· 26 다음 반응형
