B-Tree B-트리 * 검색 트리의 종류 (URL) - Balanced-Tree의 약자로, 디스크 환경에서 사용하기 적합한 Balnced-외부 다진 검색 트리이다. - Child의 수를 늘리고, Balance를 유지하여 Tree의 Depth를 줄여 검색시간을 줄이는 것을 목표로 한 구조이다. - 일반적으로, B-Tree의 Node 하나의 크기를 Disk Block 크기와 일치시켜서 CPU가 Disk에 접근하는 I/O Access 횟수를 최소화한다. (컴퓨터는 Disk의 특정 데이터에 접근할 때, Disk내에서 특정 데이터가 위치한 Disk Block 전체를 Loading한다.) (I/O Access는 CPU의 입장에서 매우 큰 시간이 소요되는 Task이다.) * Memory Management (URL..
DHCP Dynamic Host Configuration Protocol 동적 호스트 구성 프로토콜 - 처음으로 부팅했거나, 디스크가 없는 컴퓨터에게 Communication에 필요한 4가지 요소를 제공하기 위한 Client-Server Protocol(Client-Server Program)이다. (Standard Network Protocol이다.) - Host가 접속과 갱신을 빈번히 행하는 Home Internet, Wireless LAN 환경에서 자주 사용된다. ※ Communication에 필요한 4가지 요소 (Network 구성을 위한 Parameters) 1) Host 자기 자신의 IP주소 2) Network Subnet Mask - Routing 과정에서 메시지의 Netowrk-ID를 알기..
Protocol Layer 프로토콜 레이어링 - 단순한 Communication에서야 하나의 간단한 Protocol만 있으면 되겠지만, 복잡한 Communication을 위해서는 한 Task를 여러 개의 Layer에서 각기 나눠서 처리하는 것이 효율적일 것이다. - 이렇게 한 Task를 여러 Layer에서 각자의 Protocol대로 처리하게 하는 방식을 Protocol Layering이라 한다. Three-Layer Protocol (삼중 레이어 프로토콜) Principles of Protocol Layering - 프로토콜 레이어링 시, 준수해야 하는 원칙에는 크게 두 가지가 있다. 1. Bidirectional Communication - 각각의 Layer에서는 전송에 대한 Task과 수신에 대한 T..
Boyer-Moore Algorithm 보이어-무어 알고리즘 * String Matching Algorithms (문자열 매칭 알고리즘) (URL) - 전체 문자열 \(\texttt{string[1...m]}\)에서 부분 문자열 \(\texttt{pattern[1...m]}\)을 찾아내는데, 최악의 경우에는, \(\Theta(n*m)\) 시간 동안 수행되지만, 평균적으로 \(\Theta(n)\)과 \(\Theta({n \over m})\) 사이의 시간 동안 수행되어 실무에서 KMP Algorithm보다 더 자주 쓰이는 알고리즘이다. (대체로, \(\Theta({n \over m})\)에 더 가까운 성능을 보인다고 한다.) Mechanism (원리) - Mismatching이 발생했을 때, Bad-Char..
Rabin-Karp Algorithm 라빈-카프 알고리즘 * String Matching Algorithms (문자열 매칭 알고리즘) (URL) - 전체 문자열 \(\texttt{string}\) 내에서 부분 문자열 \(\texttt{pattern}\)을 찾아내는데, Hash Algorithm을 이용하여 \(\texttt{string}\)과 \(\texttt{pattern}\)의 해시값을 비교하는 방법이다. Mechanism (원리) 1. 부분 문자열 \(\texttt{pattern}\)에 해당되는 수치값(해시값)을 계산한다. - \(\texttt{pattern}\)을 구성하는 Alphabet Set을 \(\Sigma\) 라 하면, \(\texttt{pattern}\)에 해당되는 해시값 \(\mathrm..
