나름 개발자의 IT블로그

디오판투스 방정식 이름이 거창해보이지만 내용은 정수 계수 부정 방정식이다. 예를 들면 $3x+2y=5$ 이런 것이다. 지난시간에 $ax+by=c$가 정수 해를 가지려면 $\gcd(a,b) | c$를 만족해야 한다고 했다. 이를 이용하여 다양한 작업을 해보자. >> Theorem) 소수 $p$에 대해서 $p | ab$ 이면 $p|a$이거나 $p|b$이다. proof case 1) $p | a$ 자명히 성립한다. case 2) $ p \nmid a$ $p$는 소수이므로 $\gcd(a,p) = 1$ 그럼 유클리드 알고리즘에 의해 $ax + py = 1 (=\gcd(a,p))$를 만들 수 있다. 위 식은 해를 가지고 양변에 $b$를 곱하면 $abx + bpy = b$가 된다. $p | abx$이고 $p | bp..

기초부터 되짚어보자. 1. $m \mid n$ : m은 n을 나눈다. 2. $\gcd (a,b)$ : a,b의 최대공약수 3. 소수는 $1$과 자기 자신만으로 나누어 떨어지는 수 4. 나머지정리 : $a = qb + r$ $(0 \le r < b)$ 유클리드 호제법 $\gcd (a,b)$를 쉽고 빠르게(?) 구하는 방법이다. $a_1 = a, a_2 = b$라고 하자. 나머지 정리에 따르면 $a_1 = q_1a_2 + a_3$ $a_2 = q_2a_3 + a_4$ $\dots$ $a_n = q_na_{n+1}$ 같이 언젠가 나머지가 없어지는 때가 온다. 이때 $a_{n+1} = \gcd (a,b)$이다. $2a_{i+2} \le a_{i} $이기 때문에 $log$시간 안에 구할 수 있다. 예를들어 $\g..

학교에서 수학과의 정수론(학교에서의 과목이름은 수론)과목이 전공 인정이 되어 이번에 수강하게 되었다. 시험정리도 하고 알고리즘 정수론 태그 공부도 할 겸해서 포스팅을 하려고 한다. 피타고라스 정리 $a^2 + b^2 = c^2 (a,b,c \in \mathbb{R})$ 위 식은 잘 알려져 있다. 여기서 $(a,b,c) \in \mathbb{N}$으로 범위를 좁혀서 생각해보자. 피타고라스 정리에서 양변을 $c^2$로 나누면 식이 다음과 같이 된다. $\frac{a^2}{c^2} + \frac{b^2}{c^2} = 1$ 이는 단위원 $x^2 + y^2 = 1$에서 $x = \frac{a}{c}, y= \frac{b}{c}$인 점을 나타낸다. 여기서 $x,y$는 유리수가 나오므로 피타고라스 세 쌍은 단위원에서..

C까지 30~40분 안에 풀면 블루 갈 수 있을거 같다. (최대한 틀리지 않고) D부터는 너무 벽이 느껴진다.. A - Game [Solved!] 1인 땅은 밟을 수 있고 0인 땅은 밟을 수 없다. 인접한 땅은 무료로 여러번 이동할 수 있고 그렇지 않은 경우 1회에 한해 $x$코인을 소비하여 $x$만큼 건너 뛸 수 있다. 이때 처음부터 끝까지 가는데 드는 코인의 최솟값을 구하는 문제이다. 0이 없으면 0원, 아니면 가장 왼쪽에서 처음나오는 0의 위치를 가장 오른쪽에서 처음 나오는 0의 위치에서 빼고 1을 더한값이 답이된다. (여론이 안좋은 문제) B - Game of Ball Passing [Solved!] $a_i$를 $i$번째 선수가 패스를 하는 횟수라고 할 때 모든 선수가 패스를 하려면 몇번의 경기..

요즘 빠른 3솔을 목표로 하고 있는데 이번은 C에서 너무 막혔다. A - Square Counting [Solved!] $n+1$개의 수 $a_1, a_2, ..., a_n, a_{n+1}$이 주어질 때 $0\le a_i < n$이거나 $a_i = n^2$을 만족한다. 그리고 $\sum_{i=1}^{n+1} a_i = s$를 만족하는 $a_i = n^2$의 개수를 구하는 문제이다. $s$에 $n^2$을 최대한 많이 넣으면 된다. 이를 구하려면 $\lfloor \frac{s}{n^2} \rfloor$을 계산하면 된다. B - Quality vs Quantity [Solved!] 수열 $a_1, a_2, \dots, a_n$이 주어지고 각 수를 빨간색, 파란색, 색칠하지 않음 중 하나의 상태로 만들 때 빨간..

백준에 순열 사이클 분할(permutation cycle decomposition)이라는 태그가 있어서 공부를 하게 되었다. 기본적인 개념은 다음과 같다. 어떤 순열 $(a_1, a_2, \dots , a_n)$이 있으면 $a_i = f(i)$인 함수가 있다고 생각해보자. $f^2(i) = f(f(i))$라고 할 때 $i = f^k(i)$인 $1 \le k \le n$을 찾을 수 있다. 그럼 $k$번 연산하는 과정에서 나온 수들을 모으면 $(f(i), f^2(i), \dots, f^k(i))$가 나올 것이고 이것을 하나의 순열 사이클이라고 한다. 순열 사이클 안에 존재하는 원소들은 모두 같은 순열 사이클이 될 것이다. 모든 원소에 대해 수행하면 여러개의 순열 사이클이 나오는데 이를 구하는 것을 순열 사이..

이번에 4솔을 하여 민트로 복구할 수 있었다. 코드포스가 있던날 백준, 앳코더도 함께 진행해서 좀 힘든하루였다.(백준 4시간, 앳코더 1시간, 코드포스 2시간..) A - Min Or Sum [Solved!] 배열 $a$에서 서로 다른 원소 $a_i, a_j$를 뽑아 $a_i|a_j = x|y$를 만족하면서 $a_i = x, a_j = y$인 연산을 반복할 때 가능한 배열의 합의 최솟값을 찾는 문제이다. $x = a_i|a_j, y = 0$으로 두면 위 조건을 만족한다. 이 연산을 반복해서 하나의 원소에 적용하면 결국 배열은 $a_1|a_2| \dots | a_n, 0,0, \dots , 0$모양이 될 것이다. 이 때가 최소가 된다. B - Avoid Local Maximums [Solved!] 배열의 ..

민트를 복구할 수 있는 기회였는데 아쉽게 실패하고 말았다. 3솔에 블루퍼포가 나와서 싱글벙글하고 있었는데 B가 TLE로 터져버렸다. 알고보니 sys.stdin.readline을 쓰지 않아 생긴 문제였다. C문제도 같은 이유로 프리테스트에서 TLE가 발생했지만 B에서도 나올줄은 전혀 몰랐다. (두 문제 모두 $O(n)$으로 해결했었다.) 앞으로는 확인을 꼼꼼히 해야겠다. (후에 라인 추가로 AC받긴 했다.) A - Reverse [Solved!] 배열의 중간 일부 구간을 뒤집었을 때 사전순으로 가장 앞서는 배열을 출력하는 문제이다. 인덱스와 배열값이 다른 부분이 나오는 곳부터 그 이후에 나오는 최솟값이 있는 곳까지 뒤집으면 된다. B - Odd Swap Sort [Solved?] 배열에서 연속한 두 원소의..

이번에 본대회를 참가할 수 없어서 버추얼에 참가했다. A - Sorting Parts [Solved!] 길이가 $n$인 배열이 주어질 때 $1\le i\le n-1$를 정해 $[a_1,\dots,a_i], [a_{i+1},\dots,a_n]$를 정렬하여 이어붙일 때 내림차순이 아닌 배열을 만들 수 없는지 묻는 문제이다. (오름차순이 아닌 배열을 만들 수 있는지 묻는 문제) 주어진 배열이 이미 오름차순이라면 내림차순이 아닌 배열(오름차순)을 만들 수 있다. B - MEX and Array [Solved!] 배열을 $k$개의 구간으로 적당히 나누어 $ cost = c+\sum_{i=1}^c mex(\{ b_{l_i}, b_{l_{i+1}}, \dots, b_{r_i}\}) $ 라고 하자. 배열의 모든 부분배..

이번 코드포스의 결과는 굉장히 참담했다. 그래서 다시 그린으로 내려왔다. A - Reverse and Concatenate [Solved!] 문자열이 주어졌을 때 다음 연산을 $k$번 하여 만들 수 있는 서로 다른 문자열의 수를 구하는 문제이다. 연산은 다음중 하나를 수행한다. - 문자열을 뒤집어 원래 문자열 앞에 이어 붙인다. - 문자열을 뒤집어 원래 문자열 뒤에 이어 붙인다. 우선 연산을 한 번이라도 수행하면 문자열은 팰린드롬이 된다. 또한 팰린드롬은 뒤집어서 어디에 이어 붙여도 같은 문자열이 된다. 결국 주어진 문자열이 팰린드롬인지 확인하는 문제로 환원된다. 다만 팰린드롬에 상관없이 $k=0$일 때는 답이 1이다. A번부터 뇌절을 심하게 해서 4번틀리고 AC를 받았다. (발상이 상당히 힘들었다.) ..