vss121의 블로그

IA-32 Processor State 32bit compiler general purpose 6개는 범용으로 용도가 정해져 있지 않음. 컴파일러가 그때그때 결정 저장공간 6개를 (레)로 쓸 수 있다 %eax accumulate temporary data %ecx counter %edx data %ebx base %esi source index (배열 idx 관련) %edi destination index (배열 idx 관련) 특별한 목적의 (레) 범용 안 됨 %esp Current stack top stack pointer (스택이 어디까지 사용됐는지) Location of runtime stack %ebp Current stack frame 의 첫번째 위치(base address) base point..

Representing and Manipulating Floating Points 실수 숫자들이 컴퓨터 내에서 어떻게 표현되고 계산되는지 How to represent fractional values with finite number of bits? 정해진 bit 내에서 소수점 숫자를 표현? Fractional Binary Numbers Fractional Binary Numbers (2) • Divide by 2 by shifting right 수

Bit-Level Operations in C Operations &, |, ~, ^ available in C • Apply to any "integral" data type - long, int, short, char, unsigned Q) 나옴 ~0x00 -> 0xFF Logic Operations in C T/F? • &&, ||, ! • View 0 as "False" • Anything nonzero as "True" • Always return 0 or 1 Early termination // 앞부터 비교하기 때문에 적게 비교하는 게 더 좋음 Q) 나옴 char형 !0x41 0x00 !0x00 0x01 !!0x41 0x01 0x69 && 0x55 0x01 0x69 || 0x55 0x01 if..

Memory model Physical memory - DRAM chips can read/write 4, 8, 16 bits - DRAM modules can read/write 64 bits Programmer's view of memory • Conceptually very large array of bytes 굉장히 큰 공간을 연속적으로 할당받고 있다 • Stored-program computers: keeps program codes and data in memory • Running programs share the physical memory • OS handles memory allocation and mangement word size • Nominal size of integer-val..

보호되어 있는 글입니다.

a selection algorithm is an algorithm for finding the kth smallest number in a list or array 여러 개의 데이터가 무작위로 있을 때 전체 데이터에서 매번 가장 작은 (또는 가장 큰) 데이터를 선택하여 데이터 간의 위치를 변경하는 과정을 반복하여 데이터를 오름차순(또는 내림차순)으로 정렬할 때 사용 01 평균 선형 시간 선택 알고리즘 02 최악의 경우에도 선형 시간을 보장하는 선택 알고리즘

01 점화식 Recurrence formula 수열의 항 사이에 성립하는 관계식 점화식은 자기 호출을 사용하는 함수(재귀함수, recursive function)의 복잡도를 구하는데 유용함 factorial (n) { if(n=1) return 1; return n*factorial(n-1) } Divide-and-conquer (분할 정복) 1. 주어진 문제를 작은 단위 (subproblem) 로 쪼갠다. 이 때 subproblem 은 본문제와 같지만 input size (입력 값) 가 작은 문제를 뜻한다. → Divide 2. 1번에서 나눈 subproblem 들을 (recursively 하게) 해결한다. → Conquer 3. 2번에서 푼 subproblem 들의 답을 적절하게 조합 (combine..

Ch01. 알고리즘이란 01. 알고리즘은 문제 해결 과정을 묘사하는 것 : 어떤 작업을 수행하기 위해 입력을 받아 원하는 출력을 만들어내는 과정을 기술한 것 - 명확하고 효율적으로 설계해야 - 입력이 충분히 큰 경우에 대한 분석 : 점근적 분석 02. 알고리즘은 생각하는 방법을 훈련하는 것 03. 알고리즘은 자료구조의 확장 Ch02. 알고리즘 설계와 분석의 기초 01. 몇 가지 기초 사항들 1 알고리즘 분석의 필요성 시간 분석(최악의 경우, 평균적인 경우)을 하면 알고리즘이 어느 정도의 입력에서 어느 정도의 시간이 필요한지 미리 짐작할 수 있다 2 알고리즘의 수행 시간 입력의 크기에 대해 시간이 어떤 비율로 소요되는지로 표현한다 Ex Ex factorial(n) -> n에 비례 3 재귀(자기호출)와 귀납..

01 레코드, 키의 정의 및 검색 트리 - 이진 검색 트리 : 자료를 찾는 색인 역할하는 자료구조 중 하나 ● 레코드 : 개체에 대해 수집된 모든 정보를 포함하고 있는 저장 단위 - 사람의 레코드 : 주민번호, 이름, 집주소, 집 전화번호 ... - 검색 트리는 개체의 레코드 저장, 검색 (대표할 수 있는 필드만으로 ) - 필드 : 레코드에서 각각의 정보를 나타내는 부분 ● 검색키, 키 : 다른 레코드와 중복되지 않도록 각 레코드를 대표할 수 있는 필드 - 키는 필드 하나 or 필드 복수 개 ● 검색트리 - 한 노드에서 최대 몇 개의 자식 노드로 분기? 1 이진 검색 트리 : 최대 2개, 2 다진 검색 트리 - 저장되는 장소? 1 내부 검색 트리 : 메인 메모리 내에, 메인 메모리에 모든 키를 수용할 수..

Moving data (데이터를 옮기기) : CPU와 Mem 사이, CPU-CPU movl source, dest ~복사 ● Move 4B("long") word - intel 32b 기준 그냥 mov는 16b Operand types 1) Immediate - constant integer data 상수값(C에서는 숫자값, Intel 어셈블리어는 $로 시작) - 1,2,4B로 2) Register - 8개의 범용 R중 하나 - %esp, %ebp는 스택을 나타내기 위해 특별한 용도로 사용 3) Memory - 4 consecutive bytes of memory - address movl operand combinations - Cannot do memory-memory transfers with si..