알고리즘 연습 6일차

아침에는 일찍일어났다. 그러나 어머니를 따라 산에 가야만했다.

그림 이뻐서 재탕

11:20 - 집에서 홍대로 출발 할수 있나 몰라..

우선 잉여 대기 시간에 알고리즘이나 생각하자.

우선 http://algospot.com/judge/problem/read/NERD2 

2. binary tree 1개 (nlogn)

3. 일정 간격의 격자로 공간 분할 (100칸씩 가로 세로로?)

푸는데 2번이 3번보다 빠를 이유는 없어보인다.

sum 루틴은 중복되고, erase 루틴이 여러 map에서 동작해야 하는 정도?

우선 upgrade부터 시켜 보자. 망할..

13:49 분 - 마포 도서관에 자리를 잡음. 망할

흠 줄여도 마찬가지 vm에선 340, g++에서는 1400 초가 걸렸다. 버그도 있어서 이건 못써먹을듯.

몇분 생각해 보고 다른 방법을 찾자.

15:14 분 - 졸다가 어쩌다가 잠오넹

sparse matrix가 적당하지만 거기엔 range query가 없어

거기다 random input을 이용한 test에서 결국 문제는 insertion이었음.

46% - insertion, 16% - erase : 46 ms  뺄게 없는 data structure  는 문제 없는 경우가 많음

어떤 연산이 overhead인가. 없다면 아예 발상의 전환이 필요할 듯 한데..

15:58 - 빡쳐서 skip Graph가 무척 허약하므로 (딕스트라도 머였는지 햇갈린다) routing을 풀기로 한다.

딕스트라. 근대 댓글에 런터임/시간 초과를 호소하는군.. 이것도 왠지 망삘이..

SE 아주머니 제게 지혜를 주세염.

..으허헝 이것도 Time over여 누님 아이디어 좀 주세염. 망할

적용할 남은 건덕지들

1. Candi Set을 Heap으로 관리

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

3. duplicated line 제거