rhrnald's 코딩

위의 그림에서 ABCDE를 채울 수 없다. 조건이 너무 부족하여, 위의 그림을 만족하는 예시 여러 개를 충분히 잡을 수 있기 때문이다. 하지만 신문이나 책에 올라와 있는 스도쿠 문제를 풀 경우에는 사용할 수 있는 추가 조건이 하나 있다. 답이 유일하게 결정 된다는 것이다. C가 7인 경우를 생각해보자. 집합 { A, B } = { 8, 9 }={ D, E }가 되어야 한다. 하지만 그렇게 될 경우 답이 유일하지 않게 된다. 순서쌍 (A, B, D, E)=(8, 9, 9, 8)가 해가 되면 (9, 8, 8, 9)도 해가 되며 반대도 마찬가지로 성립하기 때문이다. 따라서 C는 7일 수 없고 자연스럽게 A=8, B=9, C=9, D=7, E=8인 것을 알 수 있다. 스도쿠 자체의 규칙만 본다면 비양심적인 방법..

Suffix Array를 $O(n)$시간만에 구성하는 방법입니다. 해당 논문의 내용을 그대로 옮겨왔습니다. 길이 n인 문자열 $T$가 주어져 있을때(1-base index), Suffix Array는 두개의 배열로 구성되어 있습니다. 첫 번째는 $A_{T}$, sort array입니다. $T$의 suffix $S_{i}$를 $T[i]$에서 시작해서 $T[n]$에서 끝나는 부분문자열로 정의할 수 있습니다. 이 때 이 $A_{T}$는 suffix들을 lexicographic 순서로 정렬 하였을때, index들의 배열입니다. $\{S_{1}, \cdots, S_{n}\}$중 lexicographic 순서로 $i$번째로 작은 suffix를 $S_{j}$라 하면, $A_{T}[i]$에는 $j$가 저장됩니다. 두 ..

다음 세 문제를 살펴보자. 1. Constructing String Cost 문자들의 집합 $L_{1}$, $L_{2}$, ... $L_{n}$이 있다. 각 집합의 크기를 $S_{1}$, $S_{2}$, ... $S_{n}$이라 하자. ($|L_{i}|=S_{i}$) 이제 n자리 문자열을 만들건데 $i$번째 문자는 $L_{i}$에서 선택할 것이다. 총 $S_{1}\cdot S_{2}\cdots S_{n}$ 종류의 문자열이 나올 것이다. 이제 이 모든 문자열들을 찾는데 걸리는 비용을 계산해야 한다. 문자열집합의 곱을 다음과 같이 정의하자. 두 문자열집합 $X$와 $Y$에 대해 $X \cdot Y = \{ a \cdot b | a \in X, b \in Y\}$. 이 때 두 문자열의 곱은 단순히 연결하는 것..

수식과 코드 넣는 법을 찾았다. 앞으로 깔끔한 포스팅을 위해 노력해야겠다. $ F(n) = \sum_{i=1}^{n} \phi(n) $를 $ O(n^{2/3}) $에 구하는 방법이다. 수학적인 지식이 필요하지만 내용이 별로 어렵지 않다. $ \phi(n) $의 정의 : $1$~$n$ 중 $n$과 서로소인 수의 개수 $ \phi(n) = x (1-\frac{1}{p_{1}})(1-\frac{1}{p_{2}})\cdots (1-\frac{1}{p_{k}}) $ (단, $ p_{1}, ..., p_{k} $는 $n$의 서로 다른 소인수들) $F(n)$을 쉽게 계산하는 방법으로는 전부 계산해서 더해주는 방법이 있다. $\phi(n)$은 재귀적으로 빠른 시간 내에 계산해 줄 수 있어서 길게 잡아도 $O(n\log..

Range minimum은 배열이 주어져 있을 때, 연속한 구간의 최솟값을 구하는 것을 의미한다. 최솟값을 여러 구간에 대해 반복적으로 구하는것이 Range Minimum Query, 줄여서 RMQ라 부른다. 다양한 방법이 존재하여 PS를 처음 접하는 사람들이 한번 보고 넘어가기 좋은 내용인거 같다. 다음과 같은 노테이션을 사용하겠다. n : 배열의 길이 X[1~n] : 주어진 배열 q : 쿼리의 개수 xi, yi : i번째 쿼리, X[xi]~X[yi] 중 최소인 값 1. 단순한 방법 전처리 : 無 업데이트 : 無 query당 : O(n) 특이사항 : 초등학생도 짤 수 있음 그냥 전부 탐색해주는 방법. 매 번 (l-r)개의 숫자를 직접 확인해보며 최솟값을 찾아주는 방법이다. 구간의 길이에 따라 달라지지만..