본문 바로가기

전체 글

segmented sieve 구간에서 체를 써야하는 상황일때 구간의 끝이 최대 $N$일때 우리는 $\sqrt{N}$까지의 소수만 보면 된다. (만약 합성수라면 항상 $\sqrt{N}$이하 인수를 갖는다.) 따라서 $\sqrt{N}$ 에테체 한번 하고, 소수 구하고 구간 $[L,R]$에서 체를 채울건데, 기억할만한 방법은 다음과 같다. for(ll p:primes){ for(ll j=max(p*p,(L+p-1)/p*p);j $p^2$ 미만 인수들이 지워짐, $L$ 이후 최초로 $p$의 배수인 수 중 최대를 잡으면 된다. 더보기
KMP 알고리즘 KMP(Knuth-Morris-Pratt Algorithm) 알고리즘은 어떤 한 문자열이 다른 문자열에 대해 연속 부분 문자열을 만족하는지를 판별할 수 있는 알고리즘이다. 찾을 문자열을 $P$, 원본 문자열을 $S$라 하자. 나이브하게 연속 부분 문자열을 판단하려고 하면 $O(|S||P|)$가 소요된다. KMP는 나이브한 접근을 시도하면서 선형시간에 탐색할 수 있게 하는 알고리즘이다. 예를 들어 아래와 같은 문자열을 탐색한다고 하자. 찾고자 하는 문자열 $P$를 ABABC, 원본 문자열 $S$를 ABABABC 라 하자. 나이브한 접근을 그대로 살려서 살펴보자 ABABABCABABC 까지 비교했을 때 4번째 문자가 서로 다르다. 기존에 나이브한 풀이는 위 과정 이후 $S$의 두번째 문자인 B부터 비교를 시.. 더보기
iterator를 가지는 container에서 다른 iterator로 접근하기 https://en.cppreference.com/w/cpp/iterator/prev.html BidirIt prev( BidirIt it, typename std::iterator_traits ::difference_type n = 1 ); (since C++11) (until C++17) template constexpr BidirIt prev( BidirIt it, typename std::iterator_traits ::difference_type n = 1 ); " data-og-host="en.cppreference.com" data-og-source-url="https://en.cppreference.com/w/cpp/iterator/prev.html" data-og-url="https://.. 더보기
2-SAT 판별 알고리즘 사전 지식절(clause): boolean 변수들이 or 연산으로만 묶여있는 것 CNF(Conjunctive Normal Form): 절들이 and 연산으로 묶여있는 것 2-SAT(2-satisfiability problem, 충족가능성 문제)이란 어떤 CNF의 절들이 최대 두 변수로만 이루어져있을 때 CNF가 true를 만족할 수 있는지를 판별하는 문제다. k가 3 이상인 k-SAT(변수 개수가 k개)은 NP-hard이고 2-SAT은 선형시간 안에 해결할 수 있다. CNF가 참이 되려면 모든 절들이 참이어야 하고 2-SAT은 명제가 참이 되는 조건을 활용해 풀 수 있다. 어떤 절 $(x_1\lor x_2)$에 대해 $x_1$이 거짓이라면 $x_2$는 참이어야 $(x_1\lor x_2)$의 값이 1이 되.. 더보기
Small to Large Technique - 작은 집합에서 큰 집합으로 합치는 테크닉 Small to Large 기법은 크기가 $N$인 집합을 $O(NlogN)$에 합칠 수 있는 방법이다. https://www.acmicpc.net/problem/28277 위 문제에서 1번 연산에 의해 집합을 합치는 경우 나이브한 방법을 떠올리면 $O(NQ)$로 TLE을 받는다. 그래서 우리는 Small to Large 기법을 사용해야한다. 항상 집합의 원소들을 합할 때 작은 집합에서 큰 집합으로 합치게 되면 합쳐진 집합의 원소의 개수는 항상 2배 이상이 되고 최악의 경우 이 값은 집합 크기인 $N$에 도달할 것이다. 따라서 이 행동이 최대 $O(logN)$번 걸린다는 사실은 자명하다. 위 문제에서는 이 방법과 더불어 원소의 불필요한 이동을 방지하는 포인터들을 관리해주면 된다. 코드는 다음과 같다. #i.. 더보기
Mo's Algorithm Mo's Algorithm에 대해 알아보자. Mo's Algorithm은 범위를 평방분할해 구간 쿼리를 정렬하여 빠른 시간 내에 쿼리를 처리하는 알고리즘이다. 아래 문제를 보자. https://www.acmicpc.net/problem/13547 구간 내 서로 다른 수의 개수를 세야하므로 쿼리 구간 마다 수를 관리해주어야 할 것처럼 보인다. 그래서 가장 먼저 떠오르는 풀이는 $O(NM)$ 풀이이다. 이때 TLE를 피하기 위해 평방분할을 생각해보자. 전체 수열의 범위를 $\sqrt N$개의 블록으로 쪼개고 각 쿼리 구간이 속하는 마지막 블록을 오름차순으로 정렬해보자.(마지막 블록이 같다면 앞 블록이 증가하는 순서대로) 그리고 우리는 $O(NM)$ 풀이에서 포인터 $l,r$을 사용할 것이다. 구간 쿼리를 정.. 더보기
수열 C++ - 백준 7976 https://www.acmicpc.net/problem/7976 애드혹인줄 알았으나 아주 아름다운 문제였다. 처음에 구간 $1\leq i\leq n-k+1, [1+q\times k,(q+1)\times k)$의 패턴이 반복되기만 하면 된다는 것은 관찰하였지만 "어떤 패턴으로 만들어야 최소로 만들까?" 라는 곳에서 막혔다. 패턴이 반복되기만 하면 되므로 우리는 구간 $[1,k]$만 신경써주면 된다. $cnt[i][j]$를 $1\leq i\leq n-k+1$인 $i$에 대해 모든 $1\leq i+q\times k\leq n$ $\mod 2$ 값이 $j$인 것들의 개수라고 두자. $dp[i][j]$를 구간 $[1,i]$의 $\mod 2$ 값의 합을 $j$로 만들기 위한 바꿈 연산의 최솟값이라고 생각해보자. .. 더보기
자석 C++ - 백준 28303 https://www.acmicpc.net/problem/28303 처음 접한 유형의 문제에서 신선한 충격을 받았다. 처음에는 $|a_i-a_j|-k|i-j|$의 최대를 구하기 위해서 투포인터, 이분탐색, 심지어는 삼분탐색까지 생각했지만 결국 시간 내에 해결하지 못하였다. 절댓값을 벗겨보면 $O(N)$에 해결할 수 있다. i번째 칸에 N극 j번째 칸에 S극을 놓는다고 하자. (단, $j 그때의 변화량은 $a_i-a_j-ki+kj$ 이고, 이를 최대화하기 위해서는 $a_j-kj$를 최소화 해야한다. 그렇다면 우리는 $i\in [2,N]$인 i에 대해 최소인 $a_j-kj$를 찾으면 된다. $j>i$인 경우는 $j 코드는 다음과 같다. #include typedef long long ll;using name.. 더보기

티스토리툴바