인프런 워밍업 클럽 스터디 4기 - CS 전공지식 > 1주차 발자국
◼만들면서 쉽게 배우는 컴퓨터 구조
Section1) 컴퓨터 구조 개요
컴퓨터는 트랜지스터라는 반도체 소자로 만들어지고, 여러 트랜지스터로 NAND 게이트를 만들며, 이로부터 컴퓨터가 구성된다.
프로그램의 동작방식 (2가지)
컴파일러
전체 코드를 미리 번역해 실행 속도가 빠름
컴파일 시 문법 오류 사전 발견 가능
인터프리터
한 줄씩 번역하며 실행, 실행 중 문법 오류 가능
실행 속도는 컴파일러보다 느림
Section2) 컴퓨터 구성 요소
CPU
컴퓨터의 두뇌 역할을 하는 장치로, 산술연산장치(ALU), 제어장치 등으로 구성된다.
메모리
RAM, ROM, 캐시 메모리 등이 있다.
주변 장치
입력 장치 (키보드, 마우스 등), 출력 장치 (모니터, 프린터 등) 등이 있다.
8비트, 32비트, 64비트 컴퓨터가 표현할수 있는 데이터 차이
8비트: 2^8 = 256개
32비트: 약 42억개 (RAM 4GB 한계)
64비트: 약 18경개 (RAM 한계없음, 거의 무한대)
Section3) 불 대수
불 대수의 등장
클로드 섀넌이 0과 1 (false, true)만으로 모든 논리 연산과 계이 가능함을 발견
주요 불 연산
NOT: 입력의 반대값 출력
AND: 둘 다 1일 때만 1 출력
OR: 둘 중 하나 이상 1이면 1 출력
NAND: AND의 결과를 반전
NOR: OR의 결과를 반전
XOR: 입력이 서로 다를 때 1 출력 (입력개수 2개일때), 1의 개수가 홀수이면 1, 아니면 0 (입력개수가 3개이상일때)
불 연산 우선순위 : NOT -> AND -> OR
불 대수의 성질과 법칙
항등원 법칙, 교환법칙, 분배법칙, 동일법칙, 이중부정법칙, 흡수법칙, 드모르간 법칙 등이 있다
불 연산을 바탕으로 진리표 작성 가능
방정식 -> 진리표 -> 논리회로로 변환
Section4) 비트
10진법, 2진법, 16진법
10진법은 0~9까지 10개의 숫자 사용
2진법은 0과 1 두 가지 숫자만 사용
16진법은 0~9, A~F(10~15)를 사용
바이트 저장 순서 방식
리틀 엔디안: LSB(Least Significant Byte, 가장 낮은 자리 바이트)를 낮은 주소에 저장
빅 엔디안: MSB(Most Significant Byte, 가장 높은 자리 바이트)를 낮은 주소에 저장
오버플로우
표현할 수 있는 비트 수를 초과하는 계산 결과 발생 시 결과가 제대로 저장되지 못하는 현상
음수 표현
MSB(Most Significant Bit, 최상위 비트)가 0이면 양수, 1이면 음수로 해석
2의 보수법
음수를 표현하는 방법
음수 = 1의 보수(모든 비트를 반전) + 1
Section5) 컴퓨터의 기초가 되는 하드웨어 만들기
Logisim-evolution 같은 시뮬레이터를 사용해 논리 회로를 직접 설계·실험 가능,
설치하려면 JDK 필요, GitHub에서 최신 버전 다운로드 가
기본 논리 게이트
NAND 게이트, NOT 게이트, AND 게이트, OR 게이트, XOR 게이트
Mission1)
◼그림으로 쉽개 배우는 자료구조와 알고리즘
Section1) 개요
선형 자료구조 : 배열, 연결 리스트, 스택, 큐
비선형 자료구조: 트리, 그래프, 힙
P-NP 문제 개념 이해
빅오 표기법 (시간 복잡도)
결정 문제와 최적화 문제
P 문제 (Polynomial time 문제)
NP 문제 (Nondeterministic Polynomial time 문제)
NP-hard 문제
P vs NP 문제
Section2) 트리와 이진트리
트리
노드(Node)와 간선(Edge)으로 구성된 계층적 자료구조
트리의 구성요소
노드, 간선, 루트 노드, 자식 노드, 형제 노드, 리프 노드, 레벨, 높이
이진트리
각 노드가 최대 2개의 자식 노드를 갖는 트리
포화이진트리와 완전이진트리도 존
Section3) 이진 탐색트리
각 노드가 값의 기준점 역할을 하며, 찾고자 하는 값이 현재 노드의 값보다 크면 오른쪽 서브트리를, 작으면 왼쪽 서브트리를 탐색하는 구조
Section4) AVL 트리
높이 균형을 유지하는 이진 탐색 트리로, 각 노드의 왼쪽과 오른쪽 서브트리 높이 차이(균형 인수)가 최대 1 이내여야 한다.
이 균형 조건을 벗어나면 회전 연산을 통해 트리의 균형을 맞춰 탐색, 삽입, 삭제 수행
🗒회고
컴퓨터 구조와 자료구조(알고리즘) 강의를 동시에 완벽히 이해하기엔 시간적으로 무리가 있을 것 같아 컴퓨터 구조 심화 학습에 좀 더 집중해볼 예정이다.
강의에서 Logisim-evolution을 활용해 AND, OR, NOT, XOR 등의 게이트를 직접 만들어보는 과정이 인상 깊었다. 회로를 하나하나를 쌓아가며 구조를 이해하는게 재미가 있어 몰입이 잘 되었다.
강의를 완강할 즈음에는, 정말 작은 컴퓨터 하나쯤은 스스로 만들어 낼 수 있을 것 같은 기대감이 든다
🏷출처
