본문 바로가기

알고리즘

알고리즘/문자열 2020. 7. 21. KMP 대부분의 문자열 알고리즘은 어떤 문자열이 주어졌을 때, 이 부분 문자열 중 조건에 만족하는 특정한 문자열을 찾는 알고리즘입니다. 가장 단순하게, 문자열 \(S\)에서 문자열 \(T\)를 찾는 방법에 대해 알아봅시다. 문자열을 검색하는 가장 단순한 방법은, 이중 포문을 돌려 \(O(|S||T|)\)의 시간복잡도로 검색하는 것입니다. https://www.acmicpc.net/problem/1786 1786번: 찾기 첫째 줄에, T 중간에 P가 몇 번 나타나는지를 나타내는 음이 아닌 정수를 출력한다. 둘째 줄에는 P가 나타나는 위치를 차례대로 출력한다. 예컨대, T의 i～i+m-1번 문자와 P의 1～m번 문자가 차례로 � www.acmicpc.net 하지만 \(S\)와 \(T\)의 길이가 각각 최대 100만..
알고리즘/그래프 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]\)... 이와 같이 각 서브트리를 하나의 구간으로 바꿔 생각할 ..
알고리즘/DP 2020. 6. 7. 비트마스킹 DP 비트마스킹을 이용해 DP문제를 풀어봅시다. \(n\)크기의 집합이 있을 때, 이 집합의 서로 다른 부분집합의 개수는 \(2^n\)가지 입니다. 그리고 이 부분집합들을 하나의 정수로 쉽게 변환할 수 있습니다. 어떻게 하면 될까요? 5개의 원소를 가진 집합 \(S\)가 있다고 가정해봅시다. \(S = \{1,2,3,4,5\}\) \(S\)의 모든 부분집합에 대해서, 각 원소가 존재하지 않으면 \(0\), 존재하면 \(1\)을 차례대로 써 넣어봅시다. 그러면 서로 다른 5자리 이진수가 될 텐데, 이 수를 보통의 10진수로 변환하면 \([0,15]\)의 범위를 가지는 서로 다른 수로 변환됩니다. 원소의 수가 32개 이하라면 int범위에, 64개 이하라면 long long 범위에 저장할 수 있고, 만약 원소의 수..

티스토리툴바