인프런 워밍업 클럽 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): 왼쪽 자식 노드의 오른쪽 자식 노드가 추가되어 불균형이 발생할 때 왼쪽-오른쪽으로 두 번 회전
댓글을 작성해보세요.
