4Legs_Archives

효율적인 이진탐색 트리 (Efficient BST) 다음 두 이진탐색 트리를 보자. 첫 번째 BST는 25를 검색하기 위해 6번의 비교가 필요하다. 하지만 두 번째 BST는 3번의 비교로도 검색할 수 있다. 모든 노드를 Search하는 데 비교 횟수를 비교하면, 우리는 두 번째로 제시된 BST가 Search 수행이 더 효율적이라 할 수 있다. BST가 효율적이기 위해선 가능한 트리의 높이가 최소가 되어야 한다. 그러기 위해선 각 서브트리들이 어느 한쪽으로 치우치지 않고, 균형을 잘 이루어야 할 것이다. 이것이 AVL 트리의 핵심이다. 트리의 균형 (Balance Factor) 우리는 AVL 트리를 사용하기 위해 각 노드마다 균형 인수(BF, Balance Factor)를 둔다. 균형 인수는 한 노드에 대..

이진 탐색 트리 (Binary Search Tree) 딕셔너리(Dictionary)는 페어(Pair)의 모음으로, 각 페어는 Key값과 관련된 다른 값들로 이루어져 있다. 일반적인 딕셔너리 구조는 실제로는 그렇지 않음에도 불구하고 중복된 키값이 없다 가정하지만, 이진 탐색 트리에서는 이러한 가정 없이 쉽게 중복 키값에 대해 확장할 수 있는 자료구조이다. 정의 이진 탐색 트리는 이진 트리의 한 종류로써, 다음 조건들을 만족하는 자료구조이다. ① 각 노드는 구분되는 하나의 키값을 갖는다. ② 왼쪽 서브트리의 모든 키값들은 root의 키값보다 작다. ③ 오른쪽 서브트리의 모든 키값들은 root의 키값보다 크다. ④ 왼쪽, 오른쪽 서브트리 각각 또한 이진 탐색 트리이다. 탐색 (Search) 삽입 (Insert..

힙(Heap) 구조란? 힙은 우선순위 큐를 구현하는 데 자주 이용된다. 이러한 자료구조에서는 제거되는 원소가 모든 원소들 중에서 가장 높은(또는 낮은) 우선도를 갖는다. 힙에 대한 정의는 다음과 같다. 본 게시물은 최대 힙을 기준으로 작성했다. 정의 최대 트리(Max Tree)는 각 노드의 Key 값이 그 노드의 자식 노드보다 항상 큰 노드이다. 최대 힙(Max Heap)은 최대 트리이면서 동시에 완전 이진 트리인 자료구조를 의미한다. 삽입 (Insertion) 힙 구조에서 삽입은 다음과 같이 이루어진다. 삭제 (Deletion) 힙에서의 삭제는 다음과 같이 이루어진다. ※ 본 게시글은 『Fundamentals of Data Structures in C』 를 참고하여 작성되었습니다.

정렬(Sorting)이란? 정렬은 원소(element)들을 일정한 기준을 통해 순서대로 나열하는 것이다. 정렬은 탐색(Search), 병합(Merge) 등 정렬된 상태에서 올바르게 동작하는 다른 알고리즘을 최적화하는 데 중요한 역할을 한다. 정렬 알고리즘은 이러한 정렬을 진행하는 방식을 정의한 알고리즘을 말한다. 이번 포스팅에서는 기본적인 정렬 알고리즘 5가지에 대해 알아보자. 최악의 경우 (Worst case) Worst case는 정렬 알고리즘에 대해 일반적으로 시간복잡도에 대한 최악의 경우는 그 알고리즘이 최대 실행시간으로 동작하는 경우를 말한다. 공간 복잡도에 대해서는 알고리즘이 최대 메모리를 사용하며 동작하는 경우를 의미한다. 안정성 (Stability) 정렬 알고리즘이 안전성을 가진다는 것은 ..

DLC (Data Link Control) DLC는 Point-to-Point, Broadcast 링크 모두에 포함된 하위 계층이었다. DLC는 링크의 종류에 관계없이 두 노드에 대한 통신 과정을 다룬다. DLC는 Framing, 흐름 & 오류 제어 기능을 포함한다. Framing 데이터링크 계층은 비트들을 프레임의 형태로 감싸 다른 프레임들과 구분한다. 이러한 Framing은 물리 계층으로부터 전달된 비트들을 어떻게 조직하는지를 의미하며, 송신자와 수신자의 주소를 추가함으로써 메시지를 분리한다. 이 목적지 주소를 통해 송신자는 수신자가 메시지를 받았다는 응답을 돕는다. 고정 크기 프레임 (Fixed-size Frame) : ATM이나 WAN에서 사용되며, 프레임 간의 경계를 지정할 필요가 없다. 가변 ..

오류의 유형 (Error Types) 단일 비트 오류 (Single-bit Error) 주어진 데이터 단위(문자 하나, 또는 패킷 전체 등)에서 오직 하나의 비트가 변경된 오류이다. 버스트 오류 (Burst Error) 데이터 단위에서 둘 이상의 연속적인 비트가 변경된 오류이다. 중복성 (Redundancy) 중복성은 에러를 감지하고 수정하는 것에 있어 핵심적인 개념이다. 우리는 오류를 검출하거나 수정하기 위해 데이터에 추가적인 비트를 보낸다. 이를 중복 비트(Redundant bit)라 하며, 이러한 중복 비트들은 송신자에 의해 더해지거나 수신자에 의해 제거된다. 코딩 (Coding) 송신자는 실제 데이터 비트와 관련된 중복 비트들을 전송한다. 수신자는 이 두 비트들 사이의 관계를 확인해 오류를 검출하..

ARP (Address Resolution Protocol) 한 노드가 IP 데이터그램을 링크를 통해 다른 노드로 보내고자 할 때, 데이터그램은 수신 노드의 IP 주소를 포함한다. 하지만 IP 주소는 네트워크 계층의 주소이기 때문에, 데이터링크 계층에서 링크를 통해 프레임을 전달하는 데에는 그다지 유용하지 않다. 따라서 우리는 다음 노드(수신 노드)의 데이터링크 계층 주소가 필요하다. ARP는 네트워크 계층에 속해 있으며, IP 주소를 그에 상응하는 MAC 주소로 변환해준다. 다음은 Alice와 Bob이 통신하는 과정을 통해 ARP가 어떻게 동작하는지를 그림으로 나타낸 것이다. 그림에서 N으로 표현된 것이 네트워크 계층의 주소, 즉 IP주소이고 L로 표현된 것이 데이터링크 계층의 주소이다. 네트워크 계층..

인터넷은 연결 장치들이 함께 붙어 있는 네트워크들의 집합이라 할 수 있다. 호스트로부터 다른 호스트로 보내지는 패킷은 이러한 네트워크를 지나간다. 이 카테고리에서는 데이터링크 계층에서의 통신을 알아본다. 노드와 링크 (Nodes and Links) 데이터링크 층에서의 통신은 노드와 노드 사이에서 이루어진다. (Node-to-Node) 인터넷의 한 지점에 존재한느 데이터 단위는 많은 네트워크들(LAN, WAN)을 통해 다른 지점으로 보내진다. 이러한 LAN, WAN들은 라우터에 의해 연결되어 있다. 우리는 라우터를 노드(Node)로 칭하고, 라우터 간의 네트워크를 링크(Link)라 칭한다. 서비스 (Service) 데이터링크 계층은 물리 계층과 네트워크 계층 사이에 존재한다. 따라서, 데이터링크 계층은 물..

파일 (File) 운영체제는 물리적 메모리의 한 부분을 논리적 저장 단위인 파일로 간주한다. 파일은 보조 저장장치에 기록된 관련된 정보들의 집합이다. 사용자의 관점에서 파일은 보조 저장장치의 최소 할당량이다. 따라서 데이터는 파일 안에 존재하지 않으면 보조 기억장치에 기록될 수 없다. 파일은 프로그램과 데이터를 표현한다. 데이터 파일은 숫자거나, 문자거나, 이진 데이터를 담은 파일일 수 있다. 파일의 형태는 자유롭지만 일반적으로 파일은 비트, 바이트 등의 연속으로, 사용자에 의해 의미가 정해진다. 즉 파일의 정의는 매우 광범위하다. 파일 속성 (File Attributes) 파일은 사용자의 편의를 위해 문자열로 나타낸 이름을 붙여 관리된다. 파일의 이름 등을 포함한 파일의 속성들은 다음과 같다. 이름 (..

디지털 신호의 전송 우리는 어떻게 디지털 신호를 A지점으로부터 B지점까지 보낼 수 있을까? 우리는 디지털 신호를 변조(Modulation)해 다음 두 가지의 방법으로 전송할 수 있다. 기저 대역 전송 (Baseband Transmission) Baseband Transmission은 디지털 신호를 아날로그 신호로 변환하지 않고 전송하는 것을 의미한다. Baseband Transmission는 로우패스 채널(Low-Pass Channel)을 필요로 한다. 로우패스 채널은 0부터 시작하는 대역폭을 갖는 채널을 말한다. 따라서 하나의 채널에 대한 전용 매체를 가진 경우이다. 즉, 한 번에 두 대의 컴퓨터만을 연결할 수 있는 경우이다. 넓은 대역폭을 가진 로우패스 필터 전송 과정에서 아날로그 신호가 디지털 신호..