MJay

Def(matroid) - Let x be an infinite cost. S - subsets X A belong to S, we call A “independent” (X, S) forms a matroid if hereditary property: if A belongs to S, then for any subset of A, A belongs to S (유전이지 왜냐면 A1 은 A에서 나온 애니까) A 랑 B랑 둘 다 S에 속하고 A보다 B가 더 크면 A에 속하지 않고 B에 속하는 x 가 있을 것이다. 그리고 그건 A 랑 X 랑 Union 해도 S에 속한다. exchange라는 게 B에 속하는 걸 A에 줘도 된다는 뜻으로 보인다. Optimization Problem Input - matroid ..

notes-2019-10-07 undirected graph 에서 V1 = V and E

일단 하나씩 적어보자 PQ는 V- Ak* 속하지 않는 Vertices를 가지고 있다. dist(u) 는 s to v로 가는 length를 가지고 있다. 그리고.그리고 그건 A*k에 속하는 Vertecies를 통해서다. V * 가 PQ에서 사라지는 순간 -> dist(v*)와 s에서 v*로 가는 거리가 같아진다. 그 다이 스트라에서 weight를 뜻하는 거 같네 별 의미가 없는 거 같은데 그냥 문제를 얼른 풀어봐야겠다. Running Time은 Delete Min에서 VlogE Decrease Key에서 ElogV (V+E) logV 이제 Binary Heap을 사용하여 구현을 할 수도 있다. Heap은 min-heap 이랑 max-heap을 사용할 수 있다. 이게 쉬운 거니 넘어가자 이건 뭐 당연한 건데..

[9/13] - 2019-09-25 Sequence Alignment 은 젤 끝쪽 같을 경우 1을 더해주고 아니면 [i+1 , j] [i j-1]로 따지면 된다. 이걸 배열로 나타낸다면 이런 느낌이다. 고래서 Time Complexity 즉 SubProblem은 O(mn)이라고 보면 된다. Space -> Result 즉 제일 짧은 횟구만 알고 싶으면 O(n)이지만 배열도 알고 싶으면 Time Complexity 랑 똑같이 된다. 여기서 Space Complexity를 증가시킬수 있다. DP/BF -> 벨만 포드니까 O(|V||E|) DAG 는 O(|E|)라고 보면 된다고 이게 무슨 말인지 모르겠네. DAG 는 내가 아는 건 DFS BFS로 해서 O(V + E) 밖에 모르는데 말이지… |E| = O(mn..

아침에는 집에서 밥먹으려고 멍때리다가 뭐 한거같지가 않네 학교를 가는게 좋을꺼같다. 아침에 인나서 그냥 거실에 앉지 말고 베드룸, 화장실, 식탁에서만 할꺼 다하고 30분만에 나가는걸 목표로 해봐야겠다.

Bellman Ford 는 V-1 까지 Update을 하고 한번 떠 돌려서 값이 다른지 안다른지 해서 Negative Cycle 을 판별한다. 이 과정은 각각의 제일 짧은 거리 즉 어느 node 에서 어느 node로 가는게 젤 빠른지 알려주는 식이다. best array를 사용하는 예시를 보여준다 BF Algorithm 의 특징 어떤 v에서 거리가 무한대보다 작으면, s -> v 가는 path 가 dist(v) 랑 같아질수있다. 당연한거 아닌가… Induction으로 증명을 해보자 한다. Bellman Ford 답게 iteration 이후 -> dist(u) >= distance(s,u) 가 있을 것이다. dist(v,k) >= dist(u) u 는 전 단계이다. 어쩃든 |v| - 1 iteration ..

일단 Longest Increasing Subsequence 랑 RNA Secondary Structure 복습을 하고 DP 방식으로 shortest path problem을 풀어본다. Disjktra’s Algorithm 에서 전 단계의 node + weight를 더했을떄 더 작은걸 고르는 느낌이다. 하지만 이런 계산을 할 경우 음수 weight 가 있다면 계속 값이 줄어드리 오류가 생길수도 있다. 그걸 증명한다. 그걸 앞서 Cycle 이 생기지 않으려면 Vertex - 1 개수의 edge 로 이루어진 shortest path가 생긴다. 위의 식을 보면 전 단계까지 돌린 distance 이든지 전 단계에서 + weight를 추가해서 최소를 가져가면 된다. V-1 까지 다 돌리고 나서 G가 cycle이 ..

Divide and Conquer 를 지금까지 이야기를 했다. Merge-Sort Convex-Hull Half-Plane Intersection FFT 2번 3번은 다 duality에 속한다. 다 보면 O(nlogn) 이네. 그리고 이제 Dyanmic Programming을 하면 된다. DP는 퀄 떄문에 많이 해봐서 어렵지는 않다. Longest Increasing Subsequence - 조심해야 하는 점은 이건 Substring이 아니고 subsequence 라서 연속이 아니다. 그래서 전 단계 말고 그냥 j 단계 1< j < k 이런 느낌으로 풀면 된다. RNA 는 양쪽이 같지 않으면 마지막 단계에서 1을 뺴면 되고 아니면 양쪽이 같으면 한번 k로 나눠서 1, k-1 + k+1 , j-1 이렇게 ..

Fast Fourier Transform 이다 이건 그냥 문제로 퀴즈에 나오니 그걸로 풀면 될꺼같다. Divide and Conquer 로 하면 F(n) = 2 * F(n/2) + O(n) 이렇게 하면 될꺼같다. 이정도만? 전체

2019-09-09 C는 convex hull이다 이거랑 half-plane 이랑 연관시켜서 보여준다. half-plane 이다. 정리해보자면 convex set의 교차점도 convex이다 half-plane을 교차하는 것이다. from http://www.secmem.org/blog/2019/09/17/Half-Plane-Intersection/ Removal Surface 이랑 비슷하다. Divide and Conquer - 즉 절반으로 나눠서 한 거를 의미하는 거 같다. 쉽게 생각하면 점은 라인으로 바뀔 수 있다. 이게 거꾸로 된다. 이게 중요하네 p 가 l 보다 크면 반대로 l은 p 보다 크다 된다고 알고 있으면 되겠다.