알고리즘 공부방

문제 https://oj.uz/problem/view/IOI19_split 문제 보기 - Split the Attractions (IOI19_split) :: oj.uz 문제 보기 - Split the Attractions (IOI19_split) oj.uz 연결된 무방향 그래프가 하나 주어졌을 때 정점들을 $A$, $B$, $C$ 세 개의 집합으로 분리해야 한다. 조건은 $A$, $B$, $C$의 각 집합의 크기는 이미 정해져 있고, 세 집합들 중 적어도 두개는 하나의 커넥티드 컴포넌트를 이루어야 한다. ($N

https://www.ioi-jp.org/joi/2017/2018-ho/index.htmlhttps://oj.uz/problems/source/307 1, 2번까지는 무난하게 풀 수 있었고, 3, 4번을 푸는데 내 힘으로 풀지 못하고 여러 블로그들과 공식 풀이를 보며 풀어 이틀이 걸렸다. 5번 문제는 공식 풀이 슬라이드를 봐도 도무지 이해가 안가 나중에 다시 풀어봐야 할 것 같다. 이번 셋을 풀면서 느낀 점은 DP의 중요성과, 그래프 문제들은 역시 관찰과 연습만이 답인 것 같다. 또한, 역시 JOI 문제들은 문제의 질과 수준 모두 매우 좋은 것 같다. 1. stove 만약 K번 킬 수 있다면 각 난로를 켜야하는 시간에만 켜놓으면 된다. 그럼, 그 이하라면 어떻게 해야 할까?전체 구간을 기준으로 난로를 켜..

2-SAT 문제는 다음과 같다. (a or b) 꼴의 식 여러 개를 and 연산으로 연립한 것이다. 이때 각 a, b, c 변수는 true, false 를 값으로 하는 변수이다. 각 변수에는 not 을 붙일 수 있다. 이 문제는 변수들 간의 방향 그래프로 모델링 한 후, SCC를 사용하여 해를 구할 수 있다. 첫 번째로, 각 항의 (a or b)는 모두 true 가 되어야 한다. 이제 하나의 항만 생각해 보자. (a or b) 가 성립하기 위해서는 a가 false이면 b가 true / b가 false이면 a가 true 여야 한다. 이를 명제로 표현하면 !a -> b , !b -> a 이다. 이 명제들이 모두 성립한다면 (a or b) 가 성립한다. 이제, 모든 항들을 2개의 명제로 바꾸었다. 항의 개수가..

SCC란, 방향 그래프에서 정의되는 개념으로, 한 SCC 내부에서 임의의 정점 u, v를 잡았을 때, u에서 v가 도달 가능한 컴포넌트를 의미한다. 한 그래프에는 여러개의 SCC가 존재할 수 있고, 이러한 SCC들을 분리해 내고 그 SCC들을 하나의 정점처럼 합쳐 주면 압축된 새로운 그래프를 얻을 수 있다. 이 그래프는 무조건 DAG 이고, 이를 이용하여 많은 문제들을 풀수 있다. ( 압축된 정점 들 간의 사이클이 존재하면 임의의 한 압축정점에서 다른 정점으로 양방향경로가 존재하니, 그 압축정점들 또한 하나의 SCC로 뭉쳐져야 한다. ) SCC는 $O(N+M)$ 안에 추출할 수 있고, Tarjan과 Kosaraju 두 방법이 있다. 1. Tarjan's Algorithm 타잔의 알고리즘은 기본적으로 그래..

문제 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 의 간선을 굳이 놔둘 필요..

위상정렬은 주어진 유향 그래프를 일정한 순서로 배치하였을때, 모든 간선이 오른쪽으로만 향하도록 하는 배치를 의미한다. 위상정렬을 하기 위해선 주어진 그래프에 사이클이 없음, 즉 DAG 여야 함이 보장되어야 한다. 위상정렬을 하는 방법은 크게 2가지 방법이 있다. SOL 1) 위상정렬에서 가장 먼저 오는 점은 indegree의 값이 무조건 0이라는 관찰을 해주면 된다. 각 정점에서의 indegree 값을 갖고 있고, indegree가 0인 정점을 큐에 넣어준 후, 그 정점과 연결된 간선들을 삭제해주는 과정을 반복하면 된다. 간선을 삭제하는 방법은 단순히 도착 정점의 indegree 를 감소시키면 된다. 만약 큐에 값이 2개 이상 들어가는 시간이 있으면, 위상정렬의 결과가 2개이상 가능한 것이고, 큐에 값이..

DFS를 돌면서 그래프의 간선을 4개의 종류로 분류할 수 있다. 1. 트리 간선 (Tree Edge) 트리 간선은, dfs 스패닝 트리 자체에 포함되는 간선을 의미한다. 간선의 확인은 u->v 에서 v가 아직 발견되지 않았다면 이 간선은 트리 간선에 포함된다. 2. 역방향 간선 (Back Edge) dfs 스패닝 트리에서 이미 자손에서 조상으로 향하는 간선을 의미한다. 위 그림에서 자손 D에서 조상 A로 향하는 간선을 보면, 아직 A를 종료하지 않은 상태에서 D가 A로 가려고 한다. 간선의 확인은 u->v 에서 v가 아직 종료되지 않았으면 이 간선은 역방향 간선에 포함된다. 역방향 간선의 존재는 사이클의 존재와 동치이다. 3. 순방향 간선 (Forward Edge) dfs 스패닝 트리에서 조상에서 자손으..

플로이드-워셜 알고리즘은 그래프에서 모든 점들의 쌍 (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])$ 따라..