인프런 워밍업 클럽 4기 CS - 2주차 발자국

디지털 논리 회로의 핵심 구성 요소디지털 회로는 정보를 처리하고 저장하기 위해 다양한 논리 회로들을 사용합니다. 이 회로들은 크게 조합 논리 회로와 순차 논리 회로로 나눌 수 있어요.1. 정보 선택 및 분배 회로주어진 여러 정보 중 필요한 것을 선택하거나, 하나의 정보를 여러 목적지로 분배하는 역할을 합니다.멀티플렉서 (Multiplexer, MUX)역할: 여러 개의 입력(예: 2n개) 중 하나를 선택하여 출력합니다. 마치 여러 개의 물건 중 하나를 고르는 것과 같아요.선택 신호: '선택 신호(Select Line)'를 통해 어떤 입력을 출력할지 결정합니다.예시: 4:1 MUX는 4개의 입력 중 1개를 선택하며, 이를 위해 2개의 선택선이 필요해요.디멀티플렉서 (Demultiplexer, DEMUX)역할: 하나의 입력을 받아, 선택된 하나의 출력으로 전달합니다. 마치 하나의 물건을 여러 목적지 중 한 곳으로 보내는 것과 같아요.선택 신호: '선택 신호'를 통해 어느 출력으로 보낼지 결정합니다.디코더 (Decoder)역할: n개의 입력을 받아, 2n개의 출력 중 오직 하나만 활성화(1로 만듦)시킵니다.활성화: 특정 입력 조합에 대해 해당하는 출력 하나만 '1'이 되고 나머지는 모두 '0'이 됩니다.예시: 3:8 디코더는 3개의 입력에 대해 8개의 출력 중 하나만 활성화됩니다.주요 사용처: 특정 주소나 명령어를 인식하고 선택하는 데 사용됩니다.2. 제어 및 데이터 흐름 관리 회로제어 신호를 관리하고 데이터 흐름의 안정성을 유지하는 데 사용됩니다.컨트롤 버퍼 (Control Buffer)역할: 제어 신호나 제어 정보를 일시적으로 저장하거나 전달하는 완충 회로입니다.주요 기능:타이밍 조절: 제어 신호 전달 시 속도 차이를 조절하여 동기화 문제를 해결합니다.안정성 유지: 제어 흐름을 안정적으로 유지하며, 경우에 따라 컨트롤 레지스터(Control Register)와 혼용되기도 합니다.사용처: CPU 내부, 메모리 컨트롤러, 입출력(I/O) 장치 제어 등 다양한 곳에서 사용됩니다.3. 연산 회로이진수를 이용한 덧셈을 수행하는 데 사용되는 기본적인 회로입니다.반가산기 (Half Adder)역할: 두 개의 1비트 이진수(A, B)를 더합니다.출력: 합(Sum)과 자리올림(Carry)이 있습니다.논리식:Sum=A⊕B (XOR 연산)Carry=A∧B (AND 연산)한계: 이전 자리에서 발생한 자리올림 값(Carry-in)을 처리할 수 없습니다.전가산기 (Full Adder)역할: 세 개의 1비트 이진수(A, B, 그리고 이전 자리의 자리올림 값인 Carry_in)를 더합니다.출력: 합(Sum)과 자리올림(Carry_out)이 있습니다.논리식:Sum=A⊕B⊕Carry_inCarry_out=(A∧B)∨(B∧Carry_in)∨(A∧Carry_in)특징: 자리올림 입력을 처리할 수 있어 여러 비트의 덧셈(다비트 덧셈)에 활용됩니다.4. 논리 회로의 분류회로의 동작 방식과 기억 기능 유무에 따라 크게 두 가지로 나뉩니다.조합 논리 회로 (Combinational Logic Circuit)특징: 현재 입력에 의해서만 출력이 결정되며, 과거 상태를 기억하지 않습니다. (메모리 기능 없음)동작: 입력이 바뀌면 출력이 즉시 바뀝니다. 클럭 신호가 필요 없습니다.예시: 가산기(Adder), 디코더(Decoder), 인코더(Encoder), 멀티플렉서(MUX), 비교기 등이 있습니다.순차 논리 회로 (Sequential Logic Circuit)특징: 현재 입력과 과거 상태(기억된 값)에 따라 출력이 결정됩니다. 기억 기능(메모리)을 포함합니다.동작: 클럭(Clock) 신호에 따라 타이밍 기반으로 동작하며, 출력이 시간의 흐름에 따라 변하거나 유지됩니다.예시: 플립플롭(Flip-Flop), 레지스터(Register), 카운터(Counter), FSM(상태 기계), 메모리 등이 있습니다.5. 순차 논리 회로의 기본 소자순차 논리 회로의 핵심인 기억 소자들입니다.클럭 (Clock)역할: 디지털 회로 전체의 동작 타이밍을 결정하는 주기적인 펄스 신호입니다.동작 기준: 클럭의 상승 엣지(↑)나 하강 엣지(↓)에서 회로가 동작하도록 설계됩니다.래치 (Latch)SR 래치 (Set-Reset Latch)역할: S(Set), R(Reset) 두 입력으로 출력 Q를 제어하며, 이전 상태를 기억하는 순차 회로의 기본 형태입니다.문제점: S=1, R=1일 때 출력이 불안정해지는 '금지 상태'가 발생합니다.D 래치 (Data or Delay Latch)역할: SR 래치의 금지 상태 문제를 해결했습니다.입력: D(Data)와 Enable (또는 Clock)이 있으며, Enable이 '1'일 때만 D 값이 출력 Q로 전달됩니다.특징: 항상 안정적으로 동작하며, 메모리 소자에 많이 사용됩니다.JK 래치역할: SR 래치의 금지 상태를 해결한 또 다른 형태입니다.입력: J, K, 그리고 Clock이 있습니다. J는 Set, K는 Reset 역할을 합니다.특징: J=K=1일 때 출력이 반전되는 특징이 있어 플립플롭 구현에 주로 사용됩니다.플립플롭 (Flip-Flop)역할: 1비트의 정보를 저장할 수 있는 순차 논리 회로입니다.동작: 클럭 신호에 의해 상태가 변하거나 유지됩니다.종류: D, JK, T 등 다양한 종류가 있습니다. (래치와는 클럭 동기화 방식에서 차이가 있습니다.)레지스터 (Register)역할: 여러 개의 플립플롭을 묶어 만든 구조로, 보통 8, 16, 32비트 등 데이터를 임시 저장하는 데 사용됩니다.특징: CPU 내부에서 동기식으로 동작하며 고속 데이터 처리에 필수적입니다.RAM (Random Access Memory)역할: 데이터를 자유롭게 읽고 쓸 수 있는 임의 접근 메모리입니다.특징: 전원이 꺼지면 데이터가 사라지는 휘발성 메모리입니다.접근 방식: 주소를 지정하여 원하는 위치의 데이터를 직접 접근할 수 있습니다.

인프런 워밍업 클럽 4기 CS - 1주차 - 미션

4입력 AND, OR, NAND, NOR, XOR 연산의 진리표를 작성해보세요.다음 볼 방정식들을 여러 방법을 이용해 간략화 해보세요.A( (BB)’+ 0A) + (CC)' = (AB’) +CA( (B)' + 0) + (C)' = (AB') + CA(B') + C' = (AB') + CAB' + C' = AB' + C2. (B’B’) + (AD’ + (CA)’)D = B’ + (DC’) + (DA’)(B') + AD'D + (CA)'D = B' + (DC') + (DA')B' + A0 + (CA)'D = B' + (DC') + (DA')B' + (CA)'D = B' + (DC') + (DA')B' + (C' + A')D = B' + (DC') + (DA')B' + C'D + A'D = B' + DC' + DA' 3. (A’B) + B(B1 + BC) = B(A’B) + B(B + BC) = B(A’B) + BB + BBC = B(A’B) + B + BC = B(A’B) + B = BA’B + B = BB = B 4.B’(1C + BD) + DB = (B’C) + (DB)B’(C + BD) + DB = (B’C) + DBB’C + B’BD + DB = B’C + DBB’C + 0D + DB = B’C + DBB’C + DB = B’C + DB 다음 2진수를 10진수로 변환해보세요.1. 110111 = 552. 10000001 = 1293. 11111100000 = 20164. 101010 = 42 다음 10진수를 2진수로 변환해보세요.1. 10 = 10102. 27 = 110113. 86 = 10101104. 516 = 1000000100 다음 불 방정식을 logisim을 이용해 회로를 만들어보세요.(회로 이미지와 .circ파일 첨부)1. (B’C) + (DB) 2. (AB’) +C 3. B’ + (DC’) + (DA’)첨부파일 : https://www.notion.so/1-2056efa4d8778028bd01f329b4b3073e?source=copy_link

인프런 워밍업 클럽 4기 CS - 1주차 발자국

컴퓨터 구성 요소CPU (Central Processing Unit): 컴퓨터의 뇌라고 할 수 있습니다. 모든 계산과 데이터 처리를 담당하며, 프로그램의 명령어를 실행합니다.메모리 (Memory): CPU가 작업을 처리하는 데 필요한 데이터를 임시로 저장하는 공간입니다. 주로 RAM(Random Access Memory)을 의미하며, 전원이 꺼지면 내용이 사라지는 휘발성 메모리입니다.주변 장치 (Peripherals): 컴퓨터와 정보를 주고받는 외부 장치들을 말합니다.입력 장치: 키보드, 마우스, 스캐너처럼 컴퓨터에 정보를 입력하는 장치입니다.출력 장치: 모니터, 프린터, 스피커처럼 컴퓨터가 처리한 정보를 보여주거나 내보내는 장치입니다.저장 장치: 하드 디스크 드라이브(HDD), 솔리드 스테이트 드라이브(SSD), USB 메모리처럼 데이터를 영구적으로 저장하는 장치입니다. 비트와 데이터 표현비트 (Bit): 컴퓨터가 정보를 표현하는 가장 작은 단위입니다. 0 또는 1의 두 가지 값만 가질 수 있습니다. 스위치의 ON/OFF처럼 생각할 수 있습니다.10진법, 2진법, 16진법:10진법 (Decimal): 우리가 일상생활에서 사용하는 숫자 체계입니다. 0부터 9까지 10개의 숫자를 사용합니다.2진법 (Binary): 컴퓨터가 사용하는 숫자 체계입니다. 0과 1 두 가지 숫자만 사용하여 모든 수를 표현합니다. 비트는 2진법의 한 자리를 의미합니다.16진법 (Hexadecimal): 0부터 9까지의 숫자와 A부터 F까지의 알파벳을 사용하여 16개의 숫자를 표현하는 체계입니다. 2진수를 간결하게 표현하기 위해 사용됩니다. 예를 들어, 2진수 1111은 16진수 F와 같습니다.빅 엔디안 (Big-Endian), 리틀 엔디안 (Little-Endian): 컴퓨터 메모리에 여러 바이트로 이루어진 데이터를 저장하는 방식입니다.빅 엔디안: 데이터의 가장 큰(빅) 자리부터 메모리에 저장하는 방식입니다. (예: 1234를 저장할 때 12-34 순)리틀 엔디안: 데이터의 가장 작은(리틀) 자리부터 메모리에 저장하는 방식입니다. (예: 1234를 저장할 때 34-12 순)LSB (Least Significant Bit), MSB (Most Significant Bit):LSB: 이진수에서 가장 낮은 자리의 비트입니다. 10진수의 일의 자리와 같습니다. (예: 1011에서 가장 오른쪽 1)MSB: 이진수에서 가장 높은 자리의 비트입니다. 숫자의 부호나 크기를 결정하는 중요한 비트입니다. (예: 1011에서 가장 왼쪽 1)오버플로우 (Overflow): 특정 비트 수로 표현할 수 있는 숫자의 범위를 넘어섰을 때 발생하는 현상입니다. 예를 들어, 4비트로 15까지 표현할 수 있는데 16을 표현하려 할 때 오버플로우가 발생합니다.인터럽트 (Interrupt): CPU가 어떤 작업을 처리하는 도중에 급하게 처리해야 할 일이 생겼을 때, 현재 작업을 잠시 멈추고 그 일을 먼저 처리하도록 알리는 신호입니다. 음수와 2의 보수음수 표현: 컴퓨터는 0과 1만으로 음수를 표현해야 합니다. 여러 방법이 있지만, 가장 널리 사용되는 방법은 2의 보수(Two's Complement)를 이용하는 것입니다.2의 보수 + 1로 치환: 어떤 양수 X에 대한 2의 보수는 모든 비트를 반전시킨 후 1을 더한 값입니다. 이 2의 보수 표현을 사용하면 뺄셈 연산을 덧셈 연산으로 편리하게 처리할 수 있습니다.예: 5−3을 5+(−3)으로 계산할 때, −3을 2의 보수로 표현하여 덧셈을 수행합니다. 불 대수와 논리 연산불 대수 (Boolean Algebra): 조지 불이 창시한 수학적 체계로, 논리적인 참(1)과 거짓(0)을 다루는 대수입니다. 컴퓨터의 모든 논리 회로는 불 대수를 기반으로 설계됩니다.연산:AND (논리곱): 두 입력이 모두 1일 때만 결과가 1입니다. (A AND B = A ⋅ B)OR (논리합): 두 입력 중 하나라도 1이면 결과가 1입니다. (A OR B = A + B)NOT (논리 부정): 입력이 1이면 0, 0이면 1로 반전시킵니다. (Aˉ)성질과 법칙: 불 대수에는 연산을 간단하게 할 수 있는 여러 법칙이 있습니다.교환법칙 (Commutative Law): A⋅B=B⋅A, A+B=B+A (순서를 바꿔도 결과는 같음)결합법칙 (Associative Law): (A⋅B)⋅C=A⋅(B⋅C), (A+B)+C=A+(B+C) (묶는 순서를 바꿔도 결과는 같음)분배법칙 (Distributive Law): A⋅(B+C)=A⋅B+A⋅C, A+(B⋅C)=(A+B)⋅(A+C) (괄호 안의 연산을 분배하여 계산)흡수법칙 (Absorption Law): A+(A⋅B)=A, A⋅(A+B)=A (특정 항이 다른 항을 흡수)드모르간의 법칙 (De Morgan's Law): A⋅B=A+B, A+B​=A⋅B (논리 연산의 부정을 분리)불 함수 (Boolean Function): 불 변수들을 사용하여 논리 연산으로 표현되는 함수입니다. 컴퓨터 회로의 동작을 수학적으로 표현합니다.카르노 맵 (Karnaugh Map): 불 함수를 간소화하는 시각적인 도구입니다. 복잡한 논리식을 직관적으로 정리하여 더 간단한 논리 회로를 설계할 수 있도록 돕습니다. 자료구조 & 알고리즘P-NP 문제P-NP 문제: 컴퓨터 과학의 가장 큰 미해결 문제 중 하나입니다.P (Polynomial time) 문제: 주어진 답이 올바른지 검증하는 데 걸리는 시간과 해결하는 데 걸리는 시간이 모두 효율적인(다항 시간) 문제입니다.NP (Non-deterministic Polynomial time) 문제: 주어진 답이 올바른지 검증하는 데 걸리는 시간은 효율적이지만, 해결하는 데 걸리는 시간은 비효율적일 수 있는 문제입니다.P = NP 인가? 라는 질문은 "해답을 빠르게 확인할 수 있는 모든 문제가 해답을 빠르게 찾을 수 있는 문제인가?"를 묻는 것입니다.트리 (Tree)트리: 나무처럼 가지를 뻗어나가는 형태의 자료구조입니다.계층 구조를 표현하기에 적합: 파일 시스템(폴더 안에 폴더, 파일), 조직도(사장 아래 부서장, 사원)처럼 상하 관계가 있는 데이터를 표현하는 데 아주 유용합니다.이진 트리 (Binary Tree): 각각의 노드가 최대 2개의 자식 노드(왼쪽 자식, 오른쪽 자식)를 가질 수 있는 트리입니다.성능:조회: 최악의 경우 O(n) (모든 노드를 탐색해야 함), 평균 및 최적의 경우 O(logn) (트리의 높이에 비례하여 빠르게 탐색 가능)종류:완전 이진 트리 (Complete Binary Tree): 마지막 레벨을 제외하고 모든 레벨이 완전히 채워져 있으며, 마지막 레벨은 왼쪽부터 채워지는 트리입니다.포화 이진 트리 (Full Binary Tree): 모든 노드가 0개 또는 2개의 자식 노드를 가지는 트리입니다.AVL 트리 (Adelson-Velsky and Landis Tree): 스스로 균형을 잡는(self-balancing) 이진 탐색 트리입니다. 좌우 서브트리의 높이 차이가 1을 넘지 않도록 자동으로 노드를 재배치하여 트리의 균형을 유지합니다. 이를 통해 탐색, 삽입, 삭제 시 항상 O(logn)의 시간 복잡도를 보장합니다.회전 (Rotation): AVL 트리가 균형을 맞추기 위해 사용하는 방법입니다. 불균형이 발생하면 노드의 위치를 회전시켜 높이를 조절합니다.RR 회전 (Right-Right Rotation): 오른쪽 자식 노드가 오른쪽에 추가되어 불균형이 발생할 때 왼쪽으로 회전LL 회전 (Left-Left Rotation): 왼쪽 자식 노드가 왼쪽에 추가되어 불균형이 발생할 때 오른쪽으로 회전RL 회전 (Right-Left Rotation): 오른쪽 자식 노드의 왼쪽 자식 노드가 추가되어 불균형이 발생할 때 오른쪽-왼쪽으로 두 번 회전LR 회전 (Left-Right Rotation): 왼쪽 자식 노드의 오른쪽 자식 노드가 추가되어 불균형이 발생할 때 왼쪽-오른쪽으로 두 번 회전