본문 바로가기
[알고리즘] 이진 트리 순회(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.
[알고리즘] 버블 정렬(Bubble Sort) 버블 정렬은 각 단계에서 노드 전체를 검사한다. 차례대로 각 노드에 대해 다음 노드와의 크기를 비교하여 위치를 바꾸고 이런 과정을 원소의 개수만큼 반복한다. 특성 첫 번째 과정에서 가장 큰 원소를 만나면 마지막 노드에 도달할 때까지 계속 교환이 이루어진다. 두 번째 과정에서 두 번째로 큰 원소를 만나면 끝에서 두 번째 노드에 도달할 때까지 계속 교환이 이루어진다. 일반적으로 각 i번째 과정이 끝나면 끝에서 i개의 원소들은 최종 위치에 도달한 것이다. C++ 구현 template void bubble_sort(RandomIt first, RandomIt last) { while (first != last--) for (RandomIt it = first; it *.. 2021. 6. 9.
반응형

티스토리툴바