해나의 컴공생존기

1.근사 문자열 매칭과 거리함수 근사 문자열 매칭 : 비슷한 문자열 비교 (엄청 빠른 방법은 없음) 거리함수 해밍거리 : 두 문자열을 같은 자리를 비교해서 다른 것의 개수를 센다. 밀리는 경우는 체크 못함 편집거리 : 해밍거리와 비슷하지만 insert, delete 와 change 존재 가중편집거리 : 편집거리와 비슷하지만 문자별로 가중치 존재 2. 편집거리 편집거리란 한 문자열을 다른 문자열로 변경하기 위해 필요한 편집연산들의 최소 수이다. 편집연산은 삽입, 삭제, 교체가 존재한다. 이를 구하는 방법은 문자열 두개로 표를 만든뒤 각 칸에 편집거리를 계산해주는 것이다 . 편집거리는 아래와 같이 계산한다. D(i,j)는 S1의 i번째 인덱스와 S2의 j번째 인덱스를 비교한다는 의미이다. D(i, j-1) ..

1. 문제정의 모든 노드 쌍들마다의 최단경로 구하기 (path까지는 어렵기 때문에 길이만 구할 것이다) undirect 그래프라고 가정. 가장 쉬운방법은 다익스트라 알고리즘을 n번 돌리는 것이다. 2. Floyd Warshall Alg 각 노드별로 번호를 부여했다고 가정하자. i → j로 가는 최단경로를 구할 건데, {1, 2, ..., k}번 노드 중에서만 거쳐가는 최단 경로를 찾으면 된다. 이 과정을 k가 0부터 N까지 반복한다. (k가 n일 때가 최종 답이된다,) 즉, 구하고자 하는 것은 모든 (i, j) 쌍에 대하여 1번부터 k번 노드 중에서만 거쳐서 갈 수 있는 최단경로이다. k=0이라면 {공집합}이고 i와 j를 연결하는 것은 direct edge밖에 없다. direct edge가 없다면 답은 ..

1. 문제 정의 각 칸에 숫자가 적혀있을 때, 합이 최대가 되게 하는 Subarray의 합을 구하는 것이다. 0칸의 합도 허용하는 버전과, 허용하지 않는 버전 모두 소개될 것이다. 2. idea : O(N^3) 1.모든 경우의 수를 다 해본다. 크기가 1인거 n개, 2인거 n-1개,...,n인거 1개 → n(n-1)/2 => (N^2) 한 시행이 걸리는 시간 N. 쭉 훑으면서 더해야하기 때문. 2. 칸을 나누는 선은 n+1개 이다. 이 중 시작선과 끝선을 두개 뽑는다 n+1C2 => (N^2) 한 시행이 걸리는 시간 N. 쭉 훑으면서 더해야하기 때문. 3. idea : O(N^2) 아이디어는 앞에와 같다. 이 방법은 계산에 쓰이는 시간 N을 절약하는 것이다. n개가 계산이 되어어있고 n+1개를 계산해야한..

1. 문제정의 행렬의 곱에서 어떤 행렬을 먼저 곱하냐에 따라 걸리는 시간이 달라진다. 행렬들은 M1, M2, ... Mn으로 표현되며, 행렬의 크기는 di-1 * bi로 표현된다. Cij는 Mi부터 Mj까지 곱했을 때 최소 비용을 의미하며 C1n이 최종 답이 된다. 2. solution 전체 답을 제일 좋은 답으로 만들기 위해서는 어떤 곱을 나중에 해야할까? 우리는 이 문제에 대한 해답을 알지 못한다. 따라서 하나씩 다 해볼 것이다. Cij에서 i-j가 작은 값부터 해볼 것이다. 1) i-j =0 C11,C22,C33, ... Cnn 위와 같은 경우는 비용이 모두 0이라고 할 수 있다. 2) i-j =1 C12,C23,C34, ... Cn-1n 비용은 di-1 * di * di+1 3) i-j =2 C1..

1. Select Working Days 1.1 문제정의 N일의 각각 Pay가 지정되어있다. 가장 돈을 많이 벌 수 있도록 일하는 날짜를 골라야한다. 연속근무는 불가하다. 2. solution X는 그날 일을 안했을 때, 그날까지 벌 수 있는 최대의 돈이다. O는 그날 일을 했을 때, 그날까지 벌 수 있는 최대의 돈이다. 노란색으로 색칠한 것은, 결과가 나온 후 역추척한 것이다. 3. Code 이 코드는 내용을 모르면 알아보기 쉽지 않다. 열 인덱스 0: 그 날 일을 안하는 것중에 제일 좋은 것 열 인덱스 1: 그 날 일을 하는 것중에 제일 좋은 것 배열 생성하고 첫 날 일을 할 때&안할 때의 초기값을 넣어준다. day2부터 계산한다. 그 날 일을 안할 때 = MAX(그 전날 일 할때 , 그 전날 일 안..

1. Fibonacci Number 피보나치 수열은 f(0) = 0 이고 f(1) = 1 일 때, f(n) = f(n-1) + f(n-2) 를 따라가는 수열이다. 1.1 Recursion 재귀는 독립적으로 실행할 수 있어야 한다. 전체 문제가 있고 잘라서 자른 문제가 전체인 것처럼 동작한다. 머지소트는 왼쪽 배열이 오른쪽배열의 영향을 받지 않는다. 하지만 그래프와 같은 경우는 영향을 받을 수 밖에 없다 완전히 독립적으로 잘라서 재귀로 적용하기 힘들다. 독립적인 부분문제의 답으로 전체의 답을 만든다는 점에서 분할정복과 비슷하지만 재사용에서 다르다. 피보나치에서 F(n)의 값은 변하지 않는다. F(6) = F(5) + F(4) F(7) = F(6) + F(5) 여러 곳에서 쓰이지만 F(5)의 값은 같다. 이..

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. Selection Problem and Approximate Median quick sort에서 우리는 어떻게 가장 좋은 pivot을 얻을 수 있을까? 만약 우리가 O(N)에 best pivot을 뽑으면 최악의 경우가 O(nlogn)가 되지 않을까? Selection Problem 은 k번째 작은 것들을 찾는 것이다. 이것은 median을 찾는것과 비슷한 시간복잡도는 갖는다. Selection Problem을 O(nlog)으로 구현하는 것은 쉽다. 그냥 sorting 하면되기 때문이다. 하지만 O(nlog)은 필요가 없다. 2. Selection Approximate Median with Quick Sort pivot으로써 Approximate Median을 찾으면 quick sort를 O(nlog..