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

[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)

 

|V| = O(mn)

 

그냥 외워야할듯 잘 모르겠다. 

 

그리고 이제 shortest path에서의 memory를 줄여서 할 수 있냐?

 

이건 고등학교 때 배운 빠른 길 찾는 것이다

 

i+1 , j+1 + distance

 

i+1 , j + 1

 

i j+1 1 

 

이렇게 하면 된다. 

 

F -> the length of the shortest path from (0,0) to (m, n)

 

H -> length of the shortest path 

 

즉 Divide and Conquer로 해보려고 한다. 

 

Running time to find k* = O(mn) 즉 m가랑 n개를 다 비교해야 하니까 그런다 .

 

Space는 작은 O(n) 이면 된다. 

 

그래서 Divide and Conquer로 the shortest path를 찾을 수 있다. 

 

Divide and Conquer에서 중요한 건 y축을 자를 적절한 k*를 찾아야 하는데 그건. 

 

절반으로 잘랐을 경우 즉 최소를 만드는 k*를 찾아야 하고 그것이 O(mn) 만큼 걸린다. 

 

Divide and Conquer 이거 무슨 뜻일까? -> 다시 첨부터 봐보자 

 

먼저 절반씩 잘라서 compute를 한다. 그리고 k 중에서 제일 작게 만들어주는 k*를 찾는다. 

 

그리고 x축은 절반 y축은 k까지 하여 divide and conquer를 한다.

 

나머지도 그렇게 한 다음에 Union을 해준다. 고러하여 Running Time은 O(mn) + T(m/2, k*) + T(m/2 , n-k*) 

 

mn + mn/2 + mn/4 … 

 

이렇게 되기 때문에 이거 또한 O(mn)이 된다.