혼자 정리

(구체적 슈트라센 알고리즘은 생략함) 정방행렬의 곱은 다음으로 일반화할 수 있다. $A = (a_{ij})$이고 $B = (b_{ij})$인 $n \times n$행렬일 때, $C = A \cdot B$의 원소 $c_{ij}$는 $i,j = 1,2, \cdots, n$에 대해 다음과 같이 나타낼 수 있다. $$ c_{ij} = \sum_{k=1}^{n} a_{ik} \cdot b_{kj} $$ 이를 단순한 방법으로 연산을 시키면 각 (for i = 1 to n) (for j = 1 to n)마다 (for k = 1 to n)번의 $a_{ik} \cdot b_{kj}$의 연산이 있어야 하므로, $\Theta(n^3)$의 시간이 소요된다. 언뜻 생각하기에는 $\Omega(3)$의 시간이 걸릴 것 같지만 $o..

특정 기간 내에 어떤 자산을 매수/매도를 해서 가장 높은 수익률을 내는 문제를 생각해 보자. 가장 낮은 가격이 등장한 뒤에 가장 높은 가격이 등장하면, 두 가격을 찾아서 매수/매도를 하면 되지만 일반적으로 그렇지 않다. A brute-force solution 기간의 범위가 n개로 쪼개져있다고 했을 때 단순하게 모든 매수/매도 선택지에 대해 최대 수익률을 구하기 위해서는 $\binom{n}{2}$번의 연산을 해야 하고, 이는 $\Theta(n^2)$의 시간이 필요함을 의미한다. 이는 최악의 경우도 아니고 최선의 경우에도 모든 것을 찾는 것이므로 $\Omega(n^2)$의 시간으로 볼 수 있다. A transformation 문제를 더 효율적으로 풀기 위해 우선 각 날짜의 '가격' 즉, 수준 변수 대신 날..

2.2 정수의 표시 signed integer와 unsigned integer를 인코딩하는 방법에 대해 살펴볼 것. 또한 인코딩된 정수를 길이가 다른 표현에 맞게 확장 or 축소하는 방법도 볼 것이다. 다음은 정수 인코딩 공부 과정에서 참조 가능한 수학적 용어들에 대한 표이다($\omega$는 데이터 표시에 필요한 비트 수를 의미). Symbol Type Meaning Page(한글판/영문판) $B2T_{\omega}$ Function Binary to two's complement 63/100 $B2U_{\omega}$ Function Binary to unsigned 61/98 $U2B_{\omega}$ Function Unsigned to binary 63/100 $U2T_{\omega}$ Func..

2.1 정보의 저장 기계수준의 프로그램은 메모리를 '가상메모리(virtual memory)'로 부르는 거대한 바이트의 배열로 취급. 메모리의 각 바이트는 주소로 식별할 수 있고, 모든 가능한 주소의 집합을 '가상 주소공간(virtual address space)'이라 부름(이는 기계수준 프로그램에게 제공되는 개념적인 이미지). 2.1.1 16진수 표시 C에서 0x나 0X로 시작하는 숫자 상수는 16진수로 해석. 'A'에서 'F'까지 대소문자 모두, 혼용 여부에 상관없이 16진수 자릿수로 해석(ex. 0xFA1D37B == 0xfa1d37b == 0xFa1D37b) Hex digit 0 1 2 3 4 5 6 7 Decimal value 0 1 2 3 4 5 6 7 Binary value 0000 0001 ..