알고리즘 공부방

문제 oj.uz/problem/view/IOI20_plants 문제 보기 - 식물 비교 (IOI20_plants) :: oj.uz 문제 보기 - 식물 비교 (IOI20_plants) oj.uz 원 위에 0~N-1의 N개의 수가 배열되어 있는 순열 $A$가 있다. 이 때 $R_i$는 i번째 칸부터 오른쪽으로 연속한 $K-1$개의 수들 중 $A_i$보다 큰 수들의 개수로 정의된다. 수열 $R_i$와 쿼리 (x, y)가 Q개 주어질 때, 가능한 모든 $A_i$에서 $A_xA_y$를 만족하는지, 아니면 두 경우 모두 가능한지 판별해야 한다. 단, 주어지는 $R$는 대응되는 $A$가 적어도 하나 존재하는 수열로 주어진다. $K1; init(node*2, tl, mid); init(node*2+1, mid+1, t..

문제 https://www.acmicpc.net/problem/1507 어떤 그래프에서의 임의의 두 정점 간의 최단거리가 모두 주어졌을 때, 조건을 만족하며 간선의 개수를 최소화할 수 있는 그래프를 찾는 문제이다. 풀이 기본적인 풀이는 $N^2$ 개의 간선을 모두 생성한 후, 필요 없는 간선을 하나씩 지워 가며 문제를 해결한다. 그렇다면 과연, 필요 없는 정점을 어떻게 구할 수 있을까? u->v 의 간선을 삭제하기 위해서는 u->w->v 의 경로와의 거리와 비교해 볼 필요가 있다. 1) adj[u][v]v 의 간선을 삭제해서는 안된다. u->v 의 최단거리는 다른 경유점을 거쳐 가면 안됀다는 뜻이기 떄문이다. 2) adj[u][v]==adj[u][w]+adj[w][v] u->v 의 간선을 굳이 놔둘 필요..

플로이드-워셜 알고리즘은 그래프에서 모든 점들의 쌍 (u, v) 간의 최단거리를 다 구하는 알고리즘이다. 경유점을 다음과 같이 정의하자. u -> x1 -> x2 -> x3 -> x4 -> v 일때, x1, x2, x3, x4는 경유점. 즉, 어떤 경로에서 시작점과 끝점을 제외한 정점들을 의미한다. 이렇게 정의하고, DP 를 사용한다. k-1번째 루프에서는 1~k-1의 정점들만을 경유점으로 하는 최단경로들의 값을 dp 테이블에 저장한다. 이제, 새로운 정점 k가 들어왔다고 생각하자. 최단거리는 k를 경유점으로 포함하는가, 하지 않는가로 나뉘고, 이는 다음과 같은 점화식으로 표현할 수 있다. $dp[k][i][j]=min(dp[k-1][i][j], dp[k-1][i][k]+dp[k-1][k][j])$ 따라..