해킹왕 양선규

프로시저(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바이트를 사용하는 경우..

DP(Dynamic Programming, 동적 계획법) - 하나의 큰 문제를 여러 개의 작은 문제로 나누어서 그 결과를 이용해, 다시 큰 문제를 해결할 때 사용한다. - DP는 특정 알고리즘이 아니라 하나의 방법론이므로 다양한 문제해결에 쓰인다. - “큰 문제를 작은 문제로 쪼개서 그 답을 저장해두고, 재활용” - DP라는 이름은 그냥 멋있어 보여서 지은 이름이다. DP를 쓰는 이유 - 일반적인 재귀방식도 DP와 유사하지만, 일반적인 재귀를 단순히 사용 시 “동일한 작은 문제가 반복”되어, 비효율적인 계산이 될 수 있다. ex) 피보나치 수열. 한번 한 계산을 또 하고 또 하고 반복한다. --->>> DP 방식으로 작은 문제의 결과를 저장해두고 “재사용”하면 매우 효율적으로 해결할 수 있다. --->>..

캐시 메모리를 사용하면 컴퓨터의 성능이 향상되는 이유 지역성(Locality) - 프로그램이 메모리에 접근할 때, "특정 부분을 집중적으로 사용"하는 경향 시간적 지역성(Temporal Locality) - 한 번 접근된 데이터는 가까운 미래에 다시 접근될 가능성이 높다. - ex) 루프 내에서 반복적으로 사용되는 변수 공간적 지역성(Spatial Locality) - 메모리의 특정 주소에 접근한 후, 그 주변 주소에 있는 데이터에 접근될 가능성이 높다 - ex) 배열, 연속적인 메모리 블록 등 캐시 메모리는 지역성 원리를 활용하여, 자주 사용되거나 연속적으로 사용될 가능성이 높은 데이터를 미리 캐시에 저장한다. 이로 인해 CPU는 필요한 데이터를 캐시에서 빠르게 찾을 수 있다. 메모리 계층구조 L0 :..

다익스트라(dijkstra) 알고리즘(최단 경로 알고리즘) - 그래프에서 한 정점까지의 최단 경로를 구하는 알고리즘 - 이 과정에서 도착 정점 뿐만 아니라, 모든 다른 정점까지 최단 경로로 방문한다. - 최단 경로를 구하는 과정에서, “각 노드에 대한 현재까지의 최단 거리” 정보를 항상 저장하고 갱신한다. - 매번 가장 비용이 적은 노드를 선택하는 것을 반복하기 때문에 그리디 알고리즘으로 분류되기도 한다. - 방향/무방향 그래프인지는 상관없다. 다익스트라 알고리즘 동작과정 - 우선순위 큐 사용을 위해 파이썬 heapq를 사용한다. 최소 힙으로 동작하기 때문에 항상 최단 거리를 pop하게 된다. 1. 최단 거리 테이블을 전부 INF(무한)으로 초기화한다. ( 일반적으로는 INF = int(1e9) 이다.)..

분할 정복(Divide and Conquer) - 여러 알고리즘의 기본이 되는 해결 방법, 엄청나게 크고 방대한 문제를 작은 단위로 쪼개어, 결과적으로 큰 문제를 해결하는 방법 - 퀵 정렬, 병합 정렬, 이분 탐색 등이 대표적 예시이다. - Divide를 제대로 나누면 Conquer은 자동으로 쉬워지기 때문에 Divide를 잘 설계하는 것이 매우 중요하다. - 분할 정복에서는 재귀 알고리즘이 많이 사용되는데, 이 부분에서 분할 정복의 효율을 깎아내릴 수 있다. 분할 정복의 설계 1. Divide(분할) - 원래의 문제를 분할하여, 비슷한 유형의 하위 문제로 더 이상 분할이 불가능할 때 까지 나눈다. 2. Conquer(정복) - 각 하위 문제를 재귀적으로 해결한다. 더 이상 나눌 수 없는 단위일 때의 탈..

해시 테이블(Hash Table)- 먼저 키(key)와 값(value)으로 구성된 데이터가 필요하다.- 여기서 “key”를 해시값으로 만들어, 해당 해시값을 “인덱스”로써 활용하여 테이블에 저장한다. 여기서 해시값은 정수 형태가 된다.- 데이터(value)를 해시하여 인덱스로 쓰는 거 아니냐는 사람들이 있는데, 이럴 경우 value가 같으면 인덱스가 중복될 수 있다. 해시함수는 같은 입력에 대해서 항상 같은 해시값을 만들기 때문이다.- 어떤 값을 찾든 O(1)의 복잡도를 가진다. 고유값으로 접근하면 되기 때문.- 해시 테이블에서 만들어진 원소를 버킷(Bucket)이라고 한다. 해시 테이블의 장/단점- 장점 : 자료의 검색, 읽기, 저장 속도가 빠르다. 즉 데이터 조회가 빠르다.- 장점 : 자료가 중복되는..