알고리즘 공부방

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])$ 따라..

SPFA 는 벨만 포드 알고리즘의 확장 알고리즘이다. 벨만 포드에서 1 단계의 완화를 시킬때, 간선들을 임의로 골라서 완화시켰기 때문에 비효율적인 면이 있었다. 어떠한 정점의 최단거리가 감소하지 않았다면, 그 정점에서 시작하는 간선들을 완화시키는 것은 의미가 없다. 이를 이용하면, 어떠한 정점이 완화되어 최단거리가 바뀌었다면, 그 정점으로부터 시작하는 간선들만 완화해주면 된다. 이는 BFS 와 비슷하게 큐를 이용하여 구현할 수 있다. 처음에 시작점을 큐에 넣어논 후, 그 정점으로부터 완화를 시키고, 또 성공적으로 완화된 정점들에 대해서 다시 큐에 넣어준다. 이 방법도 벨만포드와 마찬가지로 $O(VE)$ 이다. 하지만, 만약 어떤 정점 v가 이미 큐에 들어가 있고, 아직 큐에서 나오지 않은 상태인데, 지금..

벨만-포드 알고리즘은 다익스트라 알고리즘과는 다른 방법으로 그래프에서의 단일 시작점에서의 최단 거리를 구하는 알고리즘이다. 다익스트라 알고리즘은 $O(ElogV)$의 매우 빠른 시간복잡도를 갖고 있지만, 음수간선에 대해 최단거리를 구하지 못한다는 단점이 있다. 벨만-포드 알고리즘은 이를 보완하여 음수 간선에 대해서도 최단거리를 구할 수 있게 해 준다. 기본적으로, 그래프에서 각 간선을 "완화"하는 작업을 반복한 후, 이러한 과정을 적질히 계속하여 결국은 모든 노드에 대해 최단 거리를 구해 낸다. 일단, 모든 간선에 대해 이와 같은 성질이 성립한다. u에서 v로의 간선 w가 존재한다면, $dist[v]dist[u]+w$ 라면 $dist[v]=dist[u]+w$ 로 조금 더 작게 만들어 줄 수 있다. 이를 ..

다익스트라 알고리즘은 그래프에서의 최단 거리를 구하는 알고리즘이다. 기본적으로 너비 우선 탐색과 비슷한 방법으로 작동한다. 사실, 너비 우선 탐색은 다익스트라에서 모든 간선의 길이가 1인 특수한 경우라고 봐도 된다. 다익스트라 알고리즘은 하나의 시작점으로부터 다른 모든 정점까지의 최단경로를 계산한다. 여기선 너비우선탐색과는 다르게, 지금까지 큐에 넣은, 우선순위 큐(Priority Queue를 이용하여) 방문할 정점들 중 가장 거리가 짧은 정점을 골라 그곳을 방문한다. 여기서 중요한 점은 bfs에서는 vis check 를 큐에 넣기 직전, 즉 실제로는 방문하지 않았지만, 발견 되었고, 곧 방문할 정점에 표시해 준다. 즉, 큐에 한번이라도 들어가기 위해선 vis check 를 해줘야 다른 정점이 이 정점을..

문제 https://oj.uz/problem/view/JOI14_scarecrows 문제 보기 - 허수아비 (JOI14_scarecrows) :: oj.uz JOI 마을에 있는 넓은 황무지에는 $N$명의 신성한 허수아비가 서 있어, 주민들은 일 년에 몇 번씩 허수아비를 둘러싸고 축제를 하고 있었습니다. JOI 마을의 촌장은 "허수아비들의 말씀을 들었다"고 주장하며 황무지에 밭을 하나 만들 계획을 세웠습니다. 허수아비들의 말에 따르면 밭은 다음 조건을 충족해야 한다고 합니다. 각 변이 동서 방향 또는 남북 방향으로 놓인 직사각형이어야 합니다. 남서쪽의 꼭짓점과 북동쪽의 꼭짓점에는 허수아비가 서 있어야 합니다. oj.uz 평면 상에 N개의 점들이 주어져 있을때 다음 조건을 만족하는 점들의 순서쌍의 수를 세는..

문제 https://www.acmicpc.net/problem/7626 직사각형 여러개가 주어졌을 때, 그 합집합의 넓이를 구하는 문제이다. 풀이 이 문제에 대한 풀이는 https://codedoc.tistory.com/421 에 매우 자세히 나와 있다. 직사각형들의 x좌표에 대해 직사각형의 왼쪽 변은 +1, 오른쪽 변은 -1을 해주는 이벤트로 생각할 수 있다. 따라서 그러한 이벤트들을 모두 x좌표에 대해 정리한 후 오른쪽으로 쭉 한번 훑어주면서 넓이를 구할 수 있다. 이제 잘 나눈 x좌표들에 대한 구간으로 그 구간 사이의 넓이만 구해주면 된다. x좌표들에 대한 이벤트로 정렬을 때린 후 구간을 나눴으니, 하나의 구간 내에선 구해야 하는 영역의 넓이는 변하지 않는다. 따라서 이벤트들을 잘 관리해주는 자료구..