8/27 Problem Solving

3013 부분 수열의 중앙값 (G3)

 

주어진 수열에서 중앙값이 B인 부분 수열의 개수를 계산해야한다. B의 위치를 기준으로 이전의 원소들을 보면서 psum을 B보다 크면 +1, B보다 작으면 -1해주면서 map에 특정 누적합 발생 빈도를 기록한다. 그리고 B의 위치부터 오른쪽으로 보면서 다시 psum을 계산하면서 -psum이 왼쪽 부분에서 발생했는지 확인해서 해당 부분 수열의 개수를 답에 세주면 된다.

 

http://boj.kr/96cf2289845049e38029a2fbfe662fd5

 

 

1865 웜홀 (G3)

 

벨만 포드 알고리즘을 적용하여 음의 사이클이 존재하는지 여부를 판단하는 고전적인 문제이다. 그래프의 컴포넌트가 하나가 아닐 수도 있으므로 편의상 가상의 정점 0을 추가하여 실제 모든 정점을 이어줬다. 정점의 개수가 N이라 했을 때 어떤 두 정점의 최단 경로는 최대 N-1개의 간선을 가질 수 있다. 따라서 relaxation을 N-1번 반복해준다. 그 이후 한번 더 검사했을 때 더 작은 경로가 발견되면 음의 사이클이 존재한다고 판단할 수 있다.

 

http://boj.kr/0d1081ce25884dce9c6953ea8810b99e

 

 

30805 사전 순 최대 공통 부분 수열 (G4)

 

LCS 문제처럼 DP를 사용할 수도 있겠지만 공통 부분 수열 중 사전 순으로 가장 나중에 오는 것을 고려해야하므로 그리디 접근이 더 적합하다. 먼저 공통된 수 중에서 가장 큰 수를 찾는다. 여기가 공통 부분 수열의 시작이 될 것이다. 그 이후 각 해당 위치보다 뒷부분만 고려하여 다시 가장 공통된 가장 큰 수를 찾는다. 그러한 수가 여러개가 있을 경우에는 더 앞의 인덱스를 택한다. 이 과정을 더 이상 남은 수열 구간이 없을 때까지 반복한다.

 

http://boj.kr/5ba37dd5fbf24decbba0edb413519767

 

 

14938 서강그라운드 (G4)

 

플로이드 워셜 알고리즘으로 모든 지역간의 최단거리를 구한다. 그리고 모든 지역에 대해서 수색범위 안에 들어오는 아이템의 개수의 최댓값을 구해준다. O(N^3)인데 N이 최대 100이므로 시간 내에 가능하다.

 

http://boj.kr/9a37af75773c4b349dae24a459c585d0

 

 

6497 전력난 (G4)

 

MST를 만들어보면 된다. 역으로 전체 간선의 비용의 합에서 MST을 만드는데 드는 간선 비용을 빼주면 된다.

 

http://boj.kr/b441993f94694f90a5576a7114401cac