본문 바로가기

5장 컴퓨터 과학61

[자료구조] 우선순위 큐 (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.
[알고리즘] 이진 트리 순회(Binary Tree Traversal) 전위 순회(Preorder Traversal) 이진 트리는 트리의 일종으로 일반적인 트리에 대한 전위 순회 알고리즘이 똑같이 적용될 수 있다. template void preorder(Node* node) { if (node == nullptr) return; coutGetLeft()); postorder(node->GetRight()); cout 2021. 6. 11.
[알고리즘] 트리 순회(Tree traversal) 깊이와 높이 node를 트리 T의 노드라 하자. node의 깊이(depth)는 node의 조상의 수이다. 만약 node가 루트이면, node의 깊이는 0이 된다. 그렇지 않으면, node의 깊이는 node의 부모의 깊이에 1을 더한 것과 같다. template int depth(Node* node) { if (node->is_root()) return 0; return 1+depth(node->parent()); } 트리 T에서 node의 높이(height)도 재귀적으로 정의된다. 만약 p가 외부 노드이면 p의 높이는 0이다. 그렇지 않으면 node의 높이는 node의 자식의 높이 중 가장 높은 값에 1을 더하면 된다. template int height(Node* node) { if (node->is_.. 2021. 6. 10.
[컴퓨터 네트워크] 무선 LAN과 무선 매체 무선 LAN 무선 LAN 기술이란 무선접속장치인 AP(Access Point)가 설치된 곳에서 일정 거리 안에 있는 다수의 컴퓨터를 무선으로 연결하는 것이다. 전자기파 기반의 FHSS(Frequency Hopping Spread Spectrum, 주파수 도약 확산 스펙트럼), DSSS(Direct Sequence Spread Spectrum, 직접 시퀀스 확산 스펙트럼) 방식, OFDM(Orthogonal Frequency Division Multiplexing, 직교 주파수 분할 다중화) 방식 등을 사용해 제한된 지역 안에 있는 디바이스끼리 데이터통신을 할 수 있다. 무선 LAN을 구성하는 방식에는 하부구조(Infrastructure) 방식과 애드혹(Ad-hoc) 방식이 있다. 하부구조 방식 하부구조 .. 2021. 6. 10.
[컴퓨터 네트워크] LAN 프로토콜 LAN 프로토콜의 구조 LAN은 빌딩이나 대학 캠퍼스 정도 범위로 규모와 거리를 제한한 채 PC, 서버, 프린터, 라우터, 워크스테이션 등을 연결해 구성한 네트워크 시스템이다. 전송지 호스트 컴퓨터와 수신지 호스트 컴퓨터 사이의 거리를 수 km 이내로 제한함으로써 고속의 데이터 전송이 가능하고 데이터 전송률도 높다. 가장 널리 사용되는 LAN 기술은 이더넷(Ethernet)이다. 이더넷 기술은 IEEE 802.3 표준안으로 승인된 기술이다. 물리 계층에서 사용하는 동선이나 신호의 형태, 코드화 비트이 형태처럼 전기적, 기계적 틍성에 대한 표준을 정의한다. 데이터링크 계층은 오류 없이 패킷을 전송하는 계층으로, MAC(Media Access Control) 부계층과 LLC(Logical Link Contr.. 2021. 6. 10.
반응형

티스토리툴바