복습노트 복습노트

자료구조인 그래프를 탐색하는 방법입니다. #define MAX_VERTICES 50 typedef struct node* node_pointer; typedef struct node { int vertex; node_pointer link; }; node_pointer graph[MAX_VERTICES]; int n = 0; 기본 설정입니다. 변수 n은 현재 사용하고 있는 정점의 갯수 를 나타냅니다. DFS (깊이 우선 탐색) Root node 한개를 선택해 하나의 자식 노드를 집중적으로 계속 탐색하고 탐색이 끝나면 Root node의 다음 자식 노드를 선택해 또 탐색하는 방법입니다. void dfs(int v) { node_pointer w; visited[v] = TRUE; printf("%5d", ..

Union은 각각의 tree가 서로 연결되어 있지 않고 독립적으로 있을때 서로 독립되어 있는 tree를 연결시키는 작업입니다. 여기서 Disjointset이란 서로소 집합이란 의미로 서로 집합된 부분에서 중복되는 수가 없어야 합니다. 예를들어 다음과 같은 tree가 있을때 우리는 parent 배열을 만들 수 있습니다. S1의 Root는 0이고 S2의 Root는 4고 S3의 Root는 2입니다. 따라서 parent 배열에서 인덱스번호 0, 4, 2는 -1입니다. 즉, 대장이라는 의미입니다. S1의 자식 node 6, 7, 8은 0을 가리키므로 parent배열 6, 7, 8은 0입니다. 나머지 tree들도 마찬가지 입니다. 물론 이렇게 union&find를 할 수 있지만 이번시간에는 ,weighted uni..

Multiplexer (MUX)는 다수의 입력중 특정 조건에 의해 한개의 입력만 선택해 출력하는 것입니다. 그래서 mux는 data selector 라고도 불립니다. 왼쪽의 그림은 4-input multiplexer 입니다. 2개의 data select line 이 있고 4개의 data input line이 있고 1개의 single output line이 있습니다. 2개의 data select line S0, S1 에 따라 data input을 결정합니다. 예를들어 S1S0 = 00 이면 D0 가 출력되고 S1S0 = 01 이면 D1이 출력되고 S1S0 = 10 이면 D2가 출력되고 S1S0 = 11 이면 D3가 출력됩니다. 따라서 다음과 같은 bool 식이 성립 됩니다. Demultiplexer (DE..

BCD-to-Binary Conversion ex) 8-bit BCD code conversion : 87 = 10000111 (이 숫자는 BCD 코드 입니다.) 이제 Binary code로 바꾸겠습니다. 87 = 80 +7 = 80 + 4 + 2 + 1 입니다. 다음 표에 따라 80 = 1010000 4 = 0000100 2 = 0000010 1 = 0000001 이를 모두 더하면 1010111 이 됩니다. 따라서 어떤수를 8-bit라 볼때 B3B2B1B0A3A2A1A0 이 되는 것입니다. EX) Convert the BCD numbers to binary. (a) 00100111 (27) 1이 B1, A2, A1, A0 자리에 있으므로 0010100 (B1) + 0000100 (A2) + 000001..

Decoder 디코더는 어느 특정 조합된 입력을 발견하고 이를 출력을 통해 해독하는 역할을 합니다. 예를 들어 입력으로 1001이라는 수가 들어오면 AND Gate에 의해 1을 출력합니다. AND 는 모든 입력이 1이어야 1이 되므로 입력을 예측할 수 있습니다. 만약 NAND 가 AND 자리에 대체된다면 출력이 0이 된다면 입력을 1001로 해독할 수 있습니다. The 4-bit Decoder 4개의 bit의 조합을 모두 해독하기 위해 16개의 decoding gate가 필요합니다 (2^4 = 16) 왼쪽 진리표는 4-bit decoder의 진리표입니다. 4-bit decoder는 4-line-to-16-line decoder라고 불리고 (4개의 입력 16개의 출력) 또는 1-of-16 decoder라고..

binary search tree는 우리가 이전에 배운 탐색 알고리즘을 용이하게 하기 위한 자료구조입니다. 각 root node의 왼쪽은 root node보다 작고 오른쪽은 root node보다 큰 수가 들어가게 되면서 어떤 수를 찾을 때 root node와 비교해주어 작으면 왼쪽으로가고 크면 오른쪽으로 가면서 탐색을하게 됩니다. typedef struct node* tree_pointer; typedef struct node { int data; tree_pointer left, right; }node; 다음과 같은 tree 선언을 해줍니다. Search (Recursive) 재귀함수 탐색과정을 재귀적으로 수행하는 방법입니다. tree_pointer search(tree_pointer root, int..

Equality 두개의 입력 bit가 같으면 1을 출력하고 다르면 0을 출력합니다. 이는 XNOR Gate로 구현가능합니다. XNOR 의 진리표는 다음과 같습니다. A B X 0 0 1 0 1 0 1 0 0 1 1 1 따라서 두개의 A, B가 같으면 1 , 다르면 0을 출력합니다. 만약 2개의 bit를 비교하고자 한다면 더 많은 XNOR이 필요합니다. 예를 들어 A= A1A0 , B= B1B0 이라고 하면 A0, B0 끼리 비교하고 A1, B1끼리 비교하면 됩니다. 그리고 각각의 XNOR의 출력을 마지막에 AND로 보내면 두개의 bit가 모두 같은지 알 수 있습니다. Inequality equlity와 달리 우리는 두가지의 출력을 더 할 수 있습니다. 바로 '' 입니다. 예를들어 A = 1000 이고 B..

The Half-Adder Input : 두개의 2진수가 들어옵니다. Output : 두개의 출력이 나오는데 하나는 sum 또 다른 한개는 carry 입니다. A B C out Sum 0 0 0 0 0 1 0 1 1 0 0 1 1 1 1 0 다음 진리표를 보면 C out은 입력 A와 B의 AND gate와 같은 역할을 하는 것을 볼 수 있습니다. Sum 은 입력 A와 B 의 XOR gate와 같은 역할을 하는 것을 볼 수 있습니다. 따라서 왼쪽 그림과 같은 회로도로 나타낼 수 있습니다. The Full-Adder Input : 2개의 이진수와 Carry가 들어갑니다. Output : Sum과 Carry가 나옵니다. Half Adder와 차이점은 Full Adder은 Input으로 Carry를 받는다는 것..