Quick Sort Definition int qsort(int a[], int n){ int d; int p = a[0]; //Rearrange a[] so that // a[d] == p // a[0], a[1], ..., a[d-1] p qsort(a,d); qsort(a+d+1, n-d-1); return ;}a[0]에 있던 값이 p이고, p가 d에 가도록 rearrange한다.* rearrange란 ? 값이 없어지지 않고 그대로 유지되지만 위치만 바뀐다a[0]부터, a[d-1]까지 있는 얘들은 모두 p보다 작음a[d+1]부터, a[n-1]까지는 모두 p보다 큼> O(n) 시간 안에 해결함 Q) 어떻게 O(n)시간에 해결하는가?A)1. p보다 큰건 +라..

Compile | 컴파일컴파일은 인간이 이해할 수 있는 언어로 작성된 소스코드를 CPU가 이해할 수 있는 언어로 변환하는 작업즉, 바이너리 형태로 변환하는 작업이다. (기계어)Pre-Processing : 전처리기 (Pre-processor)을 통해 소스 파일을 수정된 소스 파일 (전처리된 소스 파일)로 변환Compilation : 컴파일러 (Compiler)을 통해 수정된 소스 파일을 어셈블리 파일로 변환Assembly : 어셈블러 (Assembler)을 통해 어셈블리어 파일을 오브젝트 파일로 변환 - 오브젝트 파일부터 바이너리 형태Linking : 링커 (Linker)을 통해 오브젝트 파일들과 라이브러리, 헤더 파일들을 하나로 묶어 실행 파일로 변환이때 Linking 과정에서 Static Linkin..

문제프로그램 M과 입력 X가 있을 때, M에 입력 X를 주고 수행시키면 종료할 것인가? M은 그냥 어떠한 프로그램 X는 어떠한 문자열 ex) abcabadM과 X가 모두 문자열이라고 가정함 명확한 두 가지 경우가 존재함1. 멈추는 것을 알 수 있는 경우 * 안 읽고 멈추는 것도 멈추는 것임 2. 멈추지 않는 것을 알 수 있는 경우 ex) 문자열을 입력받고 또 다음 문자열을 위해 기다리는 행위 등 HALTING Problem은 어떤 프로그램이 종료하지 않는지를 돌려보기 전에 알아야한다.Q. 돌려보기 전에 알아야하는 이유는 뭘까?A. 돌려봐서 끝난다면 끝나는 것을 알 수 있지만, 안 끝나고 있다면 "언젠가는" 끝난다는 것을 말할 수 있어야함ex) 10시간을 기다렸기에 끝나지 않을지, 10시간을 기다렸지만 언..

.text:00401000 55 push ebp.text:00401001 8B EC mov ebp, esp.text:00401003 68 F8 20 40 00 push offset Buffer ; "Hello World :)".text:00401008 FF 15 B0 20 40 00 call ds:__imp__puts.text:0040100E 83 C4 04 add esp, 4.text:00401011 FF ..

General-Purpose register여러가지 목적이나 용도로 사용하는 레지스터프로그래머가 자유롭게 조작 할 수 있음일종의 변수라고 생각할 수 있음인텔의 공식 문서에 따르면 32비트의 시스템의 경우 8개가 존재인텔의 공식 문서에 따르면 64비트의 시스템의 경우 16개가 존재용도나 목적이 정해져있지 않음 (그렇지만 일반적으로 어떠할 때 사용한다는 것은 존재함)* RAX, RBX, RCX, RDX 2byte 중 상위 1byte에 접근할 수 있음더보기[ 범용 레지스터의 용도/목적 ] 실질적으로 정해져있는 것은 아니지만 주로 사용함EAX : 피연산자와 연산 결과의 저장소EBX : data segment 안의 데이터를 가리키는 포인터ECX : 문자열 처리나 루프를 위한 카운터EDX : I/O 포인터ESI :..

어셈블리어 : 기계어와 일대일 대응되는 저급 언어IntelAT&Tmov eax, 1movl $1, %eaxlea ecx, [ebx+eax*2]leal (%ebx, %eax,2), %ecx같은 문법이 Intel과 AT&T인가에 따라 달라짐 더보기[ 어셈블리의 피연산자 ] 상수, 레지스터, 메모리 셋 중 하나이다 메모리에 접근하려면TYPE PTR [레지스터 or 상수] 형태이다 ex) QWORD PTR [rax+8]접미사mov eax, 1movl $1, %eax intel의 경우 단순 명령어만 적지만, AT&T의 경우 해당 명령어가 어떤 크기의 명령어인지 나타낸다예시를 보면, eax는 4바이트이므로 long이다. [b] byte : 1byte[w] word : 2byte[l] long(double word)..

Scheduling MetricsTurnaround time\[T_{turnaround} = T_{completion} - T_{arrival}\]프로세스가 생성된 시간부터 종료된 시간까지 걸린 시간으로 기다린 시간까지 포함Response time\[T_{response} = T_{firstrun} - T_{arrival}\]처음 실행때까지 걸린 시간 / 즉 요청을 보낸 후 처음 프로세스가 실행된 시간  Workload Assumptions cpu의 운영 방식을 가정하면서 가장 효율적인 CPU scheduling 방식이 무엇인지 찾아보고자 한다.Each job runs for the same amount of time ( 모든 프로세스가 같은 시간이 소요됨 )All jobs arrive at the sa..

Von Neumann Architecture 폰 노이만 구조거의 모든 컴퓨터의 기본이 되는 구조Idea연산제어저장세 가지의 핵심 기능이 필요함 연산 & 제어 → CPU저장 → memory장치 간 데이터 및 신호 교환 → bus CPU 중앙 처리 장치ALU (산술 논리 장치) : 산술 및 논리 연산을 실행함Control Unit : CPU를 제어하는 제어장치Register (레지스터) : CPU에 필요한 데이터를 저장함 - Program counter 등이 포함되어 있음등으로 이루어짐 Memory 기억장치주기억장치 (Ram) : 프로그램 실행과정에서 필요한 데이터들을 임시로 저장하기 위해 사용보조기억장치 (HDD, SSD) : 운영 체제, 프로그램 등과 같은 데이터를 장기간 보관하고자 할 때 사용 Bus ..

Subgraphs그래프의 일부 Defintion Let G = (V,E) and H = (W,F) be graphs. H is said to be a subgraph of G, if \(W\subseteq V\) and \(F\subseteq E\)G와 H가 모두 그래프이고, W가 V의 부분집합, F가 E의 부분 집합일 때 subgraph라고 한다 Q.How many \(Q_2\) subgraphs does \(Q_3\) have?A. 같다의 약한 개념에서는 6, 강한 개념에서는 1개이다노드에 번호를 부여하였을 때, 노드의 번호가 다르다면, 다른 그래프이기 때문에 \(Q_2\)에 1,2,3,4라는 노드 번호와 일치해야한다. Unions강하게 같다 라는 개념을 사용하여 Q.How many \(Q_2\) s..

Graph basics and definitionsVertices / nodes : 노드, 점edges : 선adjacency / incidence : 인접 - 두개의 뜻이 어떻게 다를까?Degree, in-degree, out-degree : 차수Subgraphs, unions, isomorphismAdjacency matrics (인접 행렬)Graph의 종류TreesUndirected graphs - simple graphs, Multigraphs, PseudographsDigraphs, Directed multigraphBipartiteComplete graphs, cycles, wheels, cubes, complete bipartiteIntuitive Notion 정의 A graph is a b..