전체 글

Matrix Multiplication Multiply 2 N by N MatricesTakes O(N^3) Time using Normal MethodCan we do FASTER?  Apply Divide and Conquer  In the above method, we do 8 multiplications for matrices of size N/2 x N/2 and 4 additions. Addition of two matrices takes O(N^2) time. So the time complexity can be written asT(N) = 8T(N/2) + O(N2) From Master's Theorem, time complexity of above method is O(N3)whic..

SysV: Message Queue Message Formatstruct msgbuf { long mtype; /* type of message */ char mtext[N]; /* message text */} Can be thought of as a template for message datamtype is mandatory and must be a positive numbermtext is not restricted to holding only arrays of characters, but any data, in any formMessage Format은 보내고싶은 메시지의 템플릿이라고 볼 수 있습니다. SysV의 Message Queue에 들어가는 Message는 구조체로 만들어..

Goals and Requirements Non-Functional requirements may be very difficult to state precisely.Imprecise requirements may be difficult to verifyGoals are helpful to developers as they convey the intentions of the system users일반적으로 비기능 요구사항은 정확하게 언급, 작성하기 매우 힘듭니다. Brain-storming이나 Interview들의 기술들을 이용해서 user requirements를 뽑아내기 때문에 정확하게 정의할 수 없습니다. 이렇게 뽑힌 user requirements들 중 quality attributes들을 Goal..

Create int pipe(int pipefd[2]);int pipe(int pipefd[2], int flags);creates a pipe, a unidirectional data channeldata written to the write end of the pipe is buffered by the kernel until it is read from the read end of the pipepipefd[] is used to return two file descriptors referring to the ends of the pipepipefd[0]: read endpipefd[1]: write endpipe()의 인자로 int타입 배열을 넣어주면 r/w ends을 return해준다.flagsO..

Convex hull Find smallest Convex Polygon containing all the pointsConvex hull은 2차원 좌표 평면에 존재하는 여러 점들 중 일부를 이용하여 만들 수 있는 모든 점을 포함하는 볼록 다각형입니다. 그 볼록 다각형 중, 면적이 최소인 다각형을 찾으면 됩니다. 이때, 한 직선 위에 점이 3개 이상 있지 않다고 가정하겠습니다. CCW (Counter-Clock-Wise) 벡터의 외적을 통해서 세 점 A,B,C에 대해서 A,B,C를 순서대로 봤을 때, 반시계방향으로 놓여있는지, 아니면 시계방향으로 놓여있는지 알 수 있는 방법입니다. 결과적으로는,두 벡터간의 외적값이 양수라면, 반시계방향.외적값이 음수라면, 시계방향.0이라면 직선상에 있거나, 평행하는 경우..

Types of Non-Functional Requirements  Non-Fuctional ClassificationsProduct requirementsRequirements which specify that the delivered product must behave in a particular waye.g., excution speed, reliablity, etc.Organization requirementsRequirements which are a consequence of organisational policies and procedurese.g., process standards used, implementation requirements, etc.External requirementsR..

Closest Pair 2차원 평면 상에서 가장 가까운 두 점을 찾는 알고리즘 1-Dimensional Ver. 1차원인 경우는 NlogN에 가능하다는 것이 이미 증명이 되었다.1차원의 점들을 정렬을 해야지만 가장 가까운 두 점을 찾을 수 있기 때문에,정렬을 하는데 걸리는 시간인 O(NlogN)의 시간이 소모된다. How about 2-Dimensional Ver.? 우선 O(NlogN)보다는 크다; 1-Dimensional Ver. Inputs ⊆ 2-Dimensional Ver. Inputs 이기 때문그리고 그냥 Naive하게 푼다면 모든 점들 쌍에 대해서 거리를 계산해야하니 O(N^2)가 소모된다. Divide and ConquerSort by X coordinates and divide, recu..

Signals A very simple way of sending messages between two proecesses → Information transferred is limited to a signal number (standard signal)시그널은 프로세스간의 메시지를 주고 받는 가장 간단한 방법이지만, 그 정보가 시그널 숫자로 제한된다는 한계를 갖는다. Inter-Process Communication (IPC) Pipe → Stream oriented (e.g., TCP) → Data가 쌓이면 그냥 뭉쳐버린다.Message queue → Message oriented (e.g., UDP) → Data가 오면, 덩어리 (메시지) 단위로 쌓는다.Shared Memory → A virtual..