목록PSU/CSE 565 - Algorithm (30)
MJay
일단 하나씩 적어보자 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..
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 보다 크다 된다고 알고 있으면 되겠다.
Convex - Hull 은 모든 점을 포함하는 점을 이어주는 것이라고 보면 된다. 먼저 y 축으로 Sorting을 한다. sorting을 했을 경우 젤 작은 점 기준으로 또 x 축으로 sorting을 한다. 그리고 먼저 3개의 점을 넣는다. 그리고 4번쨰점부터 계속 방향이 왼쪽으로 가는지 확인한다. 아닐 경우는 pop을 통해 제일 마지막으로 들어간 거를 빼준다. 4번에 대한 설명이다. pb -> pa -> pk 했을때 right 이면 pa를 뺸다 아니면 pk를 넣는다. Graham Scan 은 O(nlogn)이 젤 dominate 하다. 이건 sort 할떄 쓰인다고 보면 될듯 왜 Left 인지 vector 로 설명을 할수 있다. 외적 곱을 했을때 양수이어야 왼쪽이다 그게 중요하다 0이면 그냥 같은 라인..
2019-08-28 이것만 알고있으면 될꺼같다. 이건 Merge Sort를 Divide and Conquer 로 하는 것이다. 별거 없음 그냥 그래서 O(N log N) 이라는 것이다 정리해보면 Master’s theorem 만 잘 알고있으면 된다. 정리해보자면
여유가 생겼으니 낮에는 알고리즘을 해야겠다. 토요일부터 해서 12개는 했어야했는데 하나도 못했다. 뭐 연구가 먼저니까 일단 얼른 해보자 뭐부터 하지 한번 봐보자 퀴즈 - 3개 과제 - 3개 파일 - 13개 하나도 안 풀었네 파일 12개를 봐볼까 그게 나을꺼같은데 ---- 일단 교수님의 Style을 알아야겠다. 문제를 이렇게 내시네 Rates of Growth 문제 많이 풀어봐야지 뭐 PPT를 일단 얼른 다 보자 -> 30분에 1 page 씩 볼까 그것도 괜찮은거 같다. -> 일단 하고 보자 2019-08-26 알고리즘의 정의 Step by step procedure to solve logical and mathematical problems Another Example 나중에 다 다루니까 넘어가는 걸로 ..