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 • 연결 리스트로 된 두 집합을 합칠 때 작은 집합을 큰 집합의 뒤에 붙인다 – 대표 원소를 가리키는 포인터 갱신 작업을 최소화하기 위한 것 [예시] 다음의 상호배타적 집합이 연결리스트로 완성되기까지의 ..