MJay

1. (E+V)logV, 이것만 보면 왜 Disjktra's 가 생각나는걸까 -> Prim일수도 있다고 생각을 해야겠다. 2. 공부할때 배운 Matroid를 생각했어야했다. Convex-Hull도 생각해야한다. 이런걸 생각해야했었다.. -> 다음에는 생각을 꼭 하자 3. DP를 더 많이 공부를 해야겠다. -> DP 문제만 푸느라 다른 문제를 제대로 못 풀었다. 4. C이상만 받았으면 좋겠다. 뭐 그냥 조바심 갖지 말고 살자 -> 기말때 위의 3개 Feedback 꼭 생각을 하고, 직접 써보는게 중요할꺼같다 알고리즘 공부할때는 아이패드 프로로 꼭 써보자. 5. 결과 그때가서 생각하자 -> 그떄 생각하도 안늦음... -> 그떄가서 보자..

Homework 2 Find Upper Envelop of the line intersection. Half-Plane -> Convex Hull using duality between the set of points and a set of lines. N lines -> N points in the dual plane. Upper Envelop -> Easier hull of the convex Using Grahams’s scan algorithm (nlogn) y축 젤 작은거를 찾는다. 그리고 작은거 기준으로 counter-clockwise 로 되는 걸 찾는다. 이걸 각각의 점에서 한다. 총 8개의 점이 convex hull을 구성하는 걸 알고있기떄문에 각각의 Iteration 별로 한개의 점을 찾..

이건 뭐 그냥 하면 된다. (b) -> 2n 이랑 n으로 하면 달라지네 굳!! Problem 3 (1) (2) (3) (4) (5) (6) (7) g(n) 이 더큼 (8) (9) (10) 다른 방법도 있는데 이것도 맞았기 때문에 이걸로 쳐도 될 거 같다. [1 1 1 0] -> 이거의 recursive 이니까 이렇게 하자 To prove that points in S union pk forms the convex hull of {p1, p2,...}, we need to, by definition, verify that 1) S union pk form a convex polygon, 2) the polygon formed by S you pk contains all other points, and 3)..

Matroid 이건 그냥 외워야 할 거 같다. Leftist Tree 는 Rank 즉 the number of nodes on shortest path Minimum Spanning Tree는 이것도 기억하면 될꺼같은데 어떤 weight 가 다른 어떤 edge의 weight 보다 크면 이건 MST에 속하지 않는다.

Quiz 2 재밌는 문제이네 DP 에서 보면 전단계였었나? 아예 전단계는 아니네 이상하다 맞을꺼같은데 아닌게 또 신기하네 ㅎㅎ a2 -> a5 -> a7 1 2 3 4 5 6 7 8 9 2 5 7 8 9 4 2, 10, 8, 6, 14, 9, 11, 15 1 2 3 4 5 6 7 8 9 9 7 1 3 8 2 10 아 True 같은데 왜 글지 반례가 있을꺼같은데 0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15 위키에서 가져옴 0, 2, 6, 9, 11, 15. 여기서 6까지만 봐보면 0, 8, 4, 12, 2, 10, 6, 똑같지만 14까지 봐보면 0, 8, 4, 12, 2, 10, 6, 14 까지 가버린다. 그래서 답이 아니다. 이거 생각해서 False 라고..

이건 쉽지 뭐

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