[TIL] 정글 32일차 - C언어, 레드 블랙 트리

신승준·2022년 4월 30일

TIL

목록 보기

20/34

Fork 저장소 동기화하기

https://dev-yakuza.posstree.com/ko/git/sync-fork-repository/

C 언어

C언어를 공부하기 전에 컴퓨터에 대해 알면 좋을 것 같아 모두의 코드님의 강의를 참고하였다.

컴퓨터에서 명령어는 누가 읽어들이는가?

CPU

CPU가 읽어들인다. 1초에 10억 정도 연산을 한다고 가정하면, CPU의 레지스터가 저장하기엔 너무 크기에 메모리(RAM)에 저장해둔다. Random Access Memory라는 말처럼, 메모리에 저장된 데이터에 임의로 바로 접근할 수 있다. 1이라는 주소에 저장된 데이터든, 100만이라는 주소에 저장된 데이터든 접근하는데 걸리는 시간이 같다는 것이다. 보통 데이터를 쓰고 읽는데 100나노초가 걸릴 정도로 속도가 매우 빠르지만 이는 CPU에 비해서는 턱없이 느린 셈이다. RAM은 휘발성으로 컴퓨터를 끄면 데이터가 다 날라가게 된다. CPU에서 연산 1개를 하는데 필요한 소요 시간은 0.3 나노초이지만 램에서 읽어들이는 데에는 100나노초가 걸리므로 상당히 비효율적이다. CPU는 기다리는 그 시간 동안 쉬게 되는 것이다.

L1 캐시에서 데이터를 가져오는 것이 가장 빠르다. 하지만 저장할 수 있는 공간이 적다.
HDD에는 많은 데이터를 저장할 수 있는 반면, 읽어들이는 데에 많은 시간을 소요하게 된다.

캐시(Cache)
이렇게 낭비되는 시간을 방지하기 위하여 CPU에 작은 저장 공간을 마련한 것이 캐시(Cache, 은닉처)이다.
공간 : L3 > L2 > L1
속도 : L1 > L2 > L3
CPU가 읽어들이는 명령어는 어떻게 작성되는가?
'CPU'마다 설계하는 방식이 여러가지 있어, CPU마다 사용하는 명령어 체계가 다르다. 각 CPU마다 알아들을 수 있는 명령어 모음을 명령어 집합, ISA라고 한다.
이러한 ISA에는 여러 가지 종류가 있다. Intel과 AMD에서 사용하는 x86이 있고, ARM의 ARM, RISC-V 등이 있다. 만약 x86 기반의 CPU가 ARM 기반의 코드를 받는다면 실행할 수 없게 된다. 이러한 명령어들은 이진 데이터로 CPU에 전달된다. CPU는 결국 0과 1의 이진 데이터를 통해 명령어들을 이해하게 되는데, 이는 반면 사람은 이해하기 심히 어려운 데이터이다. 따라서 사람이 그나마 이해하기 쉽게 나타낸 것이 어셈블리(Assembly)이다.

CPU에서 RAM의 특정 주소에 데이터 쓰기(feat. 어셈블리)

다음 3가지가 필요하다.

램의 어디에 쓸지
램에 무엇을 쓸지
램의 해당 위치부터 얼마만큼의 공간에 쓸지

<0x1234이라는 주소값에 3이라는 데이터 쓰기>

mov eax, 4660				// 4660은 0x1234를 10진으로 표기한 것이다. 4660을 eax에 복사해라
mov BYTE PTR [rax], 3

위 코드를 살펴보자.

EAX란
EAX는 CPU의 RAX 레지스터의 하위 32비트로, 마지막 4바이트를 의미한다.

mov eax, 4600

mov BYTE PTR [rax], 3		// RAX에 저장되어 있는 값에 위치한 메모리 방부터 1바이트 만큼에 3을 써라

1칸이 아니라 여러 바이트에 쓰고 싶다면,

mov DWORD PTR [rax], 3

16진수로 0003이 들어가게 된다.

CPU가 명령어를 읽어들이는 방법

CPU가 알아서 RIP(return instruction pointer) 레지스터 값을 업데이트하면서 명령어들을 읽어나간다. 0x401340에서 push rbp라는 1byte의 명령어를 수행하면 RIP가 그 다음 주소인 0x401341을 가리키게 되고 mov rbp, rsp라는 명령어에 따라 CPU가 작업을 수행한다.

프로그램을 실행한다는 것의 의미

하드 디스크에서 프로그램 정보를 램에 복사한다.
프로그램의 시작 위치로 RIP를 설정한다.

아무튼 CPU에 작업을 시키려면 어셈블리로 명령어를 작성하면 된다. 허나 이를 사람이 이해하기 쉽지 않아 만들어진 것이, 사람이 이해하기 쉽게 작성하는 명령어인 프로그래밍 언어이다.

컴파일

이 또한 어셈블리어로 바꾸어야 CPU가 읽을 수 있는데 이렇게 어셈블리로 바꿔주는 과정을 컴파일이라고 한다.

백준

13275, 가장 긴 팰린드롬 부분 문자열(문자열)
2775, 부녀회장이 될테야(기본 수학1)

Leetcode

5, Longest Palindromic Substring

하루를 마치고

금요일 - C언어 공부 + 각자 알아서 이론 공부
토요일 - 키워드 공부
일요일 - 키워드 공부한 것 발표 + linked list를 이용한 list, queue, tree ‘각자’ 구현 시도
월요일 - 각자 구현한 것 리뷰 + 이후 쭉 RB Tree 구현
*컴퓨터 시스템 + CLRS는 각자 읽기

이번 주차는 처음부터 조금 막막하여 요일별로 어떻게 할지 팀원들과 상의해보았다.