2016.11.07 정보과학 주말 프로그램 풀이

Prob No.0689 : 스터디 [CH02.2. Algorithm(Design)]
S에서 시작하는 2개의 다익스트라를 돌리면 된다.
첫번째 다익스트라는 S에서 시작하는 정상적인 다익스트라를 돌리고
두번째 다익스트라는 간선의 방향을 반대로해서 S에서 시작하는 다익스트라를 돌린다.

첫번째와 두번째 거리 합 중 가장 작은 것이 정답이 된다.
O(NlogN+M)

Prob No.068A : 시간여행 [CH02.2. Algorithm(Design)]
모든 정점의 값을 0으로 하고, 벨만-포드 돌려서 n번째에도 값이 갱신이 되면 음수 사이클이 존재. 벨만 포드의 정의와 관련 지어 생각하면 쉽다.
for(1~정점 수)
   for(1~간선 수)

O(NM)


이 문제랑 비슷한 문제 중에 똑같은 이름으로 시간 여행이란 문제가 있다.

Prob No.0598 : 시간 여행 [CH03.3.USACO(Silver)]
http://koistudy.net/?mid=prob_page&NO=1432


Prob No.068B : 경곽길 [CH02.2. Algorithm(Design)]
1에서 시작하는 dfs와 간선 방향을 반대로한 2에서 시작하는 dfs으로 둘다 갈수 있는 정점 외에 다 없애주고 위상 정렬로 사이클을 판별한다. 이후 사이클이 없는 DAG 그래프는 dp로 해결할 수 있다.
O(N+M)

Prob No.068C : 최장 공통 부문 문자열 [CH02.2. Algorithm(Design)]
생략
O(N^2)

Prob No.068D : 큐와 함께 놀기 [CH02.2. Algorithm(Design)
queue와 multiset 사용
O(NlogN)


Prob No.068E : 눈사람 머신 [CH02.2. Algorithm(Design)]
i번째의 눈사람의 합과 i번째가 어느번째에서 왔는지만 표시하면 문제가 끝난다.
if m= 0
sum[i]=sum[t];
come[i]=come[come[t]];

else
sum[i]=sum[t]+m
come[i]=t;

O(N)

6문제 다 전에 풀어봤던 문제인데. 대회 중에 못 풀었는지 모르겠다.
풀었던 문제를 빠르게 푸는 연습과
코딩적 습관보다는 논리를 따라 코딩을 해야 겠다.