본문 바로가기

분류 전체보기63

Sqrt Decompositon(평방분할) & Mo's Algorithm BOJ8462) 배열의힘 먼저 이 문제를 살펴보자 * n개의 원소가 존재하고, [L,R] quer가 들어올 때 마다 부분 배열의 힘을 구하는 것이다. * 여기서 Ks라 하면 자연수 s의 개수를 뜻하는데, 부분배열에서 이 모든 자연수 s에 대해 Ks * Ks * s 를 구하는 것이다. => 나이브하게 모든 query에 대하여 다 훑어본다면 O(N^2)의 시간복잡도를 갖는다. 이 때 Sqrt decompostion을 적용해보자. Sqrt Decomposion이란? * 간단하게 N개의 집합을 sqrt(N)개의 집합으로 나누어 값을 다룬다고 생각하면 되는데, 이 문제에서는 query 에 적용하는 Query Sqrt Decompostion을 사용할 것이다. 또한 query에 대하여 분할 하는 것을 Mo's alg.. 2018. 4. 5.
문자열 해싱 String hash 함수일반적인 자료구조로서의 해쉬, 그중에서도 문자열을 어떤 양의 정수값으로 변환하는 해시 함수이다. (1) 좋은 해쉬함수의 조건- Determinism : 같은 수를 넣을 경우 해시함수는 항상 같은 값을 리턴해야 함. 즉 외부상황에 따라 값이 달라지지 않고, 순수 내부 로직으로 작동 - Uniformity : input을 집어 넣었을 때, 어떤 output이 나오는 해시 함수가 있다고 하자. 이 때 output range에 있는 각각의 값들이 나올 확률은 서로 대략적(roughly)으로 같아야 한다. 이것은 해시의 충돌 확률을 낮추기 위해서다. 충돌이 안 일어날 수록 좋은 해쉬 함수. - 결과값이 Bucket Size를 넘지 않도록 범위를 조정할 것. (2) String hash 함.. 2018. 3. 31.
Min Path Cover in DAG DAG(Directed Acyclic Graph)에서 모든 정점을 커버하는 겹치지 않는 최소의 경로의 수를 구하는 문제 전체 정점의 수가 N 커버한 경로상의 간선이 X라면 N-X개의 경로로 커버할 수 있다. 만약에 간선으로 커버가 되지 않았다면, 각 정점 하나가 경로가 될 것이다. 따라서 최대한 간선을 많이 선택하면 된다. 따라서 X를 최대화 시켜야한다. 간선을 고를 때 제약 조건은 한 정점이 선택 될 때 오직 하나의 indegree와 오직 하나의 outdegree가 선택되어야 한다는 점이다. 즉, indegree와 outdegree가 최대한으로 매칭되어야 한다. 이를 이용하여 indegree를 상징하는 정점과 outdegree의 정점을 상징하는 정점으로 그래프를 구성하여 해당 그래프의 이분 매칭을 구함.. 2018. 3. 31.
L-R flow : 하한이 있는 플로우 L-R flow L-R flow란? 네트워크 플로우에서 각 간선에 흐를 수 있는 용량이 정해져 있듯이무조건 흘러야 하는 하한이 정해지는 것이다. 이 하한을 어떻게 만족시켜야 할까? 또는 하한을 만족시키면서 유량을 흘릴 수 있는지 어떻게 검사할까? 만약 a->b 간선을 e 라고 할 때, 이 간선에 흘러야 하는 하한을 l, 상한을 r이라고 하자.또한 기존의 S,E 이외에 새로운 source 와 sink인 s,t 를 정의하자. 이떄 간선을 다음과 같이 구성하자 1. s -> b 로 cap = l 인 간선 (①에서 그래프에 하한인 l만 흐르게 하기 위함)2. a -> t 로 cap = l 인 간선 (①에서 그래프에 하한인 l만 흐르게 하기 위함)3. E -> S 로 cap = INF 인 간선 (①에서 S가 처음.. 2018. 3. 31.