알고리즘 시험 준비 - [2/3 Quizzes]

Quiz 2

 

 

재밌는 문제이네 

 

DP 에서 보면 전단계였었나?

 

 

아예 전단계는 아니네

 

이상하다 맞을꺼같은데 아닌게 또 신기하네 ㅎㅎ 

 

a2 -> a5 -> a7

 

1 2 3 4 5 6 7 8 9 

 

2 5  7 8 9 

 

4 2, 10, 8, 6, 14, 9, 11, 15

 

1 2 3 4 5 6 7 8 9

 

9 7 1 3 8 2 10 

 

아 True 같은데 왜 글지 

 

반례가 있을꺼같은데 

0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15

 

위키에서 가져옴

 

0, 2, 6, 9, 11, 15.

여기서 6까지만 봐보면

 

0, 8, 4, 12, 2, 10, 6, 똑같지만

 

14까지 봐보면

 

0, 8, 4, 12, 2, 10, 6, 14 까지 가버린다. 그래서 답이 아니다. 이거 생각해서 False 라고 하면 되겠다.

확실한건 전 단계가 순간 increasing 일수도 있으니 조심해야겠다. 

 

 

G -> Graph with N vertices. 

 

P -> shortest path from s to v at most n edges.

 

Q -> shortest path from s to v at most n+1 edges.

 

P = Q  shortest path 가 같다는 것인가? -> negative cycle 

 

Negative Cycle 은 그러니까 값이 변하면 안된다. 값이 음수인지 양수인지 알수가 없으니 그런거 같다. 

 

저 과정이 되야 값이 안바뀌니까 그렇다. 

 

 

Edit Distance는 뭘까

 

https://www.geeksforgeeks.org/edit-distance-dp-5/

 

 

 

FFT(A,w) 

 

음 예시가 없어서 애매하네.. 

 

w3  -> 1 로 하면 되는거같다. 예제뭐 없나