inchori

4.1 The Y86-64 Instruction Set Architecutre 4.1.1 Programmer-Visible State Y86-64의 각 명령어들은 프로세서 상태의 어떤 부분을 읽고 수정할 수 있다. 프로그래머에게 보여지는 상태(programmer-visible state)라고 하며, 프로그래머는 어셈블리 코드로 프로그램을 작성할 수 있고 기계 수준의 코드를 생성하는 컴파일러를 작성할 수 있다. 15개의 프로그램 레지스터가 있다. (%rax, %rax, %rcx, %rdx, %rbx, %rsp, %rbp, %rsi, %rdi, and %r8 through %r14) 각 레지스터들은 64비트 word를 저장한다. 레지스터 %rsp는 push, pop, call, return 명령어를 이용하여..

그래프(Graph)는 G = (V, E)로 표현 가능하다 그래프는 V는 정점(Vertex)이고 E는 간선(Edge)로 구성되어 있다. 많은 알고리즘 문제들을 푸는 핵심은 그래프의 측면에서 생각하는 것 그래프의 특징 - 무방향(undirected) 그래프 vs 방향(directed) 그래프 G = (V, E)에서 (x, y) 간선이 (y, x)을 의미하면 무방향 그래프, 아니면 방향 그래프 - 가중(weighted) 그래프 vs 비가중(unweighted) 그래프 각 에지에 가중치라고 부르는 수치가 할당 두 정점 사이의 최단 경로를 구할 때 분명해진다 비가중 그래프에서 최단 경로는 최소 에지의 개수이며 BFS로 구할 수 있다. - 단순(simple) 그래프 vs 비단순(non-simple) 그래프 자기-루..

퀵 정렬(Quick Sort): 랜덤화에 의한 정렬 정렬을 하려는 n개의 원소들로부터 랜덤 원소 p를 피벗(pivot)으로 선택 퀵 정렬은 피벗 p를 제외한 n - 1개의 원소들을 두 부분으로 분리: - 왼쪽 부분에는 정렬된 순서에서 p보다 먼저 나오는 원소 - 오른쪽 부분에는 정렬된 순서에서 p보다 나중에 나오는 원소 피벗 p는 정렬이 끝난 순서에서 위치하여야 할 배열의 자리에 머무르게 된다. 분할된 후 한쪽 편에 있는 어떠한 원소도 마지막 정렬된 순서에서 다른 쪽으로 옮겨지지 않는다 -> 피벗의 양쪽으로 나뉘어져 있는 원소들은 서로 독립적으로 정렬 가능 (재귀 알고리즘 표현 가능) quick_sort(item_type s[], int l, int h) { int p; if ((h - 1) > 0) {..

정렬을 주목해야 하는 이유 - 정렬은 알고리즘을 설계하는 데에 있어서 기본적인 구성요소(Building Block) 역할을 한다. - 분할-정복, 자료구조 등과 같은 알고리즘 설계에 사용되는 흥미 있는 아이디어들이 정렬의 과정에서 나타난다. - 역사적으로 컴퓨터는 다른 어떤 것보다도 정렬에 많은 시간을 할애하였다. 정렬의 응용 - 탐색 : 모든 값들이 정렬된 경우 이진 탐색을 사용하면 O(logN) 시간에 검사할 수 있다. - 최근접쌍(Closest Pair) : N개의 숫자가 주어질 경우, 차이가 가장 작은 두 수를 어떻게 찾을까? 정렬을 사용하면 O(NlogN)의 시간을 가진다. - 원소 유일성 - 도수 분포 : N개의 원소가 주어졌을 때 어떤 원소가 가장 많은 빈도로 나타내는가? 원소들이 정렬되어 ..

/** 자료구조는 따로 다시 정리할 예정**/ 이진 탐색 트리(Binary Search Tree) 이진 탐색을 이용하기 위해서는 두 원소에 대한 빠른 접근 필요 루트 있는 이진 트리의 재귀적 정의 1. 아무것도 없음 2. 루트로 불리는 한 노드와 왼쪽 서브트리와 오른쪽 서브트리로 구성 이진 탐색 트리에서는 이진트리의 각 노드에 하나의 키의 라벨이 있다. 어떤 노드의 값이 x이면, - 왼쪽 서브트리에 있는 모든 노드들의 값은 x보다 작다. - 오른쪽 서브트리에 있는 모든 노드들의 값은 x보다 크다. 이진 탐색 트리의 구현 typedef struct tree { item_type item; struct tree *root; struct tree *left; struct tree *right; } 트리에서의 ..

/** 자료구조는 따로 다시 정리할 예정**/ 연속(Contiguous) 대 연결 자료구조(Linked Data Structures) 자료구조는 배열에 따라 구현 vs 포인터에 따라 구현 - 연속적 자료구조는 메모리의 연속된 한 구역으로 구성 배열, 행렬, 힙, 해시 테이블 등 - 연결된 자료구조는 포인터에 의해 뚜렷이 구분되는 메모리의 구역들로 구성 리스트, 트리, 그래프 등 배열(Array) 연속적으로 자료가 할당되는 가장 핵심적인 자료구조 각 원소들을 인덱스 혹은 주소로 그 위치를 찾을 수 있는 고정 크기(fixed-size) 구조 연속적으로 할당된 배열의 장법 - 주어진 인덱스로 상수 시간 접근 : 배열의 인덱스만 알면 데이터 요소 즉시 접근 가능 - 공간 효율성 - 메모리 지역성 : 배열은 매우..

2. 알고리즘 분석 알고리즘 분석의 가장 중요한 도구는 1) RAM 계산 모델 2) 최악의 경우(worst-case)의 점근적 분석(asymptotic analysis)이다. RAM 계산 모델 기계-독립적인 알고리즘 설계는 임의 접근 기계(Random Access Machine: RAM) 가상의 컴퓨터에 달려있다. 가상의 컴퓨터의 특징 - 각각의 단순 연산은 하나의 단계 동안에 실행 - 루프와 서브루틴은 단순 연산이 아니다. - 메모리 접근은 하나의 단계 동안에 이루어진다. 메모리 크기는 무한하여, 원하는 만큼의 메모리를 사용할 수 있다. 알고리즘을 언어와 기계에 독립적인 방식으로 이해하고 연구할 수 있다. 최선, 최악, 평균의 경우 복잡도 RAM 계산 모델을 사용하면 알고리즘이 몇 개의 단계를 실행하는..

3.10 Combining Control and Data in Machine-Level Programs 어떻게 기계 수준의 코드가 프로그램의 제어 측면을 구현하는 지와 어떻게 자료 구조로 구현되는지 구별하여 보았다. 데이터와 제어가 서로 상호작용하는 방법을 알아보자 3.10.1 Understanding Pointers 포인터는 C언어에서 중심적인 특징이다. 자료 구조에 있는 요소에 대한 참조를 생성하는 통합된 방법을 제공한다. 다음은 포인터의 중요한 원칙과 기계 코드로 매핑하는 것이다. - 모든 포인터는 연관된 타입이 있다 : 포인터가 어떤 오브젝트를 가리키는지 가리킨다. - 모든 포인터는 값이 있다 : 값은 지정된 타입의 어떤 오브젝트의 주소이다. NULL 값은 어떠한 곳도 가리키지 않는 것을 뜻한다...

3.7 Procedures 프로시저는 소프트웨어에서 중요한 추상화이다. 프로시저는 인수와 반환 값의 지정된 집합을 가진 기능들을 구현한 코드를 패키징하는 방법을 제공한다. 잘 설계된 소프트웨어는 프로시저를 추상화 메카니즘으로 사용하며, 상세한 구현은 숨기며 어떤 값이 계산되고 프로시저가 프로그램 상태에 어떤 영향 있는 지에 대한 명확한 정의는 제공한다. 프로시저는 프로그래밍 언어에서 많은 모습으로 보여진다. - 함수, 메소드, 서브루틴, 핸들러 등 프로시저에 대한 기계 수준을 제공할 때 많은 속성들이 있다 프로시저 P가 프로시저 Q를 호출하고, Q가 실행되고 P로 다시 반환된다. - Passing Control : PC는 Q의 코드의 시작 주소로 설정되고 Q를 호출한 후에 P의 명령어로 설정한다. - P..

3.4 Accessing Information x86-64 중앙처리장치(CPU)는 64-비트 값을 저장하는 16개의 범용(general-purpose) 레지스터를 포함한다. 이 레지스터들은 정수 데이터와 포인터를 저장한다. 레지스터들의 이름은 %r로 시작하고 뒤에는 다른 이름들을 가지고 있다. 명령어는 16개 레지스터의 낮은 정렬에 있는 바이트에 저장되어 있는 다른 사이즈의 데이터에 대해 연산한다. 바이트 수준 연산은 최하위 비트에 접근한다. (16-비트 연산은 최하위 2바이트, 32비트는 4비트, 64-비트는 모든 레지스터에 접근한다.) 다른 레지스터들은 프로그램에서 다른 역할을 제공한다. 가장 유일한 것은 스택 포인터(stack pointer)로 %rsp이며, 런타임 스택에서 마지막 위치를 가리키는 ..