학교강의필기장

함수(프로시저)는 프로그램을 이해하기 쉽고 코드를 재사용할 수 있도록 만들어준다. 함수 호출 과정에서는 호출자와 호출 대상간의 관계가 형성된다. 호출자는 함수를 호출하는 프로그램, 호출 대상은 함수를 실행하는 프로시저이다. 호출 대상이 다른 함수를 호출하면 호출 대상은 호출자가 된다. 1) 호출자는 매개변수를 호출 대상이 접근할 수 있는 장소에 둔다. 2) 제어가 호출 대상으로 전달된다. 3) 호출 대상은 프로시저에게 필요한 저장 공간 자원을 할당한다. 4) 호출 대상은 필요한 작업을 수행한다. 5) 호출 대상은 결과 값을 호출자가 접근할 수 있는 장소에 놓는다. 6) 제어가 호출자로 반환된다. 1~3번은 함수 호출, 4번은 함수 실행, 5~6번은 함수 반환을 뜻한다. 함수 관련 레지스터는 다음과 같다...

MIPS에서 shift 연산은 sll, srl 연산으로 할 수 있다. sll(shift left logical)은 왼쪽 쉬프트 연산, srl(shift right logical)은 오른쪽 쉬프트 연산을 수행한다. rs에 0이 들어가고 첫 번째 인자는 rt, 두 번째 인자는 rd에 들어간다. LEFT SHIFT $t0 = $s0 > 1 srl $t0, $s0, 1 AND $t0 = $t1 & $t2 and $t0, $t1, $t2 AND immediate $t0 = $t1 & 8 andi $t0, $t1, 8 OR $t0 = $t1 | $t2 or $t0, $t1, $t2 OR immediate $t0 = $t1 | 8 ori $t0, $t1, 8 NOR $t0 = ~($t1 | $t2) nor $t0, ..

MIPS에서는 1워드 = 4바이트 = 32비트를 기반으로 한다. 32비트의 워드에서는 2^32개의 서로 다른 비트 패턴을 나타낼 수 있다. 첫 번째 비트가 0이라면 양수, 1이라면 음수인 2의 보수 방식을 사용할 수 있고, 이를 사용하면 음수와 양수 모두에서 산술연산을 간단하게 처리할 수 있다. 덧셈 연산과 같은 명령어도 1워드로 나타낸다. 위는 그 예제로, 첫 번째 필드와 마지막 필드는 이 명령어가 add임을 나타내고, 2,3,4번째 필드는 각각 s1 s2 t0를 나타낸다. add 명령어와 같은 구조를 R-Type이라 하며, 6가지의 필드로 나타난다. op: 명령어의 기본 연산 opcode rs : 첫 번째 소스 레지스터의 번호 rt : 두 번째 소스 레지스터의 번호 rd : 세 번째 소스 레지스터의 ..

컴퓨터 언어는 명령어(instructions)로 구성돼있으며 각 컴퓨터는 자신만의 명령어 목록(instruction set)으로 구성돼있다. 대표적인 instruction set으로는 arm, intel x86, MIPS 등이 있다. 하드웨어의 기술은 유사한 기본 원리에 기반하고, 모든 하드웨어 기술은 몇 가지 기본 작업을 수행해야하기 때문에 각각의 instructions set은 매우 유사하다. MIPS CPU에는 32개의 레지스터가 있고, 각 레지스터의 크기는 32bit이다. 레지스터는 0~31의 이름을 가지며 각 레지스터는 고유한 이름과 용도를 지닌다. 레지스터를 통해 데이터를 메모리에서 가지고 오는 비용을 줄일 수 있지만, 레지스터의 크기는 한정돼있기에 효율적으로 사용해야한다. g+h를 t0에 저..

하드웨어 위에서 애플리케이션 소프트웨어가 작동할 수 있도록 돕는 역할인 시스템 소프트웨어는 두 가지가 있다. - 운영체제 : 메모리와 저장소를 관리하고, IO 명령을 관리하며 다수의 프로세스/스레드가 충돌하지 않도록 관리함 - 컴파일러 : high-level language로 작성된 프로그램을 하드웨어가 실행할 수 있는 프로그램으로 바꿔줌 * 컴파일러는 building 과정을 통해 object 파일을 생성하고, linking을 하여 실행 파일을 생성함. * 점차 최적화 기술이 발전해서 더욱 효율적인 기계어를 생성할 수 있게 됨. 컴퓨터의 성능을 판단하는 두 가지 지표 - Response time, Execution time (응답시간, 실행시간) * 어떤 작업이 시작부터 완료까지의 걸린 시간 * 이 지표..

A1, A2, A3 이 세 행렬이 있고, A1은 3*5 A2는 5*1 A3는 1*2 행렬이라고 합시다. 행렬의 곱셈에서도 결합법칙은 성립하는데, 위 예시에서는 (A1*A2)*A3, A1*(A2*A3) 이 두 가지가 가능합니다. 그런데, 앞 식에서는 3*5*1 + 3*1*2 = 21번 연산, 뒷 식에서는 5*1*2 + 3*5*2 = 40번을 연산하게 됩니다. 즉 행렬의 곱셈은 연산 순서에 따라 연산 횟수가 달라지게 됩니다. 이때 최소 연산 횟수와 연산 순서를 구하는 알고리즘이 연쇄 행렬 곱셈 알고리즘입니다. 코드는 다음과 같습니다. int chainedMatrix(int n, int d[], int P[][N]){ int dp[N][N] = {}; for(int diag=1; diag A1 * ((A2 *..

플로이드 알고리즘은 모든 정점끼리의 최단경로를 구하는 문제입니다. void floyd(int n, int S[][N], int P[][N]){ for(int i=0; i

이항계수 알고리즘은 누구나 한 번쯤 들어봤을 법한 파스칼의 삼각형, 조합을 구하는 알고리즘입니다. 고등학교 수학에서 nCk라 표현하던 식은 2*1 행렬로 표현할 수 있습니다. 위의 식을 참고해서 분할정복으로 풀어보면, int binomial(int n, int k){ if(k==0 || k==n) return 1; return binomial(n-1,k-1)+binomial(n-1,k); } 다음과 같은 간단한 코드가 나옵니다.. 본래 DP로 접근해야 할 문제인데, 분할정복으로 접근했을 때 얼마나 비효율적인지 구해봅시다. 무려 시간복잡도가 n! 가 나옵니다. 가장 높은 수준이라고 할 수 있지요. 이제 DP로 접근해볼건데, 분할정복과 아이디어는 같습니다. int binomial(int n, int k){ ..