Fibonacci NumberF(0) = 0, F(1) = 1, F(n) = F(n-1) + F(n-2) RecursionMemoizationDynamic ProgrammingBy Recursionint F(int n) { if(n  F(10)에서 타고 들어가게 되면, 같은 것이 호출되는 경우가 굉장히 많아진다. 노드들이 굉장히 많아지게 되고 엄청나게 느려진다.  By Memoizationint FF[1000]int init(){ for (i = 2; i 기록을 해둔 얘들은 바로 리턴이 되기 때문에, 간단한 재귀보다 더 빠르게 계산됨따라서 O(n)에 계산이 가능하다 모든 재귀가 memoization이 되는 것은 아니다. 결과 값만 의미가 있지, 내부 구조가 의미가 있는 경우에는 불가능하다. By Dyna..

Maximum SubarrayFind the consective subarray with maximum sum 합이 최대가 되는 연속되는 서브 배열을 찾아라O(\(N^3\)) is easy : sub array의 갯수가 n*(n+1) / 2개가 존재한다.O(\(N^2\)) is kind of easy : 연속인 subarray는 시작과 끝 점으로 존재함. 즉 \(_{n+1}\)C\(_2\)개의 subarray가 존재한다.O(N)?Do we allow subarray with zero elements?만약 전부 양수 : 배열 전체 (자기 자신도 부분 집합이라고 생각한다) O(\(N^2\))에서 보면, 이전에 구해둔 배열의 합에서 다음 것만 더하면 됨 => i~j 까지 더하는 과정이 O(1)로 줄어들게 됨 ..

Matrix MultiplicationMultiply 2 N by N MatricesTakes O(\(N^3\)) Time using Normal Method -> Let's consider only number multiplicationApply Divide and Conquer지금 A, B, C, D 이것들이 전부 N/2 by N/2 Matrix 들이다.이러한 행렬들을 위의 공식으로 계산하면 결국 N by N 행렬을 곱한 것과 같다.결국 이는 O(N^3)이다. Strassen's Algorithm곱하기 갯수에 집중해서 생각해보자곱하기가 7번뿐이다. 대신 덧셈과 뺄셈이 늘어났다곱셈이 줄어들기 때문에, O(2^log7N)이 된다.  Karatsuba Algorithm n x n 자리수를 곱하는 것O(n^..

가장 먼 점을 찾는 문제직관적으로 생각했을 때도, 가장 먼 점은 무조건 convex hull 위에 있어야한다. Rotating Calipers캘리퍼를 움직여서 가장 먼 것을 구하는 것이다. 왼쪽을 아무데서 구하고, 각도를 이용하여 "캘리퍼가 닿는 각도"를 확인한다. (180도가 넘는 각도)캘리퍼를 한바퀴 돌리면서 확인한다.   가장 먼 점의 쌍을 구하는 유일한 방법이다. Convex Hull을 구하면 풀 수 있으므로 O(NlogN)에 해결된다.

MItigation : 보호 기법window는 winchecksec으로, linux는 checksec(pwndbg)로 확인한다.  더보기[ winchecksec JSON parsing code ]  JSON 파일이 보기 힘들어서 만든 코드이다 winchecksec와 같은 경로에 두고 원하는 파일 경로를 넣어주면 됨import osimport sysimport jsonimport subprocessdef get_security_info(file_path): """winchecksec.exe의 JSON 출력에서 보안 정보를 반환합니다.""" result = subprocess.run(['winchecksec.exe', '--json', file_path], capture_output=True, t..

문제 : https://bluehens.ctfd.io/challenges#Training%20Problem:%20Intro%20to%20PWN-161 BlueHens CTF 2024BlueHens CTF 2024 has ended ×bluehens.ctfd.io약간의 리버싱이 섞인 기초 포너블 문제 Mitigation ASLR 없음NX bit 있음카나리 있음 Code Analysisvuln함수에 무조건 취약점이 터진다.이걸로 return address를 조작해서 익스가 가능할 것으로 보인다. My Exploit Scenario 스택에 쉘코드 넣고 return address를 v1 주소로 바꾸어서 익스하기-> NX bit가 설정되어 있어서 스택에 실행 권한이 없으므로 불가능GOT overwrite : ..

Smallest Convex Polygon containing all the points모든 점을 포함하는 가장 작은 볼록 다각형작다라는 것은 면적도 가장 작고, 변의 길이와 변의 개수가 모두 작은 것을 의미한다.-> 직관적으로 이해하려면, 밖에 고무줄을 두른다고 생각했을 때 딱 들어가는 것을 convex hull 이라고 할수 있다.  결국은 이 문제가 NlogN에 풀린다. Q) NlogN보다 빠를 수가 없다. A) 점들이 원 모양으로 좌표에 있다고 하면, 이걸 이은것이 convex hull이다. 그러니, 무작위 좌표값을 각도로 sorting을 하고 이어야한다. 따라서 sorting 이 NlogN보다 빠를 수 없기 때문에 최소 NlogN이 걸린다.  CCW (Counter-Clock-Wise) 좌회전 아..

Closest pair Computational Geometry직관과 심하게 충돌하는 경우 많음주어진 점들 중에서 가장 가까우 쌍을 찾기(2차원)Usually Input is given by Coordinates좌표 형태로 입력이 들어온다. (a,b), (c,d)가 주어진다면 -> \(\sqrt{(a-c)^2 + (b-d)^2}\) 을 모든 쌍에 대해서 하면 \(n^2\)개가 생기고 이 중에 제일 작은거 찾으면 됨sqrt()라는 함수로 루트를 계산할 수 있지만, 무리수이기 때문에 정확한 계산이 불가능하다.  1 - Dimensional Versionsorting 후, 가장 옆에것과의 거리를 비교하여 가장 짧은 것을 고르면 됨Divide and ConquerFirst, Sort by x coordinate..

O notation에서 상수가 차이가 나기 때문에, 이 안에서 어떤게 더 좋을지 판단할 수 있다. 그런 류의 아주 복잡한 문제를 Quick Sort가 만들어낸다.  앞으로 이야기 하는 이야기에서는 Quick Sort가 그렇게 좋지 못하다는 것을 알게 될 것임. *Worst일 때는 merge sort가 더 좋다. 우리는 이걸 O(NlogN)으로 만들고 싶다.실제로는 merge보다 quick이 빠르다. 따라서 worst case만 고치면 O(NlogN)이 되면서 merge보다 빠르게 될 것이다. In Quick Sort : can we Find the Best Pivot?if we can do it in O(N), Quick Sort will run in Worst Case O(NlogN) time따라서, ..

int sort (int a[], int n) { // if n p) j--; if(i 배열을 추가로 할당하지 않는다.0, 1, 2 ... j, j+1 ... n-1까지의 인덱스를 가진 배열로 가지고 있다.0(a)부터, j-1까지 재귀호출을 한다. j를 제외하고a+j+1부터, n-1까지 재귀호출을 한다 .재귀호출을 끝내면 바로 끝난다. *Merge는 재귀 호출 후 다시 merge 해야함 재귀호출을 하고 끝나게끔 미리 setting을 해둔것이다. a[j]가 꼭 중간이 아닐 수도 있다.a[j] 전에 있는 것들은 모두 a[j]보다 작고, 후에 있는 것들은 모두 a[j]보다 크다. 그렇게 재귀를 돌리기 전까지 setup을 한 것이다. (while 문에서) p = a[0] pirot (아무거나..