알고리즘 시험 준비 - [6/13 Files] - 2019-09-16

 

 

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  이렇게 접근하면 된다. 

 

이건 외우는게 나을듯 

 

 

O(n^3)