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)보다 작으..