자료구조 & 알고리즘

레드블랙 트리 (Red-Black Tree)

자가 균형 이진 탐색 트리로, 각 노드가 빨간색 또는 검은색의 색상을 가지며 특정 규칙을 만족하여 트리의 균형을 유지
주요 규칙은 루트와 리프가 검은색이고, 빨간 노드의 자식은 검은색이며, 루트에서 리프까지 모든 경로의 검은 노드 수가 같음

우선순위 힙 (Priority Heap)

완전 이진 트리 구조로 구현된 자료구조로, 부모 노드가 자식 노드보다 우선순위가 높은(최대 힙) 또는 낮은(최소 힙) 특성을 만족 배열로 구현할 때 인덱스 관계가 명확하여 효율적인 구현이 가능하며, 최대값 또는 최소값을 O(1)에 접근할 수 있음

우선순위 큐 (Priority Queue)

각 원소가 우선순위를 가지며, 우선순위가 높은 원소가 먼저 처리되는 추상 자료형 일반적으로 힙으로 구현되어 삽입과 삭제 연산이 O(log n)의 시간 복잡도를 가집니다. 운영체제의 작업 스케줄링, 다익스트라 알고리즘 등에서 활용

컴퓨터 구조

MUX (Multiplexer)

여러 개의 입력 신호 중 선택 신호에 따라 하나의 입력을 선택하여 출력으로 전달하는 조합 논리회로
n개의 선택 신호로 2^n개의 입력 중 하나를 선택할 수 있으며, 데이터 경로 선택, 메모리 주소 선택 등에 사용됨

디코더 (Decoder)

n비트의 이진 입력을 받아 최대 2^n개의 출력선 중 하나만 활성화하는 조합 논리회로
입력된 이진 코드를 해석하여 해당하는 출력선을 선택하며, 메모리 주소 디코딩, 명령어 디코딩 등에 활용

컨트롤 버퍼 (Control Buffer)

시스템의 제어 신호를 임시 저장하고 전달하는 버퍼로, 제어 신호의 타이밍을 조정하고 신호 간의 동기화를 담당프로세서 내부에서 제어 신호의 전파 지연을 관리하고 안정적인 동작을 보장

반 가산기 (Half Adder)

두 개의 1비트 이진수를 더하여 합(Sum)과 자리올림(Carry)을 출력하는 기본적인 산술 논리회로 XOR 게이트로 합을, AND 게이트로 자리올림을 구현하며, 이전 자리에서의 자리올림은 고려하지 않음

전 가산기 (Full Adder)

두 개의 1비트 이진수와 이전 자리의 자리올림을 모두 고려하여 합과 자리올림을 출력하는 산술 논리회로
반 가산기 두 개를 조합하여 구현할 수 있으며, 다중 비트 덧셈 회로의 기본 구성 요소

ALU (Arithmetic Logic Unit, 산술논리연산장치)

산술 연산(덧셈, 뺄셈)과 논리 연산(AND, OR, NOT)을 수행하는 프로세서의 핵심 구성 요소
제어 신호에 따라 다양한 연산을 선택적으로 수행하며, 연산 결과에 대한 플래그 정보도 생성

조합 논리회로 / 순차 논리회로

조합 논리회로는 현재 입력값에만 의존하여 출력이 결정되는 회로로, 메모리 기능이 없음
순차 논리회로는 현재 입력과 이전 상태에 따라 출력이 결정되는 회로로, 플립플롭이나 래치 등의 메모리 소자를 포함함

SR 래치, D 래치, JK 래치

SR 래치는 Set과 Reset 입력으로 1비트 정보를 저장하는 기본 메모리 소자
D 래치는 Data 입력과 Enable 신호로 동작하며 투명 래치라고도 함
JK 래치는 SR 래치의 금지 상태를 해결한 개선된 형태로, J=K=1일 때 상태가 토글됨

플립플롭 (Flip-Flop)

클록 신호의 에지(상승 또는 하강)에 동기화되어 동작하는 순차 논리회로
래치와 달리 클록 에지에서만 상태가 변경되어 더 안정적인 동작을 보장