🖥 Computer Science

🧐 Spanning Tree 그레프 내의 모든 정점을 포함하는 트리들 중, 최소 연결 트리를 의미합니다. 최소 연결의 의미는 간선의 수가 가장 적다는 것을 의미하며, 이를 위해서는 사이클이 존재해서는 안됩니다. 따라서 정점의 수가 $n$ 개인 그래프의 Spanning Tree는 edge가 정확히 $n-1$ 개 존재합니다. 또한 하나의 그래프에는 많은 신장 트리가 존재할 수 있습니다. 🧐 최소 신장 트리 (MST) 신장 트리들 중 edge들의 비용(cost)의 총 합이 최소인 트리를 의미합니다. 동일한 Cost를 가지는 Edge가 여러개 있을 경우 MST도 여러 종류가 나올 수 있으며, 반대로 모든 Edge들의 cost가 구분가능한 경우 MST는 단 하나만 존재할 수 있습니다. (이는 뒤에서 증명해 보도록..

🧐 그리디 알고리즘 그리디 알고리즘이란 매 단계마다 현재 상태에서 최적의 해를 만들어주는 것을 선택하며 진행하는 알고리즘입니다. 주로 최적화 문제(Optimization problem)에서 많이 사용되는 알고리즘으로, 대부분의 문제들에서 그리디 알고리즘은 최적해(global-optimal)를 보장해 주지는 않으나 일부 문제들에 한하여 global-optimal 하거나 그에 매우 근접함을 보장해 주는 경우가 있습니다. ⭐️ 그리디 알고리즘 예시 N개의 숫자가 들어있는 바구니가 있습니다. 이 중 그 수들의 합이 최대가 되도록 m개를 고르고 싶습니다. 이러한 경우 그리디 알고리즘을 통해 매 단계에서 현재 바구니에 남아있는 숫자들 중, 제일 큰 숫자를 고른 뒤, 이를 m 번 반복함으로써 문제를 해결할 수 있습니..

RISC-V는 명령어의 길이를 32비트로 고정하여 하드웨어를 간단하게 만들었으나, 명령어 내에 32비트 이상의 상수나 주소를 표시할 수 없어 불편한 점도 있습니다. 이번에는 이러한 긴 상수 처리를 위한 일반적인 해법과, 분기 명령어에서 사용되는 명령어 주소의 최적화 방법을 알아보겠습니다. 🧐 큰 수치 피연산자 프로그램에서 사용하는 상수는 대체로 크기가 작으므로, 대부분의 경우 12비트 내로 표현이 가능합니다. 그러나 그렇지 않은 경우도 있으므로 더 큰 상수를 다룰 수 있어야 합니다. 이를 위해 RISC-V는 레지스터의 비트 12번째자리부터 31번째 자리까지에 20비트 상수값을 넣는 lui(load upper immediate) 명령어를 제공합니다. 위 명령어를 사용하면 남은 하위 12비트 공간은 0으로 ..

🧐 반복문 기계어에는 반복문에 대응되는 인스트럭션이 없습니다. 그 대신 조건부 테스트와, 점프 인스트럭션을 함께 사용하여 반복문을 표현합니다. GCC 와 다른 컴파일러들은 반복문을 두 개의 기본 루프 패턴에 기초하여 코드를 생성합니다. 가장 간단한 do-while부터 시작하여 보다 복잡한 구현 방법을 살펴보며 두 가지 패턴을 다루도록 하겠습니다. 🧐 do - while do-while 문장의 일반적인 형태는 아래와 같습니다. do { body-statement } while ( test-expr ); 반복문은 body-statement 를 반복적으로 실행하고, test-expr 을 계산하여 그 결과가 0이 아니라면 반복합니다. body-statement 는 적어도 한 번 실행된다는 것에 주목하며, 해당 ..

🧐 제어 명령 여러 조건문들을 사용하기 위해 제어 명령이 필요합니다. 일반적으로 CPU 내부에 상태를 저장할 수 없기 때문에, 레지스터에 상태를 저장하게 됩니다. %rax 레지스터는 임시 데이터, 연산의 결과 등을 저장하며 %rsp 레지스터는 런타임 스택의 위치를, %rip 레지스터는 현재 실행코드의 위치를 저장합니다. 그리고 최근 진행한 연산의 결과에 따라 상태가 변경되는 4종류의 (1비트) 플래그 레지스터가 존재합니다. 이름은 CF, ZF, SF, OF이며, 이들을 통해 조건문 등의 제어를 진행합니다. 🧐 Conditional Codes (조건 코드) 플래그 레지스터는 조건코드 레지스터라고도 불립니다. 이들은 산술 연산의 결과에 따라 값이 바뀌는 레지스터들입니다. 주의하여야 할 점은 movq 혹은 l..

🧐 기계수준 코드 하나의 기계어 인스트럭션은 매우 기초적인 동작만을 수행합니다. 예를 들어 레지스터들에 저장된 두 개의 수를 더하고, 메모리와 레지스터 간에 데이터를 교환하거나, 새로운 인스트럭션 주소로 조건에 따라 분기하는 등의 동작을 수행합니다. 컴파일러는 일련의 인스트럭션을 생성해서 산술연산식의 계산, 반복문 프로시저 호출과 리턴 등의 프로그램 구문을 구현해야 합니다. 🧐 어셈블리어 기계어에 1대1 대응관계를 갖는 명령어로 이루어진 low-level 프로그래밍 언어입니다. ⭐️ 코드 예제 long plus(long x, long y); void sumstore(long x, long y, long * dest) { long t = plus(x, y); *dest = t; } 위의 코드를 어셈블리어로..

🧐 프로시저 (procedure) 프로시저나 함수는 이해하기 쉽고, 재사용이 가능하도록 프로그램을 구조화하는 방법 중 하나입니다. 프로그램이 프로시저를 실행할 때에는 다음과 같이 여섯 단계를 거쳐야 합니다. 1. 프로시저가 접근할 수 있는 곳에 인수를 넣는다. ( x10 - x17 레지스터 사용 ) 2. 프로시저로 제어를 넘긴다. ( jal x1, ProcedureAddress 명령어 사용 ) 3. 프로시저가 필요로 하는 메모리 자원을 획득한다. 4. 필요한 작업을 수행한다. 5. 호출한 프로그램이 접근할 수 있는 장소에 결과값을 넣는다. ( x10 - x17 레지스터 사용 ) 6. 프로시저는 프로그램 내의 여러 곳에서 호출될 수 있으므로, 원래 위치로 제어권을 돌려준다. ( jalr x0, 0(x1) ..

🧐 의사 결정 명령어 컴퓨터는 단순히 산술 연산만을 진행하지 않습니다. 입력 데이터나 연산 결과에 따라 다른 명령어를 실행할 수 있습니다. 프로그래밍 언어에서는 보통 if 문장을 통해서 판단 기능을 표현합니다. RISC-V 어셈블리어에서는 go to 가 있는 if 문과 비슷한 판단 명령어를 가집니다. 두개의 명령어를 본 후 넘어가도록 하겠습니다. ⭐️ beq - 같으면 분기한다. beq rs1, rs2, L1 위 명령어는 rs1의 값이 rs2의 값과 같은 경우 L1으로 이동하라는 뜻입니다. ⭐️ bne - 같지 않으면 분기한다. bne rs1, rs2, L1 위 명령어는 rs1의 값이 rs2의 값과 같지 않은 경우 L1으로 이동하라는 뜻입니다. 🧐 조건부 분기 (Conditional branch) 조건부..