🖥 Computer Science

부족한 부분이 많아 코드가 그리 깔끔하지는 않습니다.. ㅠ (시프 다들 화이팅하세요😊) 🧐 addOK /* * addOK - Determine if can compute x+y without overflow * Example: addOK(0x80000000,0x80000000) = 0, * addOK(0x80000000,0x70000000) = 1, * Legal ops: ! ~ & ^ | + > * Max ops: 20 * Rating: 3 */ int addOK(int x, int y) { /* * Overflow가 발생하는 경우는 다음과 같다. * (1) MSB_X = 0, MSB_Y = 0, MSB_(X+Y) = 1 * (2) MSB_X = 1, MSB_Y = 1, MSB_(X+Y) = 0 * *..

🧐 유니온 파인드 자료구조 유니온 파인드 자료구조(또는 서로소 집합(disjoint set) 자료구조)는 다음 두 종류의 연산을 지원하는 자료구조입니다. Union : 두 개의 노드가 포함된 집합을 하나의 집합으로 합치는 연산 Find : 특정 노드가 속한 집합의 루트 노드를 반환하는 연산 우선 동빈나님의 설명이 굉장히 좋기 때문에, 동빈나님의 유튜브 링크를 걸어두도록 하겠습니다. ( 저는 그냥 제가 공부하려고 글 쓴 거니까, 유튜브 보러 가세여..ㅠㅠ ) ⭐️ Find 연산 Find 연산은 다음과 같은 알고리즘을 통해 구현할 수 있습니다. 1. 해당 노드의 부모 노드와 해당 노드를 비교합니다. 이때 두 노드가 같은 경우, 해당 노드는 루트 노드입니다. 2. 만약 같지 않다면 해당 노드의 부모 노드에 대..

컴퓨터에서는 소수를 표현하기 위해 부동소수점 표현을 사용합니다. 부동소수점 표현은 $V = x \times 2^{y}$ 형태의 소수를 인코딩합니다. 현재 대부분의 컴퓨터는 IEEE 부동소수점 표준 의 방식을 지원합니다. 이제부터 숫자를 어떻게 IEEE 부동소수점 형식으로 나타내는지와, 숫자를 해당 형태로 정확하게 나타낼 수 없을 때 수행하게 되는 근사(rounding)에 대해 알아보도록 하겠습니다. 🧐 비율 이진수 부동소수점에 대해 알아보기 전, 비율 이진수에 대해 알아보도록 하겠습니다. 비율 이진수의 표기는 다음과 같습니다. $$b_m \;b_{m-1}\; ... b_2\; b_1\; b_0\; .\; b_{-1} \;b_{-2}\; ... \;b_{-n+1}\; b_{-n}$$ 이진 소수점 좌측의 숫..

🧐 논리 연산 명령어 논리 연산의 종류로는 Shift 연산과, 비트별 AND, OR, XOR, NOT 의 연산이 존재합니다. 이번 글에서는 이러한 논리 연산 명령어들에 대해 알아보도록 하겠습니다. 🧐 Shift 연산 Shift 명령어는 워드 내의 모든 비트를 왼쪽 또는 오른쪽으로 이동시키고, 이동 후 빈자리는 0으로 채우는 명령어입니다. 예를 들어서 x19 레지스터에 다음과 같은 값이 있다고 가정하면 $00000000 \;\;00000000 \;\;00000000 \;\;0000$$1001_2 \;\;$$ = 9_{10} $ 왼쪽으로 4번 Shift 시키는 명령어를 실행시키면 다음과 같아집니다. $00000000 \;\; 00000000 \;\; 00000000 \;\; $$1001$$0000_2 \;\..

🧐 명령어 형식 (Instruction Format) 명령어는 명령 코드와 피연산자로 이루어집니다. 명령어들은 이진수로 인코딩되기 때문에, 명령어의 각 부분을 숫자로 볼 수 있습니다. 다음 예제를 통해 좀 더 자세히 살펴보도록 하겠습니다. 😮‍💨 예제 아래 어셈블리 명령어의 RISC-V 언어 버전을 십진수와 이진수로 표현해 보도록 하겠습니다. add x9, x20, x21 십진수 표현은 다음과 같습니다. 0 21 20 0 9 51 명령어의 각 부분을 필드(Field)라 부릅니다. 위에서 첫 번째, 네 번째, 여섯 번째 필드(0, 0, 51 부분)는 RISC-V 컴퓨터에게 이 명령어는 덧셈을 수행한다고 알려주는 부분입니다. 두 번째 필드는 덧셈에 사용할 두 번째 피연산자 레지스터의 번호( 21 = x21 ..

🧐 피연산자 (Operands) 산술 명령어의 피연산자에는 제약이 있습니다. 레지스터(register)의 주소 혹은 상수만이 해당 위치에 올 수 있습니다. RISC-V 컴퓨터는 32개의 레지스터를 가지고 있으며, 각각의 레지스터는 64비트를 저장할 수 있습니다. (32비트 컴퓨터의 경우 레지스터는 32비트를 저장할 수 있습니다.) 각각의 레지스터는 x0 부터 x31 까지의 주소를 가집니다. 여기서 워드(Word)라는 단어가 등장하는데, 워드는 컴퓨터에서의 접근 단위이며, 레지스터의 크기에 해당합니다. 그러나 본래의 의미와는 다르게 일반적으로 Word라고 하면 32비트를 떠올리며, 64비트 컴퓨터에서는 Word가 64비트이지만 Word는 32비트라는 인식이 강하므로, 64비트를 나타내기 위해 Double ..

🧐 명령어 컴퓨터의 하드웨어에게 일을 시키기 위해서는, 하드웨어가 알아들을 수 있는 언어로 명령을 해야 합니다. 컴퓨터 언어에서의 단어를 명령어(Instruction)라 칭합니다. 그리고 어떠한 CPU가 이해할 수 있는 명령어들을 모아놓은 것을 명령어 집합(Instruction set)이라 부릅니다. ISA가 다른 컴퓨터들은, 모두 다른 명령어 집합을 가지고 있습니다. 그러나 모두 유사한 구조를 가지고 있기에, 하나를 배우면 다른 것들도 쉽게 익숙해질 수 있습니다. 앞으로 등장하는 모든 명령어 집합은 RISC-V 입니다. ✏️ 참고 : CISC와 RISC CISC : Complex Instruction Set Computer RISC : Reduced Instruction Set Computer CISC..

🧐 Strongly Connected 방향 그래프에서는 무방향 그래프와 동일하게 Connectivity(연결성)를 정의할 수 없습니다. 방향 그래프에서의 Connectivity는 보통 Strongly Connected 로 정의되며, 해당 정의는 다음과 같습니다. $G$ 는 Strongly Connected 하다 : 임의의 서로 다른 두 정점 $v$, $u$ $\in V(G)$ 에 대하여, $v$ 에서 $w$ 로의 Path와, $w$ 에서 $v$ 로의 Path가 존재한다. 🧐 Strongly Connected Components (강한 연결 요소) 그래프 $G$에 대한 Strong Connected Component $G'$ : $G$ 의 Maximal Strongly Connected Subgraph $..