D플립플롭 입력값 D가 바로 다음 상태가 되는 플립플롭 특성식: 플립플롭의 논리 특성을 대수학적으로 표현 D 플립플롭 Q(t+1)=D D플립플롭 회로 분석 입력식 == 상태식 A(t+1)=Ax + Bx B(t+1)=A'x 출력식 y=(B+A)x' 상태표 예) 현재상태가 0, 1이고 입력 1인경우 -> 다음상태가 1, 1 출력은 0 상태도표 [예제1] 다음 D플립플롭의 회로를 분석하시오. [예제2] 다음 D플립플롭의 회로를 분석하시오. D플립플롭 회로 설계 [예제1] D플립플롭을 이용하여 순차 검출기 설계하기 1. 상태도표 더보기 2. 상태표 3. 입력식과 출력식 4. 회로도 [예제2] D플립플롭을 이용하여 3신호(도, 레, 미) 반복기 설계 더보기 [예제3] D플립플롭을 이용하여 7-segment 0~5..

JK플립플롭 세가지 동작을 수행 세트(J), 리세트(K), 보수화(J=K=1) D = JQ′+K′Q 특성식: 플립플롭의 논리 특성을 대수학적으로 표현 JK 플립플롭 Q(t+1)=JQ’+K’Q JK플립플롭 회로 분석 입력식 J_A = B K_A = Bx' J_B = x' K_B = A'x + Ax' 특성식 Q(t+1)= JQ′+K′Q 상태식 ( 특성식으로부터 유도, J와 K에 입력식 J_A, J_B, K_A, K_B 대입 and Q에 상태 A, B 대입) A(t+1) = J_AA' + K_A'A B(t+1) = J_BB' + K_B'B 출력식 [예제1] 1) 입력식을 구한다 J_A = x K_A = A 2) 상태식을 구한다 (특성식을 이용하여) A(t+1) = JQ′+K′Q = xA' + A'A = xA'..

T플립플롭 입력값 T와 현재 상태 값을 XOR한 값이 다음 상태가 됨. (입력값이 바로 다음 상태가 되는 D플립플롭가 차별점) D = TQ' + T'Q 어떤 입력값이든 0과 XOR하면 입력값의 변화 없음. 어떤 입력값이든 1과 XOR하면 입력값이 보수화됨. 즉, T플립플롭은 Toggle기능을 수행함. 특성식: 플립플롭의 논리 특성을 대수학적으로 표현 T 플립플롭 Q(t+1)=TQ’+T’Q T플립플롭 회로 분석 입력식 T_A=Bx, T_B=x 특성식 Q(t+1)= TQ′+T′Q 상태식 ( 특성식으로부터 유도, T에 입력식 T_A, T_B 대입 and Q에 상태 A, B 대입) A(t+1)=T_AA′+T_A′A B(t+1)=T_BB′+T_B′B 출력식 y=AB [예제1] 다음 D플립플롭 회로를 T플립플롭으로..

최단 경로 • 조건 – 간선 가중치가 있는 유향 그래프 – 무향 그래프는 각 간선에 대해 양쪽으로 유향 간선이 있는 유향 그래프로 생각할 수 있다 • 즉, 무향 간선 (u, v)는 유향 간선 (u, v)와 (v, u)를 의미한다고 가정하면 된다 • 두 정점 사이의 최단경로 – 두 정점 사이의 경로들 중 간선의 가중치 합이 최소인 경로 – 간선 가중치의 합이 음인 싸이클이 있으면 문제가 정의되지 않는다 • 단일 시작점 최단경로 – 단일 시작점으로부터 각 정점에 이르는 최단경로를 구한다 다익스트라 알고리즘 : 음의 가중치를 허용하지 않는 최단경로 벨만-포드 알고리즘 : 음의 가중치를 허용하는 최단경로 싸이클이 없는 그래프의 최단경로 • 모든 쌍 최단경로 – 모든 정점 쌍 사이의 최단경로를 모두 구한다 플로이..

깊이 우선 탐색(DFS: depth first search) • 한 방향으로 갈 수 있을 때까지 가다가 더 이상 갈 수 없게 되면 가장 가까운 갈림길로 돌아와서 이 곳으로부터 다른 방향으로 다시 탐색 진행 • 되돌아가기 위해서는 스택 필요 (재귀 함수 호출로 묵시적인 스택 이용 가능) 실행단계 알고리즘 DFS(G) { for each v ∈ V visited[v] ← NO; for each v ∈ V if (visited[v] = NO) then aDFS(v); } aDFS (v) { visited[v] ← YES; for each u ∈ L(v) # L(v) : 정점 v의 인접 리스트 if (visited[u] = NO) then aDFS(u); } 시간 복잡도 O(V(V-1)), Θ(|V|+|E|) ..

상호 배타적 집합의 처리 ※ 교집합은 다루지 않는다. • 지원할 연산 – Make-Set(x): 원소 x로만 이루어진 집합을 만든다 – Find-Set(x): 원소 x를 가지고 있는 집합을 알아낸다 – Union(x, y): 원소 x를 가진 집합과 원소 y를 가진 집합의 합집합 연결 리스트를 이용하는 방법과 트리를 이용하는 방법 연결리스트를 이용한 집합 처리 • 같은 집합의 원소들은 하나의 연결 리스트로 관리한다 • 연결 리스트의 맨 앞의 원소를 집합의 대표 원소로 삼는다 Weight를 고려한 Union • 연결 리스트로 된 두 집합을 합칠 때 작은 집합을 큰 집합의 뒤에 붙인다 – 대표 원소를 가리키는 포인터 갱신 작업을 최소화하기 위한 것 [예시] 다음의 상호배타적 집합이 연결리스트로 완성되기까지의 ..

해시 테이블 해시 테이블 원소가 저장될 자리가 원소의 값에 의해 단 한번의 계산으로 결정되는 자료구조 (검색 트리와 상반) 평균 상수 시간에 삽입, 삭제, 검색 매우 빠른 응답을 요하는 응용에 유용 - 예 : 119 긴급구조 호출과 호출번호 관련 정보 검색, 주민등록 시스템 해시 테이블은 최소 원소를 찾는 것과 같은 작업은 지원하지 않는다 해시함수 • 입력 원소가 해시 테이블에 고루 저장되어야 한다 • 계산이 간단해야 한다 • 여러 가지 방법이 있으나 가장 대표적인 것은 나누기 방법과 곱하기 방법이다 나누기 방법 Division Method – h(x) = x mod m – m: 해시 테이블 사이즈. 대개 소수임. 곱하기 방법 Multiplication Method – h(x) = (xA mod 1) *..

다차원 검색 트리 KD-트리 • 검색키가 두 개 이상의 필드로 이루어진 검색 • 3개의 다차원 검색트리와 하나의 다차원 저장/검색 방법 소개 – KD-트리 – KDB-트리 – R-트리 – 그리드 파일 KD-Tree • 각 레벨에서 필드를 번갈아가며 검색에 사용한다 − 한 level에서는 하나의 필드만 사용한다 − 총 k개의 필드를 사용하는 검색이라면, k개의 level을 내려가면 검색에 사용하는 필드가 일치한다 1레벨 : x축 비교 -> 2레벨 : y축 비교 -> 3레벨 : x축 비교 -> 4레벨 : y축 비교 ... - 만약 [10|60] 노드를 검색 하고자 한다면 다음과 같은 순서가 된다. (1) 1레벨 x축(50)보다 작으므로(10) A의 왼쪽 자식으로 내려간다. (2) 2레벨 y축(70)보다 작으..

다진 검색 트리 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