해킹왕 양선규

동적 메모리 할당- heap 영역에서 이루어진다.- heap은 위쪽으로(높은 주소 방향으로) 성장한다.- heap의 top(높은 주소 쪽)을 가리키는 변수는 “brk”이며 break로 발음한다.- 할당기는 힙을 다양한 크기의 블록들의 집합으로 관리한다.- 각 블록은 할당된 블록과, 가용된 가상메모리의 연속적인 묶음이다. 명시적 할당기 - malloc- malloc을 호출해서 메모리 블록을 할당한다.- free를 호출해서 메모리 블록을 반환한다. 묵시적 할당기 - garbage collector- 할당된 블록이 언제 반환되어야 하는지 할당기가 알고 있다- 사용되지 않는 블록을 자동으로 반환하는 작업을 “garbage collection" 이라고 부른다.- List, ML, Java 같은 언어들은 garba..

페이징과 세그먼테이션세그먼테이션(Segmentation)- 메모리를 “세그먼트”단위로 나누는 방법- 각 세그먼트는 시작 길이와 주소를 가지며, 다른 유형의 데이터(코드, 데이터, 스택 등)을 위해 사용됨- 메모리를 유연하게 관리할 수 있게 하며, 프로그램의 논리적 구조를 반영함 페이징(Paging)- 메모리를 동일한 크기의 블록인 “페이지”로 나누는 방법- 각 페이지는 가상 메모리 주소와 매핑되고, 페이지 테이블을 통해 물리적 메모리 주소로 변환됨- 메모리 관리를 단순화시키고 낭비를 줄이며, 프로그램 간 메모리 충돌을 방지함 세그먼테이션 : 장점- 메모리를 논리적 단위로 나눠, 프로그램 구조를 반영한다.- 세그먼트별 보호/공유가 용이하다.세그먼테이션 : 단점- 외부 단편화 발생 가능성- 메모리 관리가 복..

RB Tree(Red Black Tree) - 이진 탐색 트리(BST) 기반의 self balanced tree - 삽입/삭제는 BST와 동일하지만, 삽입/삭제 후 RB Tree의 5가지 속성을 만족하기 위한 재조정 작업이 필요하다. - 스스로 좌/우 서브트리의 균형을 맞춘다 - 서브트리 간 height 차이는 최대 2이다. RB Tree의 속성 5가지 1. 모든 노드는 red 혹은 black 2. 루트 노드는 black 3. 모든 nil 노드는 black nil 노드 - 존재하지 않음을 의미하는 노드 - 자녀가 없을 때 자녀를 nil 노드로 표기함 - nil노드는 값이 있는 노드와 동등하게 취급 - RB트리에서 leaf노드는 nil노드이다. 4. red의 자녀는 모두 black이다 = red는 연속적으..

이진 탐색 트리(Binary Search Tree, BST) - 왼쪽 서브트리는 부모 노드보다 작고 오른쪽 서브트리는 부모 노드보다 큰 이진 트리 - BST의 최소값은 “트리의 가장 왼쪽”에 존재한다 - BST의 최대값은 “트리의 가장 오른쪽”에 존재한다 이진 탐색 트리의 삽입 - 아무것도 없는 트리라면 그냥 삽입한다. - 삽입할 노드를 루트 노드부터 하나씩 비교한다. 루트 노드보다 작다면 왼쪽, 크다면 오른쪽으로 간다. 빈 자리를 찾을 때 까지 반복한다. - 같은 값을 가지는 노드는 없다. 이진 탐색 트리의 삭제/검색 - 삭제를 하려면 검색부터 해야 한다. - 찾을 노드를 기준으로, 루트 노드부터 하나씩 비교한다. 삽입할 때처럼 루트 노드보다 작다면 왼쪽, 크다면 오른쪽으로 간다. 값이 같다면 해당 노..

선언(declaration)과 정의(definition) 선언(declaration) - 컴파일러가 참조할 식별자(identifier)의 이름을 알린다. - 식별자란 변수의 타입, 함수의 인자목록을 뜻하며 이름은 변수, 함수, 클래스의 이름 등을 뜻한다. - 선언은 메모리 영역 상에 올리지 않기 때문에 중복되어도 문제가 되지 않는다. extern int a; // 전역변수 선언 int add(int a, int b); // 함수 선언 class ClassId; // 클래스의 선언 정의(definition) - 식별자와 이름으로부터 코드를 생성한 것 - 정의는 고유해야 한다. 같은 식별자와 이름의 정의가 2개 이상이면 컴파일 에러 발생 int add(int a, int b) { // 함수의 정의 (함수 본..

x86-64에서 프로시저에서 프로시저로의 데이터 전달 - 레지스터를 통해서 일어난다. ( 인자들이 %rdi, %rsi등으로 전달되고 %rax로써 리턴되는 형태들을 의미 ) - 프로시저 P가 프로시저 Q를 호출할 때, P는 자신이 전달할 인자들을 레지스터에 복사해야 한다. - 전달할 인자들이 레지스터에 복사되거나 스택에 할당된 후에!!!!!! Q를 호출하게 된다. - Q가 일을 끝내고 P로 리턴할 때, P는 Q가 리턴한 값을 %rax에서 접근할 수 있다. x86-64에서 프로시저에서 프로시저로의 데이터 전달2 - x86-64에서는 “최대 여섯 개의 정수형 인자(정수와 포인터)”가 레지스터로 전달될 수 있다. - 레지스터는 “전달되는 데이터 형의 길이”에 따라서, 정해진 순서대로 이용된다. - “프로시저의 ..

프로시저(procedure) - 제공되는 인수(parameter)에 따라서 특정 작업을 수행하는 서브루틴 - 프로그래밍에서의 함수(function)과 같다. 또는 메소드, 서브루틴, 핸들러 등.. 모두 프로시저라고 한다. - 소프트웨어에서의 주요 추상화이다. 내부 동작을 숨기고, 프로시저를 통해 사용자가 쉽게 기능을 사용할 수 있게 한다. 프로시저가 실행될 때 처리되어야 하는 많은 과정들 프로시저 P가 프로시저 Q를 호출하고, Q가 실행된 후에 P로 리턴한다고 가정 - 제어권 전달 : 프로그램 카운터는 진입할 때 Q 코드의 시작주소로 설정된다. 리턴할 때는 P에서 Q를 호출하는 인스트럭션 다음의 인스트럭션으로 설정되어야 한다. - 데이터 전달 : P는 하나 이상의 매개변수를 Q에 제공할 수 있어야 하고,..

스택(stack) - 프로시저 호출 시 “지역 변수와 매개변수”를 저장하기 위한 메모리 공간(지역변수 = 로컬변수) - 후입선출(LIFO, Last In First Out) 구조 스택의 용도 - 함수의 로컬 변수 저장 : 각 함수 호출 시, 그 함수의 로컬 변수들이 스택에 저장된다. - 함수의 제어 흐름 관리 : 함수가 다른 함수를 호출할 때, 반환 주소와 이전 함수의 스택 프레임 정보가 스택에 저장된다. - 장점 : 동적으로 메모리 할당/해제 가능, 구현이 간단함, 메모리 관리 overhead가 낮음 스택의 특징 - 스택에서 데이터가 삽입되고 빠져나가는 쪽을 top 이라고 한다. 반대쪽은 bottom이다. - %rsp 레지스터는 스택 포인터이다. 스택 포인터는 항상 스택의 top 주소를 가리키고 있다...

플로이드 워셜(Floyd-Warshall) 알고리즘 - 다익스트라가 특정 정점과 특정 정점까지의 최단 경로를 구하는 알고리즘 이라면, 플로이드 워셜은 모든 정점에서 다른 모든 정점까지의 최단 경로를 모두 찾는 탐색 알고리즘 - 다익스트라는 그리디, 플로이드 워셜은 DP - 노드의 개수가 N개일 때 알고리즘상으로 N번의 단계를 수행하며, 단계마다 O(N2)의 연산을 통해 ‘현재 노드를 거쳐 가는 모든 경로’를 고려한다. 따라서 총 시간 복잡도는 O(N3)이다. 플로이드 워셜(Floyd-Warshall) 알고리즘의 과정 1. 인접 행렬 방식으로 출발노드, 도착노드, 비용을 입력한다. 갈 수 없다면 INF로 설정한다. 2. k(거쳐갈 노드), a(출발 노드), b(도착 노드) 순서로 3중 for문을 만든다. ..

Byte : 8bit Word : 16bit Double Word : 32bit Quad Word : 64bit CPU의 16개 범용 레지스터 - 각 범용 레지스터의 크기는 64bit이다. - 16개의 레지스터에 있는, 여러 크기의 하위 바이트 데이터에 대해 연산이 가능하다. - %rsp : 스택 포인터이며, 런타임 “스택의 끝 부분(Top)”을 가리킨다. 레지스터의 역사 8086 - 8개의 16비트 레지스터 - %ax ~ %sp IA32 - 32비트로 확장 - %eax ~ %esp x86-64 - 기존의 8개의 레지스터가 64비트로 확장 (%rax ~ %rsp) - 8개의 새로운 레지스터 추가 (%r8 ~ %r15) 레지스터는 1, 2, 4, 8 바이트 단위로 사용할 수 있다. 8바이트를 사용하는 경우..