본문 바로가기

알고리즘 관련

L-R flow http://blog.myungwoo.kr/111 와 http://koosaga.com/134 에서 많은 부분 참고하였습니다. -간선에 lower_bound가 존재할 때 플로우를 흘릴 수 있는지 여부 확인 1. MCMF로 모델링 a->b로의 간선이 하한이 l 상한이 r일 때 a->b로 (l , -1) , (r-l ,0)으로 두가지 간선을 만들어 준 뒤 MCMF 를 돌린다면 항상 -1이 있는 쪽으로 플로우가 강제된다. 이 때 cost를 확인하여 플로우를 흘릴 수 있는 지 여부를 확인해준다. 이 때의 maxflow는 flow를 확인하여 구할 수 있다. 2. 디닉을 사용하는 방법 새로운 소스와 새로운 싱크를 만든다. 기존 싱크-> 기존 소스로 capacity가 INF인 간선을 생성한다. a->b로의 간선이 하.. 더보기
BOJ)8462 배열의 힘 문제: icpc.me/8462 시퀀스와 쿼리가 주어질 때 매 쿼리에 대한 답을 출력하는 문제이다. 쿼리는 구간이 주어지면 구간에 존재하는 모든 자연수 s에 대하여 (s 의 개수의 제곱) x s를 합한 값이다. 쿼리와 시퀀스가 10만이기 때문에 적어도 쿼리를 log나 root 시간에 처리해주고 싶지만 안타깝게도 저 쿼리를 해당 시간에 처리하기는 힘든거 같다. 하지만 쿼리 도중에 업데이트가 일어나지 않기 때문에 쿼리를 정렬한 뒤 mo's 알고리즘으로 접근한다면 해답을 얻을 수 있다. 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657#include #include usin.. 더보기
BOJ)3172 현주와 윤주의 재미있는 단어 게임 문제:icpc.me/3172 어떤 단어가 x가 어떤 단어 y보다 사전순으로 앞서 있으면서 y를 뒤집은 y'이 x를 뒤집은 x'보다 앞서 있다면 두 단어는 서로 좋아하지 않는다고 한다. 단어가 10만개이기 때문에 brute force로 접근한다면 시간초과를 면치 못할 것이다. 그렇기 때문에 생각을 바꾸어서 기존의 문자열 기준으로 정렬을하여 번호를 매겨준 뒤 그 번호를 가진 상태로 문자열을 다 뒤집은 후 정렬을 해주고 앞에서 부터 보면 나보다 먼저 본 문자열 중에 나보다 할당 된 번호가 큰 문자열의 수를 세주면 된다. 이는 세그먼트 트리나 펜윅 트로로 효율적으로 해결할 수 있다. 123456789101112131415161718192021222324252627282930313233343536373839#in.. 더보기
BOJ)14675 단절점과 단절선 문제:icpc.me/14675 트리에서 단절선인지 단절점인지 여부를 판단하는 쿼리를 처리하는 문제이다. 단절선 단절점을 직접 구해줄 필요 없이, 트리이기 때문에 모든 선은 단절선이 된다. 트리에서 단절점 여부는 리프를 제외한 모든 노드는 단절점이 된다. 트리에서 리프판단 여부는 indegree의 개수를 세주면 된다. 1234567891011121314151617181920#include #include using namespace std;int n, m, x, y, c[100010];int main() { scanf("%d", &n); for (int i = 0; i 더보기
BOJ)14426 접두사 찾기 문제: icpc.me/14426 N개의 문자열로 이루어진 집합 S가 주어질 때 M개의 문자열 중에서 집합 S에 포함 된 문자열 중 하나 이상의 접두사인 문자열들의 수를 출력하는 문제이다. 문자열의 길이가 짧음을 이용하여 트라이를 사용하여 문제를 해결 할 수 있다. N개의 문자열을 모두 트라이에 삽입해준 뒤 문자열 X에 대해 검색을 한다고 가정하면 X가 끝날 때 까지 트라이에서 계속 탐색이 가능하면 true를 중간에 경로가 없다면 false 를 return하도록 구현해주면 된다. 1234567891011121314151617181920212223242526272829303132333435363738394041424344#include #include using namespace std;int n, m;ch.. 더보기
BOJ)1938 통나무 옮기기 문제: icpc.me/1938 BFS를 이용하여 답을 구해줄 수 있다. 구현이 상당히 귀찮다 ... 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788899091929394#include #include #include using namespace std;struct ele { int x, y, z; ele(int x, int y, int z) :x(x), y(y), z(z) {} ele() {}};int dx[] = { 1,-1,0,0,0 };int dy[].. 더보기
BOJ)1445 일요일 아침의 데이트 문제: icpc.me/1445 꽃을 통과하는 경우를 최소로 하고 싶고 꽃을 통과하는 경우의 최소가 여러경로가 존재할 때 꽃의 옆을 지나가는 경우를 최소로 하고 싶을 때 최단경로를 찾는 문제이다. 우선이 되는 꽃을 통과하는 경우에 나올 수 있는 최대 꽃의 수 2500보다 큰값을 곱해서 cost를 주고 꽃의 옆을 지나가는 경우를 1로 준 뒤 다익스트라를 돌린 후 곱한 값을 나눈 값과 나머지를 출력해주면 된다. 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758#include #include #include #include using namespace std;int n,.. 더보기
BOJ)10256 돌연변이 문제: icpc.me/10256 N^3으로 만들 수 있는 모든 마커를 트라이에 넣어준 뒤 아호코라식을 통하여 몇개의 마커가 주어진 문자열에서 출연하는지 개수를 세주면 되는 문제이다. 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293#include #include #include using namespace std;struct trie { trie *go[4]; trie *fail; int out; trie() { for (int i = 0;.. 더보기
BOJ)9250 문자열 집합 판별 문제: icpc.me/9250 n개의 문자열 집합 a와 m개의 문자열 집합 b가 있을 때 b의 원소들을 확인하면서 a의 문자열이 하나라도 부분문자열으로 존재하는지 여부를 출력하는 문제이다. 일대 다 패턴매칭인 아호코라식을 이용하여 해결할 수 있다. 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182#include #include #include using namespace std;struct trie { trie *go[26]; trie *fail; bool out; trie() .. 더보기
BOJ)1063 킹 문제: icpc.me/1063 조건에 맞게 시뮬레이션을 돌려주면 된다. 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647#include #include #include #include using namespace std;string mov[] = { "R","L","B","T","RT","LT","RB","LB" };string a;int dx[] = { 0,0,-1,1,1,1,-1,-1 };int dy[] = { 1,-1,0,0,1,-1,1,-1 };int n, kx, ky, sx, sy;int chk(int x, int y) { return 1 > n; ky = x[0] - 'A' + 1; kx =.. 더보기

티스토리툴바