레지스터 레지스터(이하 Reg)는 다수비트의 데이터를 저장하는 목적으로 사용하는 소자입니다. 1. 공통 클럭을 갖는 다수의 FF을 묶어서 만듭니다. 2. 이진데이터를 저장하기 위해 사용합니다. 4비트 D-FF으로 구성한 Reg 위 ClrN은 Clear입력이 NOT 게이트를 거쳐서 들어간다는 뜻입니다. Load를 1로 만들어준 상태에서 클럭입력이 하강에지가 되면, D-FF의 출력에 입력이 나타나게 됩니다. 하지만 위와같이 구성된 reg를 사용하게 되면, 게이트를 통과하면서 생기는 시간 지연으로 모든 FF에서 동시에 값의 저장이 일어나지 않을 수 있습니다. 또한 클럭입력의 에지에서 값의 변화가 일어날 수도 있지만, Load신호에 의해서도 FF 출력에 변화가 일어날 수 있습니다. 여기서 클럭활성화(Clock ..

플립플롭 플립플롭(이후 FF)은 단일클럭을 사용하는 순차회로에서 정확히 동작하도록 설계된 저장회로입니다. FF의 특성은 다음과 같습니다. 1. FF에서 출력이 변경되기 전에 입력에서 출력으로 가는 경로를 끊어줍니다. 2. FF은 자신의 출력 변화를 볼 수 없습니다. 3. FF의 다음 상태는 바로 직전 상태에만 의존합니다.(즉, 다수의 상태 변경이 일어나지 않습니다.) 앞으로 설명하는 모든 FF은 에지-트리거형 FF입니다. 클럭 입력의 상승이나 하강 에지에서만 변경되기 때문에 사실 에지-트리거형이라고 묶어놓는 것은 의미가 없습니다. 다만 상승 에지-트리거냐 하강 에지-트리거냐가 중요합니다. D-FF D-FF은 데이터 D와 클럭 Ck 두개의 입력을 갖습니다. 심볼의 삼각형 모양이 클럭 모양입니다. 출력이 클..

순차회로 입력에만 의존했던 조합회로와는 달리 순차회로는 현재 입력과 입력들의 과거 값들의 순서에 의존합니다. 따라서 순차회로는 현재의 출력을 발생시키기 위해, 과거에 대한 무언가를 기억해야합니다. 이때 Latch(이하 래치)와 Flip-Flop(이하 플립플롭)이 기억소자로 사용됩니다. 래치와 플립플롭은 기억소자들로 1. 두 개의 안정된 출력 상태 중에 한 개를 가질 수 있으며 2. 출력 상태를 바꿀 수 있는 입력을 한 개 이상 가질 수 있습니다. 이때 클럭 입력이 없는 기억소자를 래치라고 부릅니다. 피드백 위와같이 게이트 출력중의 일부가 게이트의 다른 입력에 연결되어 폐회로를 만드는 경우, 피드백 회로라고 부릅니다. 저장장치는 피드백 회로의 지연시간으로 구현될 수 있습니다. 즉, 출력으로 나간 값이 다시..

ROM ROM은 Read only memory의 줄임말로 말 그대로 읽기만 가능한 메모리입니다. 따라서 변경이 불가능합니다. 이진 데이터 배열을 저장하는 것이 목적이며, 이를 위해 반도체 소자의 연결로 구성되어 있습니다. ROM은 n개의 입력 라인과 m개의 출력 라인을 갖습니다. n개의 입력라인이므로 총 $2^n$개의 입력을 만들 수 있고 각각의 입력에 대응되는 m비트의 배열을 워드라고 불립니다. 이때 m비트를 워드의 길이라고 합니다. $2^n \times m$비트 ROM은 $2^n$개의 행과 m개의 열을 갖는 진리표를 저장할 수 있기 때문에 n변수의 m개의 함수를 구현할 수 있게됩니다. ROM의 기본적인 구조 ROM은 디코더와 메모리 배열로 구성됩니다. 길이가 n인 입력이 디코더에 들어오면, $2^n$..

MUX MUX는 Multiplexer의 약자로 다수의 입력 + 다수의 제어입력을 갖습니다. MUX에 제어 입력을 넣으면 다수의 입력중 하나를 선택하여 출력에 연결할 수 있게됩니다. 이때 입력은 $2^n$개가 가능하며, 꼭 하나의 입력에 대해 하나의 데이터를 물려놓지 않아도 됩니다. 즉, 총 4개의 입력이 가능하다고 할때, 0에는 A라는 데이터 1에는 B라는 2~3에는 C라는 데이터를 물려놓을 수 있습니다. 중요한 것은 이중 0~3중 하나만을 제어입력을 통해 선택하여 출력해야 한다는 것입니다. 입력의 개수를 $IC$라고 하면, $IC = 2^n$개가 가능하므로 제어입력은 $log_2^{IC} = n$개가 있어야합니다. 이때 입력의 개수에 따라 MUX의 이름을 달리 부르게 되는데, 만약 4개의 입력을 가진다..

기본적인 내용은 건너뛰겠습니다. 2-3 트리를 포함한 2-3-4 트리 혹은 Multi-way 탐색 트리 까지 공통점이 있습니다.한 노드에 들어갈 수 있는 자식 노드의 개수가 m개라고 하겠습니다. 1. 루트 노드는 적어도 2개의 자식 노드가 있어야 합니다.2. 모든 leaf 노드는 같은 높이에 위치해야합니다. 즉, 항상 균형잡힌 형태를 유지해야합니다.3. 루트 노드를 제외한 모든 노드는 $\lceil \frac{m}{2} \rceil$ 개의 자식 노드들이 있어야합니다. 이번에 소개할 내용은 2-3 트리이며, m이 3인 트리중 하나라고 할 수 있습니다. 위 공통점에 해당하는 내용을 잘 생각하고 읽어주세요. 아래 예시로 드는 모든 2-3 트리들의 그림은 다음과 같은 공통점이 있습니다. 박스가 하나인 경우 --..

1주차 확률과 통계 내용 정리 목차 Introduction to Probablity Set Theory (operations & relations) The definition of probability Introduction to Probablity 목차 Experiment Sample Space Event Experiment Experiment는 가능한 식별 가능한 모든 결과를 말한다. 모든 경우의 수를 다 세는 것을 설명하신듯. Sample Space $S$ 로 표기한다. 한 experiment에 대해 가능한 모든 결과들의 집합을 말한다. 주사위를 한 번 던질 때의 Sample Space는 다음과 같이 나타낸다. $$ S = {1, 2, 3, 4, 5, 6} $$ Event $E$ 로 표기한다. 조건..

중요하게 다뤄지는 테마로는 Min-Cut Max-Flow Theorem문제부터 이분매칭, 그리고 MCMF까지있다. 3가지를 모두 깊게 파지는 못했지만 그래도 풀면서 알게된 테크닉들을 적어보려한다. 문제들은 모두 백준에있는 문제들로 했으며, 전역하면 코드포스나 탑코더에 있는 문제들도 풀어보려한다. 알고리즘 하나를 알게되면 관련된 문제들을 모두 풀어보려고 노력한다. 따라서 유형을 정리한다고 하면 백준에있는 알고리즘 분류를 통해 알게되는 문제들을 정리한다는 말이다. 정리가 오늘 하루만 하는것도아니고.. 계속해서 업데이트되는 글이 될것이다. SRC = 시작점, SINK = 도착점입니다. [Min-Cut Max-Flow Theorem] 최대 플로우가 최소컷이라는 재미있는 이론이다. 이걸 처음 접할 때만해도 컷이라..