다진 검색 트리 B-tree • 디스크의 접근 단위는 블록(페이지) • 디스크에 한 번 접근하는 시간은 수십만 명령어의 처리 시간과 맞먹는다 • 검색트리가 디스크에 저장되어 있다면 트리의 높이를 최소화하는 것이 유리하다 • B-트리는 다진검색트리가 균형을 유지하도록 하여 최악의 경우 디스크 접근 횟수를 줄인 것이다 B-tree는 균형잡힌 다진검색트리로 다음 성질을 만족한다. - 루트는 1~k개의 키를 갖는다 - 루트를 제외한 모든 노드는 floor(k/2) ~ k개의 키를 갖는다. - 모든 리프 노드는 같은 깊이를 갖는다. - 키가 하나도 없는 트리로 B-tree이다. B-tree 노드 삽입 알고리즘 # t : 트리의 루트 노드 # x : 삽입하고자 하는 키 BTreeInsert(t, x) { x를 삽입..

검색 알고리즘 기타 개념 > 레코드record – 개체에 대해 수집된 모든 정보를 포함하고 있는 저장 단위 – e.g., 사람의 레코드 주민번호, 이름, 집주소, 집 전화번호, 직장 전화번호, 휴대폰 번호, 최종 학력, 연소득, 가족 상황 등의 정보 포함 > 필드field – 레코드에서 각각의 정보를 나타내는 부분 – e.g., 위 사람의 레코드에서 각각의 정보를 나타내는 부분 > 검색키search key 또는 키key – 다른 레코드와 중복되지 않도록 각 레코드를 대표할 수 있는 필드 – 키는 하나의 필드로 이루어질 수도 있고, 두 개 이상의 필드로 이루어질 수도 있다 > 검색트리search tree – 각 노드가 규칙에 맞도록 하나씩의 키를 갖고 있다 – 이를 통해 해당 레코드가 저장된 위치를 알 수..

순차 논리회로 - 출력은 입력과 순차회로의 현재 상태에 관한 함수 - 현재 상태는 기억소자에 의해 주어짐 순차 회로의 두 유형 - 동기식(syncronous) : 규정된 각 시점에서의 입력신호만 이용하여 출력 결정 - 비동기식(asyncronous) : 모든 시점에서의 입력신호에 대해 출력 결정, 입력 신호가 변하는 순간에 출력도 변함 클럭 펄스 - 동기식 순차회로에서 동기화를 이루는 규정된 시점을 알려주는 신호 클럭에 동기화된 순차회로 (Clocked sequential circuit) - 저장요소의 입력으로 클럭 신호를 사용하여 동기화를 맞추는 순차회로 플립플롭 (flip-flops) - 클럭형 순차회로에 쓰이는 저장소자 - 한 비트의 정보를 저장할 능력을 갖는 2진 저장소자 - 여러 비트를 저장하려..

10진 가산기 • 직접 10진수계로 산술연산을 하는 컴퓨터나 계산기는 2진 코드 형태로 10진수를 표현한다. • 이러한 컴퓨터에서 가산기는 코드화된 10진수를 입력 받아 코드화된 10진수를 출력한다. • 예) BCD 코드에 대한 10진 가산기 2진 곱셈기 • 2bit x 2bit = 4bit(max) • (K비트) x (J비트) (K x J)개의 AND 게이트, (J-1)개의 K비트 가산기 필요 크기 비교기 • xi=1. i번째 비트에 있는 짝이 같을 때에만 • (A=B)=x3x2x1x0 • (A>B)=A3B3′+x3A2B2′+x3x2A1B1′+x3x2x1A0B0′ • (A

논리회로 (logic circuit) 조합회로(combinational circuit) - Boole 함수의 집합을 논리적으로 구현하는 동작을 수행 - 출력이 입력값에 따라 결정됨 순차회로(sequential circuit) - 출력이 저장된 값과 입력 값에 따라 달라짐. - 출력 값이 현재 입력 값 뿐만 아니라 이전 입력값에 따라 달라짐. - 회로의 동작을 입력 값과 저장된 값의 시간순서로 정의할 수 있음. 조합회로 조합회로 • 출력값이 현재의 입력값에 의해 결정됨 • 입력변수와 논리 게이트, 출력 변수들로 구성됨 n개의 입력변수에 대해 2^n개의 2진 입력조합이 가능 각 입력조합에 대하여 하나의 출력 출력 변수 하나를 Boole 함수로 표현할 수 있음. 디지털 시스템을 설계하는데 자주 사용되는 조합회..

선택 정렬 수행시간 최악: (n-1)+(n-2)+···+2+1 = Θ(n2) 평균: (n-1)+(n-2)+···+2+1 = Θ(n2) • 각 루프마다 – 최대 원소를 찾는다 – 최대 원소와 맨 오른쪽 원소를 교환한다 – 맨 오른쪽 원소를 제외한다 • 하나의 원소만 남을 때까지 위의 루프를 반복 # 일반 selectionSort(A[], n) { # A[1 ... n]을 정렬한다 for last