Definition of Linked ListConsists of NodesNode: unit of storage (item)Nodes are linked with pointers(link) - 포인터가 옆에 붙어있다 (what does that mean?)메모리 아무 곳에나 흩어져있음논리적으로는 1차원pointer to next node : 단순히 주소가 저장되어 있는 것Q. 화살표는 코드에서 무슨 뜻일까? A. 다음 노드의 주소가 값으로 적혀있다화살표를 따라가면 다음 노드가 어디에 있는지 알 수 있다 프로그램의 head는 변수로 가지고 있어야한다 - head는 노드가 아니다Code of nodeclass Node { int a; Node *n;};Q. node 옆에 *이 없다면 어떻게 될까A. 노드가..

미로찾기 : 알고리즘이 달라도 성능 차이가 나지 않음 Definition of Equivalence Relation (Equivalence Relation의 정의)Definition of Relation의미가 있는 관계 순전히 집합으로만 정의된 관계 ex) Given a Set A a Relation on A is any subset of A \(\times\) AA = {1, 2, 3, 4} R = {(1,3) (3,4),(1,1),(2,2)} (A\(\times\)A인 수많은 집합의 부분집합)We write 1R3 to mean (1,3) ∈ R extreme example)  관계가 성립한다는 것을 Relation 2  Equivalence Relation (동치 관계인 Relation)같다는 관계..

StackPush(Insert) / Pop(Delete)만 제공함Last in, First outQ. Stack을 가지고 sorting 할 수 있는가? A. 안되는 경우 : 3, 8, 2와 같이 중간수, 큰 수, 작은 수의 순서가 전체에 한번이라도 등장하면 sorting 할 수 없음 Q. 함수 호출 시 스택A. a함수가 b함수를 , b함수가 c함수를 실행시킨다면, c, b, a 순으로 리턴됨 스택의 구조와 같다.성능 Push : O(1)Pop : O(1)구현Stack Pointer : 빈 자리를 가리키는 ( 개인 취향 ) 배열 인덱스 (보통 빈 자리를 가리킴) - 배열의 크기(가용)을 나타내기도 함 //Stack 구현int Stack[100]; //Stackint SP; //stack pointerint..

Problem definition (문제 정의)text : simple string of characters (문자열을 찾을 텍스트)pattern : simple string of characters (찾을 텍스트 - 패턴)to do : find where in the text the patter occurs 패턴이 나타나는 텍스트 찾기AlgorithmAlgorithm시간공간naive \(O(mn)\) \(O(n)\) or \(O(1)\)DFA (Deterministic Finite Automaton) \(O(\sum m + n)\) - 테이블 제작 + 텍스트 읽기 \(O(\sum m\) - 테이블 메모리KMP (Knuth Morris Pratt) \(O(m+n)\) \(O(m)\)* n : 텍스트의 길..

Unpacked unsorted빈 자리들이 흩어져 있음 - item 별로 사용중인지 아닌지 표시가 필요함free list head로 빈 칸들의 리스트를 만든다빈 칸인 인덱스를 계속 따라가면 다른 빈 칸인 인덱스를 알 수 있음실제 free block의 번호 > 다음 free block 의 번호search : O(n) - binary searchinsert : [search O(n)] O(n) (free list head 추가시 O(1))delete : [search O(n)] O(1)Unpacked sorted지울 때 값을 지우는 것이 아닌 다른 배열에 존재 하는지 하지 않는지 마킹함지우지 않은 칸, 지운 칸 모두 유지해서 sorting order가 맞아야함#include int a[100] = {0};i..

Packed sorted정렬이 되어있다는 것을 가정하므로 search 시 binary search를 사용할 수 있음item의 개수를 표시하는 변수가 필요함 (packed의 특징)insert : search를 통해 계속 좁혀오다가, 두 개의 리턴 값을 보낼 수 있음 (그 사이 혹은 그 곳에 insert)#include int a[100] = {0};int size = 0;int r, l, m;int arr_search(int a[], int n, int x){ int s, e, m; s = 0; e = n-1; while(s x) e = m-1; else s = m+1; } l = e; r = s; return -1;}void arr_insert(i..

Array (배열): 연속된 주소, 같은 타입array는 에를 들어, 8개의 자리가 있어도 꽉 차있지 않을 수도 있음 > 빈 칸이 있을 수도 있다는 것 how to store items in an array? (배열에 데이터를 어떻게 저장하는가)packed vs unpacked빈 자리를 한 쪽으로 모으는지 여부에 따른 것packed : 사용하는 칸을 한 쪽으로 뭉쳐놓기unpacked : 사용하지 않는 칸과 사용하는 칸이 섞여 산발적으로 데이터가 흩어져있음sorted vs unsorted item들이 정렬된 상태를 유지하는지의 여부에 따른 것같은 값들이 없다는 전제 하에 이루어짐sorted : 정렬된 상태unsorted : 정렬되지 않은 상태 Packed Unsorted index0123456value30..

Merge Sort : 두 개의 sorting된 배열을 비교하여 더 작은것부터 정렬하여 전체 sortingint sort(int a[], int n){ int h; int b[n]; h = n/2; //copy a[] to b[] sort(b,h); // 왼쪽 sorting sort(b+h, n-h); //오른쪽 sorting // merge two halves in b to a return ;} Proof of invariantsorting의 정의 (invariant)sorting이 끝난 후 배열에 저장된 값들을 b[0], b[1] …b[n-1]라고 부르자 (같은 배열이지만 구별하기 위해)조건 1 : {a[0], a[1], … a[n-1]} = {b[0], b[1] … b[n]} 집합으로 같음조건 2 ..

문제 : https://dreamhack.io/wargame/challenges/3 basic_exploitation_001Description 이 문제는 서버에서 작동하고 있는 서비스(basic_exploitation_001)의 바이너리와 소스 코드가 주어집니다. 프로그램의 취약점을 찾고 익스플로잇해 "flag" 파일을 읽으세요. "flag" 파일의 내용dreamhack.io Environment32비트 바이너리 파일리틀 엔디안stack canary 없음 - buffer overflow 공격 가능NX bit 사용no pie - 주소값 고정Code Analysis#include #include #include #include void alarm_handler() { puts("TIME OUT"); ..

mac에서 x86_64등으로 빌드된 프로그램은 실행되지 않는다. zsh: exec format error mac이라는 에러와 함께 m기반 cpu로는 실행되지 않는다. exec 파일은 intel cpu 기반으로 빌드한 것이기 때문에 mac cpu를 기반으로 하는 가상환경에서는 불가능하다. 두 가지 방법이 있는데, 첫번째는 가상머신을 가상화하지 않고 애뮬레이터로 돌리는 것이고 aws를 사용하는 것이다. 방법 1 : UTM 사용하기1. UTM의 +버튼을 눌러 가상환경을 만들어준다2. Emulate/linux 선택Virtualize는 가상화로 현재 내 cpu를 기반으로 가상머신을 만들어준다. 즉, Virtualize로 만들어진 가상환경은 여전히 arm64기반이므로 exec파일을 실행할 수 없다.따라서 아예 Em..