본문 바로가기

알고리즘/그래프

알고리즘/그래프 2021. 10. 13. Centroid Decomposition Centroid Decomposition에 대해 알아봅시다. Centroid Decomposition을 이용하면 트리에서 분할정복을 사용할 수 있게 됩니다. https://anz1217.tistory.com/17 분할 정복 (Divide and Conquer) 분할 정복은 큰 문제를 분할하여 단순한 부분 문제로 만든 다음, 각 부분 문제의 답으로부터 전체 문제의 답을 이끌어내는 방식의 알고리즘입니다. 역시 분할 정복 자체만으로 풀 수 있는 문제 anz1217.tistory.com 위의 글에서 히스토그램에서 가장 큰 직사각형을 찾는 문제를 어떻게 풀었는지 다시 한 번 생각해봅시다. 히스토그램을 반으로 나눕니다. 그러면 답은 히스토그램의 왼쪽 절반, 오른쪽 절반, 또는 양쪽에 모두 걸쳐서 존재합니다. 한 절..
알고리즘/그래프 2021. 8. 25. HLD 트리의 경로에 관한 질의를 빠르게 처리할 수 있게 해주는, Heavy-Light Decomposition (HLD)에 대해 알아봅시다. 이전에 트리의 모든 서브트리를 하나의 구간으로 나타내게 해주는 Euler tour technique에 대한 글을 쓴 적이 있습니다. https://anz1217.tistory.com/41 Euler tour technique 트리를 펴서 배열에 저장해봅시다. 다음과 같은 트리가 있다고 가정해봅시다. 1번 정점이 루트입니다. 이 트리에서 루트인 1번 정점부터 시작해 DFS를 돌립니다. 그리고 각 정점이 방문되는 순서 anz1217.tistory.com 이와 비슷하게 트리의 모든 경로도 HLD를 이용하면 몇 개의 구간으로 나눌 수 있고, 세그먼트 트리등의 자료구조를 사용할 ..
알고리즘/그래프 2020. 7. 14. Minimum Cost Maximum Flow 만약 그래프의 간선에 비용과 용량이 모두 존재하면 어떨까요? 간선에 1의 용량을 흘릴 때마다 그 간선에 주어진 비용이 드는 그래프를 생각할 수 있습니다. 용량과 비용이 있는 방향그래프에서, 시작점 \(S\)에서 끝점 \(T\)까지 흐를 수 있는 최대 용량을 구하되, 그 때의 비용을 최소로 만드는 문제를 MCMF(Minimum Cost Maximum Flow) 문제라고 합니다. 예를 들어 다음과 같은 그래프에서, 최대 유량은 60, 그 때의 최소 비용은 210이고, 실해는 다음과 같습니다. https://www.acmicpc.net/problem/11408 11408번: 열혈강호 5 강호네 회사에는 직원이 N명이 있고, 해야 할 일이 M개가 있다. 직원은 1번부터 N번까지 번호가 매겨져 있고, 일은 1번부..
알고리즘/그래프 2020. 7. 10. 네트워크 유량 그래프의 간선에 '용량'이라는 개념을 추가해 봅시다. 지금까지 많이 봐왔던 '비용'의 개념과는 조금 다릅니다. 어떤 간선 \(e\)가 30의 용량을 가지고 있다면, 최대 30의 유량이 흐를 수 있음을 말합니다. 용량이 있는 방향그래프에서, 시작점 \(S\)에서 끝점 \(T\)까지 흐를 수 있는 최대 유량(Maximum Flow)가 얼마인지 구하는 문제를 네트워크 유량 문제라고 합니다. 예를 들어 다음과 같은 그래프에서, 최대 유량은 60이고, 실해는 다음과 같습니다. 다양한 문제들을 유량 문제로 변환해 풀 수 있습니다. 예를 들어 이전 글에 썼던 이분 매칭의 경우, 다음과 같은 방식으로 변환하면 유량 문제로 바꿔서 풀 수도 있습니다. https://www.acmicpc.net/problem/11378 1..
알고리즘/그래프 2020. 7. 7. 이분 매칭 정점을 두 개의 그룹으로 나누었을 때, 모든 간선의 끝점 두 개가 서로 다른 그룹에 속하게 만들 수 있는 그래프를 이분 그래프(Bipartite Graph)라고 합니다. 이분 그래프에서 간선들을 선택해 봅시다. 단, 모든 정점은 선택한 간선 중 단 하나의 간선에만 포함될 수 있습니다. 이 때 선택할 수 있는 간선(매칭)의 최대 개수를 구하는 문제를 이분 매칭(Bipartite Matching) 문제라고 합니다. 예를 들어 다음과 같은 이분 그래프에서, 최대 매칭은 4이고, 실해 중 하나는 다음과 같습니다. https://www.acmicpc.net/problem/11375 11375번: 열혈강호 강호네 회사에는 직원이 N명이 있고, 해야할 일이 M개가 있다. 직원은 1번부터 N번까지 번호가 매겨져 있고,..
알고리즘/그래프 2020. 6. 22. Biconnected Component Biconnected Component (BCC)는 무방향 그래프에서, 다음 조건을 만족하는 정점의 부분집합을 말합니다. 1. 부분집합에서 어떤 정점 하나를 삭제하더라도, 남은 정점들은 서로 연결되어 있다. 2. 이 부분집합에 다른 정점들을 추가하더라도 1을 만족하지 않는다. (1번을 만족하는 최대 크기의 집합이다) 따라서 다음과 같은 무방향 그래프는, 다음과 같이 5개의 BCC로 분리됩니다. 그래프를 이와같이 BCC로 분리하여 하나의 BCC를 하나의 정점으로 대체하면 그래프를 트리로 나타낼 수 있게 됩니다. 일반적인 그래프를 트리로 바꾸고 나면 트리에만 사용할 수 있는 다양한 알고리즘을 사용할 수 있게 됩니다. SCC를 먼저 보신분들은 알겠지만, SCC와 개념이나 코드가 거의 동일합니다. SCC의 무방..
알고리즘/그래프 2020. 6. 18. Strongly Connected Component Strongly Connected Component (SCC)는 방향 그래프에서, 다음 조건을 만족하는 정점의 부분집합을 말합니다. 1. 부분집합에서 어떻게 두 정점 \(u,v\)를 선택하더라도 \(u\)에서 \(v\)로 가는 경로가 존재한다. 2. 부분집합에 속한 정점 \(u\)와 그렇지 않은 정점 \(v\)에 대해서, \(u\)에서 \(v\)로 가는 경로와 \(v\)에서 \(u\)로 가는 경로가 동시에 존재하지 않는다. 따라서 다음과 같은 방향 그래프는, 다음과 같이 4개의 SCC로 분할됩니다. 그래프를 이와같이 SCC로 분할하여 하나의 SCC를 하나의 정점으로 대체하면 그래프를 DAG로 나타낼 수 있게 됩니다. 일반적인 그래프를 DAG로 바꾸고 나면 위상정렬이나 DP등 다양한 작업을 할 수 있게 됩..
알고리즘/그래프 2020. 6. 15. Euler tour technique 트리를 펴서 배열에 저장해봅시다. 다음과 같은 트리가 있다고 가정해봅시다. 1번 정점이 루트입니다. 이 트리에서 루트인 1번 정점부터 시작해 DFS를 돌립니다. 그리고 각 정점이 방문되는 순서대로 번호를 다시 붙여줍시다. 그리고 새로 붙인 번호를 인덱스로 하는 배열에 각 정점을 저장합시다. 그러면 트리를 배열에 저장할 수 있게 됩니다. 방법은 매우 간단한데, 굳이 이런식으로 저장을 하는 이유가 뭘까요? 이런 식으로 트리를 저장하면, 각 정점을 루트로 하는 서브트리가 모두 하나의 구간으로 나타나게 됩니다. 1번 정점의 서브트리는 구간 \([1,7]\), 2번 정점의 서브트리는 구간 \([2,5]\), 3번 정점의 서브트리는 구간 \([6,6]\)... 이와 같이 각 서브트리를 하나의 구간으로 바꿔 생각할 ..

티스토리툴바