1. The Postman경로에 대한 조건이 없을 때 이 문제는 방향 그래프에서 오일러 회로를 찾는 잘 알려진 문제이다. 오일러 회로는 모든 정점의 indegree와 outdegree가 같으며, 연결되어 있는 그래프라면 항상 존재한다. 이 문제의 그래프가 그러함을 가정하자 (그렇지 않다면 NIE).오일러 회로는 다음과 같은 재귀 함수 Rec(v) 로 선형 시간에 찾을 수 있다. 오일러 회로에 대해서는 복습을 위해 알고리즘만 간략히 적어두고 설명하지는 않겠다. * 정점 v에서 나가는 에지 e를 아무거나 찾고 제거 (사용한 에지들의 인덱스를 전역 변수 등에다 마킹해 놓고, vector에서 pop_back() 하면서 에지를 지워주자) * e의 반대편 끝점이 w라면, Rec(w) 호출 * Rec(w)가 종료되면..
1. 작은 새각각의 쿼리가 그다지 연관성이 없어보이니, 그냥 K가 고정됐다 치고 각 문제를 독립적으로 풀어보자. 결국 쿼리당 O(n)에 해결하면 되니 말이다. O(n^2) 동적 계획법은 다음과 같이 어렵지 않게 할 수 있다. dp(i) = 1번에서 i로 오는 데 필요한 최소의 힘든 점프 수라 하면, 그 전 위치를 j라 했을 때에 대한 식으로 동적 계획법 표를 채울 수 있다. 기본적으로 dp(j)를 가져올 수 있지만, 만약 H_j Ei라는 것은, 어떠한 시간에 Si에 있다가, 그 후에 Ei에 있고, 그 다음에 Si에 다시 돌아와야 한다는 것을 뜻한다. 그렇다면, 최소 Ei -> Si로 한번은 거꾸로 가는 것이 필요하다는 것을 뜻한다. (거꾸로 간다는 것은 돌아온다는 것을 함의한다.) 이들을 [Ei, Si]..
1. 레이저원점을 지나는 직선이 해당 선분을 맞추려면 기울기가 어떠한 수의 구간 사이에 있어야 한다. 그러니 2차원 평면에 직선을 쏴서 선분을 맞춘다고 생각하지 말고, 수직선에 구간이 있는데 점을 몇 개 넣어서 구간들을 덮는다고 생각해보자. 모든 점들이 1사분면 위에 있고 x/y축에 닿지도 않기 때문에, 각 구간은 어떠한 분수와 분수 사이의 폐구간으로 쉽게 표현할 수 있다. 하지만, 더 간단하게 분수가 아닌 정수로 생각해 줄 수도 있다. 각 분수의 정확한 값이 아닌 대소 관계만이 중요하기 때문이다. 고로 좌표 압축을 통해 분수를 적당한 0 - 2n-1 사이의 정수로 바꿀 수 있다. 이제, 0 ~ 2n-1 사이의 정수를 시작점 끝점으로 가지는 n개의 폐구간이 있을 때, k개의 실수를 골라서 최대의 구간을 ..
- Total
- Today
- Yesterday