kthng

Rectangles [SCPC 2016 - 2차 예선] https://www.codeground.org/practice/practiceProbView.do?probId=30 문제는 저 점 (7, 3.5)를 찾는 것이다.R1은 R3을 포함하고, R3는 R4를 포함한다. 그리고 R1,R3,R4는 서로 겹치지 않는다. 점 (7, 3.5)는 겹치지 않고 서로 포함관계에 있는 3개의 Rectangle 안에 포함되고, 위와같은 조건을 만족하면서 더 많은 Rectangle 안에 포함되는 점을 찾을 수 없으므로 답은 3을 출력하면 된다. 그렇다면 답은 어떻게 구할 수 있을까?먼저 R1에 포함되는 최대 집함을 찾아보자.Ri의 집합의 크기를 Si라 두면,R1은 R2,R3,R4를 포함하므로 S1 = max(S2,S3,S4)..

codeground : 프리랜서 [SCPC 2016 - 2차 예선] https://www.codeground.org/practice/practiceProbView.do?probId=31 간단한 DP로 해결할 수 있다.일하는 데 일주일이 걸리는 P사의 각 주당 금액 을 Pi, 이주일이 걸리는 Q사의 각 주당 금액을 Qi라 하고, i번째 주에 받을 수 있는 가장 큰 금액을 Ai라 한다면, Ai = max(Ai-1+ Pi, Ai-2 + Qi) 위와같은 단 하나의 점화식으로 DP를 구성하면 가뿐하게 AC를 받을 수 있다.

codeground : 대피소 [SCPC 2016 - 1차 예선] https://www.codeground.org/practice/practiceProbView.do?probId=28 떠올릴 수 있는 가장 간단한 방법은 v번의 다익스트라를 하는 것. 하지만 이 방법은 간단히 시간초과임을 알 수 있다. 그렇다면 다른 해결방법이 있을까? 이 문제는 단 한번의 다익스트라로 해결이 가능하다.heap에 모든 대피소를 넣고 시작하면 된다. 또한, 경로의 길이가 같을 경우 대피소번호가 작은 대피소를 선택하는 것도 동시에 해결해주면 된다. 알고리즘을 간략히 써보면, 1. 새로운 경로가 더 작으면 힙에 push. dist 갱신 위에께 일반적인 다익스트라 알고리즘이라면, 이문제에 해당하는 알고리즘은 다음과 같다. 1. 새..

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번째 도시에 대해 다익스트라 알고리즘으로 모든 경로까지..