알고리즘 관련 썸네일형 리스트형 BOJ)13538 XOR 쿼리 문제: icpc.me/13538 5가지 종류의 쿼리를 처리하는 문제이다. 1번 쿼리를 x의 위치에 업데이트 시키는 새로운 세그먼트 트리를 생성한다고 가정하면 persistent segment tree 자료구조를 이용할 수 있다. 고로 1번 쿼리의 경우 트리의 개수 n을 증가시켜주면서 n번째 세그먼트 트리의 x의 위치에 업데이트 시켜준다. 이 방식으로 persistent segment tree를 구축시켜주면 3번 쿼리는 자연스럽게 n=n-k가 된다. 이제 2,4,5의 쿼리를 생각해보자 4번 쿼리의 경우 r번째 세그먼트 트리에서의 0~x의 sum에서 l-1번째 세그먼트 트리에서의 0~x의 sum을 빼줌으로서 처리가능하다. 5번 쿼리의 경우는 r번째 세그먼트 트리가 가지는 값에서 l-1번째 세그먼트 트리가 가.. 더보기 Persistent Segment Tree 먼저 시작하기 전에 .. -오늘 공부한 내용을 제 멍청한 머리가 기억하지 못할까봐 기록하는 개인용 글입니다. -해당 자료구조에 대하여 완벽하게 알고 적는 글이 아니기 때문에 Persistent segment tree를 공부하는 용도로는 좋지 못한 글이 될 확률이 높습니다.-BOJ 11932 문제를 풀기 위해 https://hongjun7.tistory.com/m/64와 http://blog.myungwoo.kr/100 를 많은 부분에서 참고하였습니다. persistent segment tree가 뭔지는 알고있었지만 귀찮아서 공부를 미루다가 오늘 BOJ 11932번을 접하고 도전하게 되었다. persistent segment tree는 가상의 N개의 세그먼트 트리를 O(NlogN)의 공간복잡도로 유지하는 .. 더보기 BOJ)1322 X와K 문제: icpc.me/1322 X가 정해져 있을 때 X+Y = X | Y 를 만족하는 Y는 2진수에서의 연산을 생각한다면 X가 0인 비트에만 1이 채워져있는 수일 것이다. 고로 K번째로 큰 Y를 찾는다면 K를 이진수로 표현하였을 때 1이 채워진 순서를 X에서 0인 부분에 순서대로 채운 수가 된다. 이는 투 포인터로 구해줄 수 있다. 12345678910111213141516#include #include using namespace std;typedef long long ll;ll x, y, k;int main() { scanf("%lld%lld", &x, &k); for (int i = 0, j = 0; j 더보기 BOJ)1837 암호제작 문제: icpc.me/1837 P가 너무 크기 때문에 K를 이용하여 답을 구해내야 한다. 우선 K이하의 소수를 에라토스테네스의 체를 이용하여 구해준 뒤 P가 해당 소수들 중 하나라도 나누어 떨어지는 수가 있다면 BAD를 출력하게 된다. 12345678910111213141516171819202122232425262728293031#include #include using namespace std;char a[110];int k, p[2000000];bool chk(const char *s, int p) { int ret = 0; for (int i = 0; s[i]; i++) ret = (ret * 10 + s[i] - '0') % p; return !ret ? true : false;}int main(.. 더보기 BOJ)14577 일기예보 문제:icpc.me/14577 4가지 종류의 질의가 들어오는 문제이다. 지역 수 가 N 질의의 수가 M일 때 N,M이 10만까지 들어오므로 적어도 질의 하나당 log 시간에 해결해줘야 한다. 결국 3,4번 질의를 로그시간에 답해줘야 하는데 구간에 대한 질의이므로 우선 세그먼트 트리를 생각해낼 수 있다. 하지만 좌표 자체에 업데이트를 할 경우 좌표의 범위부터가 감당이 안된다. 그렇기 때문에 우리는 한 지역에 쌓일 수 있는 눈의 양에 업데이트를 해야한다. 나올 수 있는 눈의 양은 3번 쿼리의 경우 2개 1,2번 쿼리의 경우 1개 일 뿐이니 최대 2*M개 뿐이기 때문이다. 말을 어렵게 표현했는데 우선 쿼리를 오프라인으로 처리할거다. 모든 쿼리를 받은 뒤에 해당 질의 때 마다 나올 수 있는 모든 눈의 양을 저장.. 더보기 BOJ)6850 Cows 문제: icpc.me/6850 말뚝들이 주어질 때 주어진 말뚝들을 이용하여 펜스를 쳐서 펜스 안에 넣을 수 있는 소의 최대 마리수를 출력하는 문제이다. 펜스를 쳐서 얻을 수 있는 최대 면적이 S라면 floor(S/50)을 출력하는 문제가 된다. 고로 우리는 최대 면적 S를 구하기 위하여 말뚝들로 얻을 수 있는 Convex hull을 구해낸 뒤 얻어 낸 볼록껍질의 넓이를 구해주면 된다. 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071#include #include #include #include using namesp.. 더보기 BOJ)2254 감옥 건설 문제: icpc.me/2254 점(Px,py)를 감싸는 볼록껍질이 최대 몇개까지 가능한지 묻는 문제이다. 기둥들로 Convex hull을 구해준 뒤 해당 껍질이 Px,Py를 감싸는지 ccw로 확인해준 뒤 해당 Convex hull을 이루는 요소들을 전부 지워 준 뒤 이를 반복하여 점(Px,Py)를 감싸는 껍질의 수를 구해준다. 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105#includ.. 더보기 BOJ)5670 휴대폰 자판 문제:icpc.me/5670 입력으로 들어오는 모든 문자열을 trie에 저장한 후 현재 확인중인 문자에서 다음 문자로 넘어가는 경로가 2 이상인 경우나 해당 지점에서 문자열이 끝나는 경우가 버튼을 눌러야 하는 경우이니 카운트를 증가시켜주어 return하는 쿼리를 구현하여 해결 가능하다. 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758#include #include #include #include #include using namespace std;struct trie { trie *go[26]; int gocnt; bool finished; trie() { go.. 더보기 제1종 스털링 수 원소의 개수가 N인 집합을 구분되지 않는 K개의 원순열로 분할하는 방법의 수이다. 이를 D[N][K]로 정의하면 D[N][K]=D[N-1][K-1]+(N-1)*D[N-1][K] 라는 점화식을 얻을 수 있다. 관련 문제: https://www.acmicpc.net/problem/1413 더보기 Minimum Path cover in DAG DAG(Directed Acyclic Graph)에서 모든 정점을 커버하는 겹치지 않는 최소의 경로의 수를 구하는 문제 전체 정점의 수가 V 커버한 경로상의 간선이 X라면 V-X개의 경로로 커버할 수 있다. 따라서 X를 최대화 시켜야한다. 간선을 고를 때 제약 조건은 한 정점이 선택 될 때 오직 하나의 indegree와 오직 하나의 outdegree가 선택되어야 한다는 점이다. 즉, indegree와 outdegree가 최대한으로 매칭되어야 한다. 이를 이용하여 indegree를 상징하는 정점과 outdegree의 정점을 상징하는 정점으로 그래프를 구성하여 해당 그래프의 이분 매칭을 구함으로서 Minimum Path cover in DAG를 구할 수 있다. 참조: http://koosaga.com/ent.. 더보기 이전 1 ··· 9 10 11 12 13 14 15 ··· 34 다음