해나의 컴공생존기

1. Matrix Multiplication N*N 배열 두개를 곱하는 과정은 O(N^3)이 소요된다. 한칸만드는데 O(N) * n^2개 칸 존재 여기서도 Divide and Conquer 를 사용할 수 있다. 이렇게 되면 식이 아래와같이 된다. T(N) = 8T(n/2) = 2^3 T(n/2) = 2^6T(n/2) = ... =(2^3)^logn 2. Strassen Alg 3. Karatsuba Alg n bit 곱하기 n bit 는O(n^2)에 할 수 있다. 하지만 Karatsuba Alg를 사용하면 n에 가깝게 수행할수있다.

Convex Hull 이란 평면 좌표에서 어떤 점들이 있을 때 모든 점들을 포함 하는 가장 작은 볼록 다각형을 의미한다. (점들의 바깥에서 고무줄을 놨을 때 만들어지는 도형) 점들을 정렬하는 과정이 필요하기 때문에 Convex Hull 을 만드는 알고리즘의 시간 복잡도는 O(nlog n)보다 빠를 수 없다. 1. Count - Clock - Wise (CCW) 이 알고리즘은 세 점이 관계를 표현할 때 유용하다. A(x1,y1), B(x2,y2), C(x3,y3)가 있다고 해보자. A와 B의 기울기 + B와 C의 기울기를 가지고 회전 방향을 알 수 있다. A와 B의 기울기 > B와 C의 기울기 → 우회전 A와 B의 기울기 < B와 C의 기울기 → 좌회전 A와 B의 기울기 = B와 C의 기울기 → 한 직선 ..

1. Closest pair Closest pair은 주어진 점들 중에서 가장 가까운 쌍을 찾는 문제이다. 이 문제는 직관과 심하게 충돌하는 경우가 많다 1차원일 때는 단순하게 sorting 하면 구할 수 있고 2차원일 경우 두 점사이의 거리공식으로 구할 수 있다. 하지만 이 경우에는 O(n^2) 이 필요하다. 이 방법은 어렵지 않다. 우리의 목표는 O(nlogn)이다. 2. Divide and Conquer 먼저 이들을 절반으로 나눈다. (나누는 것은 x 를 기준으로 sorting 한 뒤 나눠주면 된다) 나눠거 각각 가장 최소거리를 구해준다. 왼쪽의 최소걸이는 DL 오른쪽의 최소거리를 DR이라고 하자. D = min(DL , DR) 라고 D를 정의하자. 중심 선으로부터 D만큼의 거리에 선을 그으면 위 ..

1. Quick Sort Quick Sort의 알고리즘을 한번 보겠다. 1. 배열에서 하나를 pivot으로 설정한다. 2. 배열의 가장 앞을 가르키는 i와 가장 뒤를 가르키는 j로 설정한다. 3. i와 j가 만날때까지 아래의 과정을 반복한다. 3-1. i가 가르키는 값과 pivot이 가르키는 값을 비교해서 i가 더 작다면 pivot보다 더 큰 숫자를 만날때까지 i를 증가시킨다. 3-2. j가 가르키는 값과 pivot이 가르키는 값을 비교해서 j가 더 크다면 pivot보다 더 작은 숫자를 만날때까지 j를 증가시킨다. 3-3. 둘다 적절한 값을 찾는다면 i가 가르키는 값과 j가 가르키는 값을 바꾼다. 4. 반복문을 나왔다면 pivot값과 j가 가르키는 값을 교환한다. 5. 처음부터 j까지, j 다음부터 끝까..