![]()
Traversal Visit Nodes of a Graph in SOME orderMay go through a node several timeWhile doing calculation Any order traversalStart at a node s (put s into BOX)while BOX is not empty:Take one node from BOXIf node not Marked:Mark nodeDo computation on nodeput Every Adjacent node This solves ReachabilitySolution: start at s, check if t was visited with any order traversal Proof (귀류법) 위에서 제시한 any orde..
최대 공백 정사각형 문제 정의: 주어진 N x N크기의 흑백 이미지에서 검은 점을 포함하지 않는 가장 큰 빈 정사각형을 찾는 문제 DP Idea LES(x,y)를 (x,y)를 우측하단 꼭짓점으로 하는 최대 정사각형의 크기라고 하자LES(x,y) = 0 : (x,y)가 비어있지 않은 경우LES(x,y) = 1 : 첫번째 행 또는 열의 (x,y)가 비어있는 경우, baseLES(x,y) = min(LES(x-1,y-1), LES(x,y-1), LES(x-1,y)) + 1 : 나머지 픽셀 (x,y)가 비어있는 경우, step, 하나라도 작으면 작은 사이즈의 정사각형을 가지고 계산해야함 최대 공백 직사각형 문제 정의: 주어진 N x N크기의 흑백 이미지에서 검은 점을 포함하지 않는 가장 큰 빈 직사각형을 찾는 ..
근사 문자열 매칭과 거리 함수 근사 문자열 매칭 (approximate string matching) 은 비슷한 문자열을 매칭하는 것을 말합니다. 거리 함수는 어떤 문자열과 문자열 사이의 거리를 구하는 함수로 다음 3가지의 예가 있습니다.해밍거리편집거리가중 편집거리 편집 거리 한 문자열을 다른 문자열로 변경하기 위해 필요한 편집연산들의 최소 수 연산의 종류는 [삽입, 삭제, 교체, 유지]가 있습니다. DP Idea D(i,j)는 두 문자열 S1, S2에 대한 편집거리를 나타낸다고 할때, 제일 오른쪽 문자부터 비교를 하면서 연산들 중 값이 가장 작아지는 것을 고르면 됩니다. D(i,j)값은 아래 4가지 값들 중 가장 작은 값입니다:D(i,j-1) + 1 → 삽입D(i-1,j) + 1 → 삭제D(i-1,j-..
Maximum sub-array Find the consecutive sub-array with maximum sum 이때 subarray란 전체 배열안에 연속된 부분 배열을 의미합니다. 즉, 전체 배열에서 부분 배열의 가장 큰 합을 구하는 문제입니다. 만약 배열에 음수가 없다면, 최대 부분 배열의 합은 전체 배열의 합이 될 것입니다.또한 배열에 양수가 없다면, 가장 큰 음수 하나이거나 조건에 따라서 빈 배열이 가장 큰 부분 배열의 합이 될 것입니다. 부분 배열의 길이가 0인 것을 허용하지 않는다면, 가장 큰 음수 하나가 가장 큰 부분 배열의 합이 될 것이고,부분 배열의 길이가 0인 것을 허용한다면, 빈 배열즉, 0이 가장 큰 부분 배열의 합이 될 것입니다. 이하에 적을 알고리즘은 부분 배열의 길이가 0..
![]()
Fibonacci Number 피보나치 수열은 다음과 같은 방식으로 전개되는 수열입니다.long fibonacci(int n){ return (n 위와 같이 피보나치 수열의 값을 재귀로 구하게 된다면 시간이 너무 오래걸린다는 문제가 있습니다.재귀적으로 짠 fibonacci()의 경우 아래와 같은 방식으로 호출이 일어납니다. 아래의 예시는 fibonacci(5)를 구하는 case입니다: 함수 호출을 총 15번하는 것을 볼 수 있습니다. 구하는 n의 값이 작은 경우 그리 크게 상관은 없지만, n이 커지게 된다면 2가지 문제점이 발생할 수 있습니다.재귀호출이 지나치게 많아져서 memory가 부족해 질 수 있다 → stack overflow느리다 → O(2^n)의 시간복잡도를 갖습니다 위 방식의 문제점은..
![]()
Matrix Multiplication Multiply 2 N by N MatricesTakes O(N^3) Time using Normal MethodCan we do FASTER? Apply Divide and Conquer In the above method, we do 8 multiplications for matrices of size N/2 x N/2 and 4 additions. Addition of two matrices takes O(N^2) time. So the time complexity can be written asT(N) = 8T(N/2) + O(N2) From Master's Theorem, time complexity of above method is O(N3)whic..
![]()
Convex hull Find smallest Convex Polygon containing all the pointsConvex hull은 2차원 좌표 평면에 존재하는 여러 점들 중 일부를 이용하여 만들 수 있는 모든 점을 포함하는 볼록 다각형입니다. 그 볼록 다각형 중, 면적이 최소인 다각형을 찾으면 됩니다. 이때, 한 직선 위에 점이 3개 이상 있지 않다고 가정하겠습니다. CCW (Counter-Clock-Wise) 벡터의 외적을 통해서 세 점 A,B,C에 대해서 A,B,C를 순서대로 봤을 때, 반시계방향으로 놓여있는지, 아니면 시계방향으로 놓여있는지 알 수 있는 방법입니다. 결과적으로는,두 벡터간의 외적값이 양수라면, 반시계방향.외적값이 음수라면, 시계방향.0이라면 직선상에 있거나, 평행하는 경우..
![]()
Closest Pair 2차원 평면 상에서 가장 가까운 두 점을 찾는 알고리즘 1-Dimensional Ver. 1차원인 경우는 NlogN에 가능하다는 것이 이미 증명이 되었다.1차원의 점들을 정렬을 해야지만 가장 가까운 두 점을 찾을 수 있기 때문에,정렬을 하는데 걸리는 시간인 O(NlogN)의 시간이 소모된다. How about 2-Dimensional Ver.? 우선 O(NlogN)보다는 크다; 1-Dimensional Ver. Inputs ⊆ 2-Dimensional Ver. Inputs 이기 때문그리고 그냥 Naive하게 푼다면 모든 점들 쌍에 대해서 거리를 계산해야하니 O(N^2)가 소모된다. Divide and ConquerSort by X coordinates and divide, recu..
