MJay

일단 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 나중에 다 다루니까 넘어가는 걸로 ..

오늘 Jashwant를 만났다. 그 이유는 아니 Jashwant 도 교수님도 Spock 논문에 참여했으니 그때 인용한 Costless 논문 내용을 잘 아는데 내가 굳이 발표할 필요가 있나 생각이 들어서다. 만나본 결과 그건 아니었다. 몇 부분밖에 몰라서 디테일하게 준비를 해야 하는 거였다. 다시 준비를 해야 할 줄 알았는데 매우 다행이다.. PPT를 만들었는데 75 page 라서 20~30 page로 줄이는 게 맞을 거 같다. ---- 교수님들이 관심 있어야할 것을 생각하고 적자. 1. 예로 들면 Cost Graph 이런 디테일한 거는 다 알고 있다. 그 대신 Node와 Edge 가 무엇을 뜻하고 하는지 이런 걸 적어야겠다. 2. Algorithm Analysis 는 안 적어도 될 거 같다. 3. Eva..

어제 왜 그랬는지 몰겠지만 3시에 자서 9시에 인났다. 역시 6시간 이상은 자야한다. 오늘은 2시에 자서 8시에 인나는 걸 목표로 해보자. 일단 1시간 30분 남았으니 - 얼른 연구를 하고 낮에는 알고리즘을 하고 저녁에는 다시 연구를 해보자 그게 나을꺼같다. 알고리즘은 될지 몰겠지만 12개를 봐보고 연구는 50 pages 까지는 대본을 써보자

21 page We can define models in many aspects. For the resource model, we think the AWS Lambda resource model as f with only one variable as a requesting memory. Other options are the default. 22 page For Data model - The data sent to the Lambda function is in the form of a request encoded in JavaScript Object Notation (JSON) format. The above request is retrieving images from S3. 23 page Model t..