* 본 글은 [Introduction to Logic Design, 3rd ed. - Alan B. Marcovitz] 를 바탕으로 작성하였습니다. 스위칭 대수는 진리표 혹은 다른 부품으로 구성된 시스템의 해석 및 설계에 필수적이다. "불 대수(boolean algebra)" 로 이루어진 스위칭 대수는, (1) 게이트 회로에서 입력에 대한 출력값을 연산할 때, (2) 아주 복잡한 게이트 회로의 수식을 설계할 때, (3) 게이트 회로를 구현할 때 필수적이다. 스위칭 대수란? 스위칭 대수는 모든 변수/상수가 2개의 값(0 혹은 1)으로 된 대수를 말한다. 2진으로 표현되지 않는 변수는 2진으로 코딩된다. 아래는 스위칭 대수의 3가지 연산자이다. OR (+): a+b로 나타냄, a=1이거나 b=1일 때, 둘 ..

* 본 글은 [Introduction to Logic Design, 3rd ed. - Alan B. Marcovitz] 를 바탕으로 작성하였습니다. 조합회로란, 해당 시점의 출력이 그 시점에서 입력으로만 결정되는 회로를 말한다. 반대되는 개념으로는 이전의 입력도 출력에 관여하는 순차회로가 있다. 본 포스팅에서는 조합회로를 설계하는 기본적인 방법에 대해 알아보고자 한다. 조합회로 시스템 설계 과정 1단계: 각 입력과 출력을 2진으로 표현하라 일반적으로 스위치가 켜지는 위 방향을 1, 꺼지는 아래 방향을 0으로 코딩할 수 있다. 또한, 만약 필요하다면 문제를 더 자근 부문제(subproblem)으로 나눌 수 있다. 2단계: 설계 사양을 진리표 혹은 대수식으로 형식화하라 진리표란, 가능한 입력 조합에 대한 각..

* 본 글은 [Introduction to Logic Design, 3rd ed. - Alan B. Marcovitz] 를 바탕으로 작성하였습니다. 디지털 시스템이란? 디지털 시스템이란, 임의의 불연속적인 입력(A, B, ..)을 받아 임의의 출력(W, X, ...)을 만드는 시스템을 말한다. 입력은 클럭 등 다양한 방식에 의해 이루어진다. 예를 들어, 세 개의 입력 A, B, C를 받아 두 개의 입력이 1일 때만 출력 Z = 1을 출력하는 시스템은 디지털 시스템이다. 이처럼 출력이 입력의 현재 값에만 의존하는 회로를 조합회로(combinational)라고 한다. 반면, 지난 시간의 입력 상태를 알아야 하는 회로를 순차회로(sequential)라고 한다. 대표적인 불연속 입력은 이진수로 이루어진다. 예를..

1764번: 듣보잡 김진영이 듣도 못한 사람의 명단과, 보도 못한 사람의 명단이 주어질 때, 듣도 보도 못한 사람의 명단을 구하는 프로그램을 작성하시오. 입력: 첫째 줄에 듣도 못한 사람의 수 N, 보도 못한 사람의 수 M이 주어진다. 이어서 둘째 줄부터 N개의 줄에 걸쳐 듣도 못한 사람의 이름과, N+2째 줄부터 보도 못한 사람의 이름이 순서대로 주어진다. 이름은 띄어쓰기 없이 알파벳 소문자로만 이루어지며, 그 길이는 20 이하이다. N, M은 500,000 이하의 자연수이다. 듣도 못한 사람의 명단에는 중복되는 이름이 없으며, 보도 못한 사람의 명단도 마찬가지이다. 출력: 듣보잡의 수와 그 명단을 사전순으로 출력한다. 문제를 보자마자 "교집합->set을 이용하자" 를 떠올렸다. Intersection..

백준 2164번: 카드 2 N장의 카드가 있다. 각각의 카드는 차례로 1부터 N까지의 번호가 붙어 있으며, 1번 카드가 제일 위에, N번 카드가 제일 아래인 상태로 순서대로 카드가 놓여 있다. 이제 다음과 같은 동작을 카드가 한 장 남을 때까지 반복하게 된다. 우선, 제일 위에 있는 카드를 바닥에 버린다. 그 다음, 제일 위에 있는 카드를 제일 아래에 있는 카드 밑으로 옮긴다. 예를 들어 N=4인 경우를 생각해 보자. 카드는 제일 위에서부터 1234 의 순서로 놓여있다. 1을 버리면 234가 남는다. 여기서 2를 제일 아래로 옮기면 342가 된다. 3을 버리면 42가 되고, 4를 밑으로 옮기면 24가 된다. 마지막으로 2를 버리고 나면, 남는 카드는 4가 된다. N이 주어졌을 때, 제일 마지막에 남게 되..

* 본 글은 [윤성우의 열혈 자료구조 - C언어를 이용한 자료구조 학습서] 를 바탕으로 작성하였습니다. 우선순위 큐(Priority Queue)란? 우선순위 큐 또한 큐와 마찬가지로 enqueue, dequeue 연산이 있으나, 연산의 결과에서 차이를 보인다. 뒤에서 데이터를 enqueue하고 앞에서 dequeue 하는 큐와 달리, 우선순위 큐는 들어간 순서에 상관없이 우선순위가 높은 데이터가 먼저 나오는 자료구조이다. 프로그래머가 결정한 기준에 따라 데이터에 우선순위를 매기고, 해당 순서에 따라 데이터를 꺼낼 수 있도록 하는 것이다. 우선순위 큐는 아래 세 가지 방법으로 구현한다. 배열을 기반으로 구현 연결 리스트를 기반으로 구현 힙(heap)을 기반으로 구현 배열을 기반으로 구현 배열을 기반으로 구현..