MJay

저녁에는 확실히 집 청소 밥 만들기 빨래 이렇게만 해도 2시간이 걸린다 ㅜㅜ 힘들다...

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 라고..

이건 쉽지 뭐