TIL 11/11

드립이 블로그·2022년 11월 11일

TIL

목록 보기

9/80

이번 CS시간에는 CPU에 대하여 배웠다
CPU
n개의 코어가 있음
코어는 n개의 레지스터로 구성됨

싱글코어에서 멀티코어로 진화 된 이유
발열을 감당 할 수가 없음. 코어 성능 향상에는 본질적으로 한계가 있기 때문에 멀티 코어를 사용하게 됨.

ALU Arithmetic and Logical Unit 산술 논리 연산
CU로부터 연산 명령을 받아 모든 산술, 논리 연산을 실행한다.
그후 프로그램에 결과를 보낸다.

CU Control Unit
1.fetch
2.decode
3.ALU에 연산명령

Cache
자주, 최근에 접속한 것을 저장해놓음

Compiler
기계어, 어셈블리어로 언어를 바꿔준다.

이렇게 한시간동안 CPU에 대해 간단하게 강의를 들었다.

오늘 CPU 말고도 Stack, Queue, Hash 에 대해서도 알게 되었다.

Stack은 한 쪽으로만 데이터를 넣고 빼는 구조이다. 가장 먼저 넣었던 데이터가 가장 먼저 나오는 구조를 가지고 있다.
Last In First Out LIFO 구조 라고도 한다.
이는 대표적으로 되돌리기 (Ctrl + Z)에 사용된다.

push(data) 맨 위에 데이터를 넣는다.
pop() 맨 위의 데이터를 뽑는다. 맨 위에만 해당하기 때문에 인자가 존재하지 않는다.
peek() 맨 위의 데이터를 본다.
is empty() Stack이 비었는지의 여부를 확인한다.

Queue는 한 쪽으로 데이터를 넣고 다른 한 쪽으로는 데이터가 나오는 구조를 가지고 있다.
First In First Out FIFO구조 라고도 한다.
순서대로 처리 되어야 하는 일에 사용되는 구조이다.

enqueue(data) 맨 뒤에 데이터를 추가한다.
dequeue() 맨 위의 데이터를 뽑는다.
peek() 맨 위의 데이터를 본다.
is empty() Queue가 비었는지의 여부를 확인한다.

스택과는 다르게 시작(self.head)과 끝(self.tail)의 노드 전부를 가지고 있어야 한다.

검색과 저장이 아주 빠르게 진행된다.
dictionary를 hash table이라고 부르기도 한다.
딕셔너리는 내부적으로 배열을 사용한다.

dict = {"A" : "a", "B" : "b" }

Class Dict:
    def __init__(self):
        self.items = [None] * n

여기서 A와 B의 값인 a,b는 이 배열 어딘가에 있을 때, hash 함수를 사용하여 찾는다.

Hash Function
임의의 길이를 갖는 메시지를 입력하면, 고정된 길이의 hash 값을 출력하는 함수이다

Python 에서는 hash(object)로 해당 함수를 제공하고 있다.
hash(A) % n을 하게 되면 나머지 값이 나온다.
그 숫자의 index에 이 값을 저장하면 된다.
items[hash("A") % n] = "a"

hash 함수에 index 값이 동일해지는 경우가 존재한다. 이 경우 이전 값이 덮어씌워지는데, 이를 충돌이 발생했다고 표현한다.

이를 해결하는 방법은 여러가지 존재한다.

chaining
충돌을 해결하는 방법중 하나이다.
각 배열에 Linkedlist를 연결해 동일한 key 값을 받는 경우 item의 뒤에 item을 만들게 된다.

hash table은 시간을 극대화 하는 대신에 공간을 많이 사용하게되는 자료구조이다.

이렇게 Stack, Queue, Hash에 대해서도 알아보았다.
점점 더 어려워 지는 것 같다. 내가 이들을 전부 다 이해하는데 얼마나 걸릴지 모르겠다.

뉴비