목록PSU (46)
MJay
Merge two binary hea takes O(n) time 이게 일반적인 사실이다. 이걸 O(logn)으로 하기 위해서 쓰는게 leftist tree 이다. rank 라는게 shortest path from v to NULL leftist propoerty -> T 에 있는 vertex 를 가지고 봤을떄 vertex 의 left child 의 rank 가 오른쪽보다 항상 같거나 많다. Fact - rank(root) = O(logn) 이다 당연하다 이건 그래서 이 둘을 Merge 하기 하려고 한다. 쨋든 O(logn) 으로 바뀐다. 그릭 봐서 swap 을 해준다. ㅇ Find Min - return root delete - min 은 root끼리 merge 한다. insert - Merge (PQ..
OS 공부중 퀄리파잉 http://pages.cs.wisc.edu/~remzi/OSTEP/ 다 봐야함 일단 전체를 보자면 Intro Virtualization Concurrency Persistence 크게 있다. 1번째 단원은 - Table of Contents 2번째 단원 - Dialogue 3번째 단원 - Dialogue 4번째 단원부터 하면 될꺼같다.
CSE 560 을 봐보자 2019-10-02.pdf PQ stores the vertices in V - Ak* (전체에서 A를 뺀 것) Ak* = {V1*, V2*, Vk*} ak가 아마 s 랑 v 랑 다 같이 Ak에 속한다고 일단 생각하자 V* 가 PQ 로 부터 지워지면 - dist(v*) = distance (s, v*) v1, v2, v3, v4, v5 지금 이게 뭐를 하고있지? Binary Heap 을 얘기하는 건가? 그냥 그래프를 그려볼까 Binary-Heap 은 find-min -> O(1) min heap delete min, decrease-key, insert -> log(n) # times -> delete min, find-min, insert - Vertex 랑 관련이 있고 dec..
다시 정리 Crossing Edge 는 항상 MST 에 속한다. 증명 - 다른 crossing edge를 할 경우 결국 crossing edge 기존꺼가 더 작다고 해서 접근한다. Prim은 Priority Queue 를 사용해서 min crossing edge를 찾는다. Kruskal은 Cycle https://progresivojs.tistory.com/7 https://progresivojs.tistory.com/3
Prim Algorithm crossing edge 의 최소를 찾기 V 는 Vertex 에서 S 가 뭘까? 그냥 Vertex Set을 뜻함 이거는 좀 찾아봐야겠다. Kruskal 은 알겠다. 뭐 대충은 알겠다 일단 한국말부터 알아야할듯..
notes-2019-10-07 undirected graph 에서 V1 = V and E
금메달을 찍었다. 왜냐면 다 풀어봤기 때문이다. 이렇게만 나오면 너무 감사하겠다 낼은 transfer 할꺼를 다 해봐야겠다.
알고리즘은 책으로 시작하는게 좋아보인다. 일단 책으로 어디까지 했는지 다 정리를 해보는게 좋을꺼 같다. CSE 565 KT 위주로 보면 될꺼같다. 모르는거 위주로 봐야할꺼같다. 2.2 2.4 2.5 4.4 4.5 5.1 5.2 5.3 5.4 5.5 5.6 6.1 6.5 6.6 6.7 6.8 6.10 homework 랑 퀴즈도 해야한다. 책을 먼저 보고 해결을 해보자 2.2 Asymptotic Order of Growth 중요한거랑 모르는거랑만 정리를 해보자면 O, Theta, 하나가 뭐드라 근데 이건 이제 고수다. Pass 2.4 A Survey of Common Running Times Merging Two Sorted Lists O(n log n) Time 이 정도 2.5 A More Complex ..
Computer Architecture 퀴즈 준비 RISC에서 문제는 나올꺼같지가 않다. IBM 퀴즈 이것도 나올 문제가 없는거 같은데 Optimum PipeLine 이것도 뭔지 몰겠네 Branch History 만 챙기면 되겠네 Associativy 이거 없애면 더 나으려나 없는게 더 나을꺼같은데 퀴즈는 진짜 건질게 없어보인다.
Computer Architecture 공부 Throughput 이다. PipeLining으로 인해 할수있는 양이 늘어났다. Cache - Temporal, Spatial Locality 2 * 10 ^ 9 을 역수로 하면 된다. G -> 2 ^ 9 이였나. 그냥 외우자 일단 Cache는 보면 physical address 랑 관련있는 듯 Number of sets -> 64kB / 2 * 32 = 2 ^ 10 10 bits 이다. 즉 Index가 10개라는 걸 뜻한다. 2 ^ 5 = 5 bits are block offset -> offset은 아마 set 안에서 몇개의 블락이 있는 거니까 32B Cache -> 2 ^ 5 을 뜻하는 거 같다. Tag Overhead - 17 bits * 2 ^ 10 ..