알고리즘 연습 7일차

9:57 분 - 오오 휴일 잉여한 하루

1. Candi Set을 Heap으로 관리

2. 왕복 보두 같으니 중복 적용 금지

3. duplicated line 제거

머 Dijkstra Algorith으로 안되니 위의 변형 적용하기 전에

Heap Dijkstra, Pibonacchi dijkstra를 찾아봄

알고리즘 대회 책에는 실제 구현하면 느리다고 되어있는데

피보나치에 대한 것 Heap 을 사용하는것의 장단점에 대해 기술해 놓음.

당연히 사용 안하면 이문제 폿풀게 해놨으니..

그건 저자 기준이고 얼마나 느린지는 파악해볼 필요가 있는듯.

http://stackoverflow.com/questions/504823/has-anyone-actually-implemented-a-fibonacci-heap-efficiently

boost 라이브러리를 응용한 것으로는

Generating graph...10000 vertices, 20000000 edges.
Running Dijkstra's with binary heap...1.46 seconds.
Running Dijkstra's with Fibonacci heap...1.31 seconds.
Speedup = 1.1145.

나은것 같이 보인다. 근대 edge가 좀 많네 dense의 기준도 살펴볼 필요가 있는듯

14:15 - 카페에서 계속 쳐웃는 아줌마가 있다. 망할

14:26 - 그만좀 쳐웃어라 썅년아 으아아ㅏ앙

After I compiled with very strong optimizations, binary heaps got an enormous boost. In my tests, Fibonacci heaps only outperformed binary heaps when the graph was incredibly large and dense, e.g.:

http://algorithms.soc.srcf.net/notes/dijkstra_with_heaps.pdf 

dense 라면 그냥 버젼이 더 빠름여..

머 하여간 다른거 치우고 우선 문제는 2만 edge랑 1만 vertex니까 sparse 하다고 볼수 있고,

1. 우선 set만 관리할 생각이었는데 보통 k 찾아서 update하넹 어케 해야하는지 생각해보자

2. if 로 검사하니까 그게 그거다.

3. 줄여도 order는 변화없다. 적용하지 말자.

15:47 - 몇시간 동안 공부함. 결론은 적용해보자. 안하면 안는다.

http://algorithms.soc.srcf.net/notes/dijkstra_with_heaps.pdf

1. STL priority quque 사용 : 이건 모든 키를 넣어둘 수 없다. 필요한 것만 넣는 방식 

(그래도 중복 키가 발생하므로 used check로 때워야 하넹)

http://stackoverflow.com/questions/6333847/implementing-dijkstras-algorithm-using-stl-make-heap

http://codereview.stackexchange.com/questions/37422/stl-and-dijkstras-algorithm-optimization

decrease key를 지원하지 않기에, 직접 vector를 이용해 만들던가 해야함.

2. map을 이용

16:03 - priority quque 안 써봤으니 한번 써보자.

18:01 - priority quque를 이용한 버전을 통과 근대 시간이 1.2 초넹. 근대 1위 200ms도 비슷한 방식인것 같은데 문제는 멀까. 우선 scanf로 바꿔보고 개선하자 그다음에 map도 넣어보고 코드 길이도 반절로! 오랜만에 기쁘넹.

22:23 - 집에와서 밥먹고 공원 산책하는데 징집. 앉으니 10시넹

You need to pass the type of the lambda as a template argument, not the lambda itself. What you want is this:

auto mycomp = [](const int&a, const int& b) { return a < b; };

std::map<int, int, decltype(mycomp)> test(mycomp);

map으로 이용시 730ms / priority quque사용시 450ms

24:08 코드 정리후 제출 후 Repo 정리.

27:42 : codeforce 참전 - 3번 구글 검색 후 왠지 길이 보였는데 시간 부족