rhrnald's 코딩

https://www.acmicpc.net/problem/16329 16329번: Space Station The first line contains the number T, representing the number of tests. The first line that describes a test contains the three variables N M K. (1 ≤ N, M ≤ 1000) The following N–1 lines are of the form A B C (1 ≤ A ≤ B ≤ N; 0 ≤ C, K ≤ 106), meaning there www.acmicpc.net 신기한 방법으로 풀어 문제를 포스팅해봅니다. 증명을 못했는데 혹시 증명법이나 관련 정리를 알고 계시면 알려주시면 감사하..

기분 좋게 풀어서 포스팅 해보겠습니다. https://www.acmicpc.net/problem/8229 8229번: Fibonacci Representation The Fibonacci sequence is a sequence of integers, called Fibonacci numbers, defined as follows: Fib0=0, Fib1=1, Fibn=Fibn-2+Fibn-1 for n > 1 Its initial elements are: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ... Byteasar investigates representations of numbers www.acmicpc.net 특정 수 $n$이 주어졌을 때 $n$을 피보나치 수들의 합과 ..

위의 그림에서 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)개의 숫자를 직접 확인해보며 최솟값을 찾아주는 방법이다. 구간의 길이에 따라 달라지지만..

PS가 뭔지 잘 모르거나 처음 접하는 사람에게 나는 이 문제를 소개 시켜 주고 싶다. https://www.acmicpc.net/problem/8907 8907번: 네온 사인 문제 시흠이는 최근에 레스토랑 "삼각형"을 오픈했고, 시흠이는 레스토랑을 상징하는 네온 사인을 주문했다. 네온 사인은 총 N개의 꼭짓점이 원의 둘레를 따라 찍혀져 있다. 그리고, 총 N * (N-1) / 2개의 야광 튜브가 꼭짓점을 연결하고 있다. 야광 튜브는 두 가지 색(빨간색과 파란색)이 있다. 시흠이는 한 번에 한 삼각형만 불을 밝히려고 한다. 이때, 삼각형의 모든 변은 색상이 같아야 하고, 꼭짓점이 서로 이어져 있어야 한다. 그는 이러한 단색 삼각 www.acmicpc.net 굉장히 좋은 문제이다. 주관적이긴 하지만 좋은 문..