대엉코딩

0. 시작에 앞서...

- 만약, 그래프가 가중치가 모두 같은 간선들로 이루어져 있다면 BFS(넓이 우선탐색)을 통하여 쉽게

   최단거리를 구할 수 있다.

- 오늘은 가장 유명한 최단거리 구하는 알고리즘인 다익스트라 알고리즘에 대하여 알아보겠다.

1. Shortest-Path 정의

- 그래프 G=(V,E,W)에서 P는 nonempty-path이라 하자

- W(P) (Weight of P) = the sum of the weights (각 간선들의 가중치의 합)  이다.

- 만약 x=y (즉 같은 정점) 사이의 가중치는 0 이다.

- x정점과 y정점사이에 W(P)보다 가중치가 작은 path가 없다면 이 경로가

    shortest-path or minimum-weight path이다

2.Properties of Shortest Paths

- Lemma: shortest path property

- 간단하게 말하면 최단경로는 최단경로들로 구성되어있다 라는 것.

- 이는 귀류법으로 손쉽게 증명할 수 있다.

- if) P가 최단경로가 아니거나 Q가 최단경로가 아니라면(즉, 위 그림처럼 P'가 존재)

           W(P')<W(P)이고 W(P')+W(Q)<W(P)+W(Q) 즉 R이 최단경로가 아니다.

3. Dijkstra's Algorithm(다익스트라 알고리즘)

- Weight are nonnegative (가중치는 음수가 아니여야한다.)

- greedy 알고리즘 이기도 하며 dynamic programming 알고리즘 이기도 하다.

- 기본적인 구조는 prim 알고리즘과 비슷하다.

4.Example

- 가중치가 같다면 알파벳 순서로 선택한다고 가정.

(1) A-출발점

(2) 가중치가 가장 짧은 간선 2를 선택 결과 테이블 UPDATE

(3) AG(3)을 선택

(4) BC(4)를 선택

(.....) 이런식으로 테이블을 업데이트 해서 끝나면 A점으로 부터 다른 정점들로의

최단거리를 테이블에서 불러오기만 하면 된다.

5.Correctness

- 새로운 경로가 나타날 수 도 있는데 최단경로를 이렇게 확정해버려도 되는가?

- 간선의 가중치는 음수가 아니므로 새로운 경로가 나타도 같을 순 있어도, 

   더 짧은 경로가 나타날 순 없다.

6.분석(Analysis)

- 힙자료구조를 이용한 우선순위 큐 사용시 시간복잡도는 O(mlogm) = O(mlogn)

이라 할 수 있습니다.

** divide and conquer(분할 정복) 은 알고 들어가야한다. --> 퀵소트가 사용하는 기법

1.Quick-sort

 - random 한 속성을 가진 형태의 input을 정렬하는 데 성능이 매우 좋다.

 - pivot 이라는 하나의 element를 기준으로  L(less), E(equal), G(greater)로 나눈다 (분할)

 - 나눈후  L 과 G(E U G) 로 다시 recursive하게 sort를 수행한다.

2. Worst Case

 - 최악의 경우 pivot을 잡고 분류를 하는 과정에서 L,G를 나누는데 계속 한쪽으로 몰리는 경우 이다

 - 이럴경우 n-1번을 나누게 되고 (depth = n), 각 단계에서 약 n, n-1, n-2 ....... 1까지 진행되므로

 - running  time의 합은 n+(n-1)+ ... +1 이므로 최악의 경우 O(n^2) 이다.

3. Average Case

 - 평균분석의 경우 O(n*logn) 이다.

 - 최악의 경우는 느리지만 평균분석은 상당히 빠르다.

4. 알고리즘

-partion 별 

5. 특징

 - partion을 한번 하면 pivot은 자신의 위치를 찾는데 그 자리가 최종 출력 위치이다.

 - in-place 로 구현 가능 (추가적으로 사용하는 메모리가 tmp변수 하나 정도로 O(1) 정도

6. 구현

https://www.acmicpc.net/problem/1305

입력 값과 출력값은 간단해서

따로 말할건 없고

kmp알고리즘을 공부하고 첫 문제였는데

lps table을 만들면되는 문제인데

prefix와 suffix를 찾으면 되는 문제이다.

즉 입력받은 문자열의 lps table을 구한 후 

문자열의 마지막 글자 의 lps table에 해당되는 값을 보면되는데

해당 전광판에서 적혀있는문구는 뒤에 아직 나오지 않은 문자열이 있고(1초마다 나옴)

입력 문자열의 prefix와 suffix만 같으면 1초뒤에 나올 문자는 그 뒤에 이어지는 문자열이 나온다라고

생각하고 구해주면 된다.