kthng

codeground : 캠퍼스와 도로(1) [SCPC 2015 - 1차 예선] https://www.codeground.org/practice/practiceProbView.do?probId=15 SW역량테스트를 맞아 codeground문제들도 써보려고 한다.그 첫번째 문제..이 문제는 v번의 다익스트라 알고리즘으로 떠오르는 아이디어 그대로 해결할 수있다.시간복잡도는 v*(v+e)log(v+e)가 되어 시간안에 충분히 해결할 수 있을 듯 하다.다만, 방문하는 도시까지의 거리가 같을 때가 문제 ㅜㅜ...힙에 push하기 전에 방문노드를 체크해주면 왜안되는지 모르겠다. 아직 밝혀내지 못했음... 해결한 방법은, 코드가 조금 길어지긴하지만 스타팅 지점인 v번째 도시에 대해 다익스트라 알고리즘으로 모든 경로까지..

boj 2381 : 최대거리 https://www.acmicpc.net/problem/2381 n^2만에 해결할 수 있는 방법은 간단히 떠올릴 수 있다. 하지만 n이 최대 50000이기 때문에 시간초과. nlongn 이하의 해결법을 찾아야한다. 답은 (x+y의 최대값) - (x+y의 최소값), (x-y의 최대값) - (x-y의 최소값) 둘 중 큰값이 답이다.응??? 증명을 해보자.1. (x+y의 최대값) - (x+y의 최소값)이 답일 경우1.1 앞 괄호를 (x1,y1), 뒷 괄호를 (x2,y2)라 두면,1.2 x1 > x2이고, y1 > y2의 경우만 가능하다.1.3 그렇다면 만약 x1 < x2이거나 y1 < y2라면? 답에 모순이 생기지 않을까?x1 < x2이거나 y1 < y2라도 상관없다는것을 증명해..

boj 1238 : 파티 https://www.acmicpc.net/problem/1238 시간초과가 나지 않겠나? 라는 의문을 가졌지만, 잘 생각해본다면 단 두번의 다익스트라로 해결이 가능하다.^^.. 우선 파티장소에서 모든마을까지는 단순한 다익스트라의 구현으로 구할 수 있다.그렇다면 각각의 마을에서 파티장소까지의 경로는 어떻게 구할 수 있을까?답은 경로를 거꾸로 저장한 edge를 저장하는 것으로 해결 가능하다.a->z 경로의 최단거리는 반대경로의 최단거리와 같다. 호기심에 floyd로 시간초과인지 테스트해보았지만 역시나 시간초과^^