._.

DFS Tree전진(재귀 호출)을 한 edge로 만듦DFS Tree is the Result of DFSUsually analyze DFS Tree to get information DFS Tree에 있는 edge를 Tree edge라고 부른다그리고 Tree edge에 포함되지 않은 것들을 Back Edges라고 한다 Edges of input Graph becomes Tree or Back edges of DFS TreeBack edges는 전부 자손과 조상을 연결하는 것 밖에 없다그 이유는, 조상이 아닌 다른 것과 연결되어 있었다면, 아래로 호출했을 것이다. 파란색 선을 back edge라고 가정한다면이미 노드가 연결되어있다는 것이다.그렇가면, 만약 맨 아래 leaf가 DFS를 통해 저 노드를 호출할..

TraversalVisit Nodes of a Graph in Some order : 그래프의 노드들을 특정한 순서로 지나간다.May go through a node Several TimesWhile doing some CalculationUsually After the Traversal Some Data Structure Results : Useful Information Extracted 결과적으로 어떤 "정보"가 나오게 된다 Any-Order traversalStart at a Node s (put s into BOX)While BOX is not Emptytake one node from BOXIf Node not Marked -> Mark Node -> Do Computation on Node ..

금화 모으기 만약 연속으로 같은 방향으로 가지 못한다는 규칙이 있다고 생각하자해당 칸에 왔을 때, 이전 방향을 기억하고 있어야한다결국, 중간 부분에서 왼쪽에서 오는 것인지 아래에서 오는 두 가지 모두 알고 있어야한다 결국 과거 일을 덜 기억해야할 수록 더 쉽다 로봇이 (i,j)에 도착할 때까지 모을 수 있는 최대 금화 개수 Pseudo Polynomial 설명 pseudo polynomial 이라는 알고리즘들 중 하나이다.어떤 입력이 n일 때 O($n^2$)이 걸린다.n개의 숫자가 얼마나 큰지 작은지에 상관 없이 우리는 항상 n이라고 생각한다. 작은 값들과 큰 값들은 연산에 차이를 보인다사실은 비트 수에 따라서 비교를 해야하기 때문에 엄청나게 큰 숫자는 작은 숫자와 연산에 차이가 있다 즉, 비교하는데..

다양한 Alignment 문제들을 의미한다. edit distance보다 좀 더 확장된 의미이다. Global, Local, Semi-local Alignment ProblemsGlobal Alignment는 두 개의 문자열을 gap symbol("-")을 포함하도록 확장하여 같은 길이의 문자열로 만드는 문제이다edit distance의 경우, gap 부분에 insert한다고 생각하면 된다대응되는 문자들의 쌍에 대하여 score가 입력으로 주어진ㄴ다대응되는 문자들의 쌍들의 score 합의 최대치가 되는 alignment를 구하는 것이 목적이다alignment 문제들은 대부분 동적 계획법으로 해결된다Global Alignment두 개의 스트링 acvcdb와 cadbd가 있을 때 두 스트링은 얼마나 비슷한가..

근사 문자열 매칭 (approximate string matching)비슷한 문자열 비교주어진 문자열과 비슷한 문자열을 검색 ex) 검색 엔진 유사어 추천 등..비슷한 것이라는 것은 무엇인가?이때 사용하는 것이 거리함수이다. 거리 함수해밍거리 (Hamming distance) : 단순 문자열 매칭으로 다른 자리의 갯수 - 글자가 끼어들거나 빠지거나 할 수 없는 경우 사용할 수 있음 편집거리 (edit distance) : 첫번째 문자열을 두번째 문자열로 바꾸는데 얼마나 많은 editing 작업을 해야하는가? 가중편집거리 (weighted edit distance)  편집 거리한 문자열을 다른 문자열로 변경하기 위해 필요한 편집 연산 (edit operation)들의 최소 수 편집 연산삽입 (Inserti..

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..