나름 개발자의 IT블로그

합동 만약 $m | a-b$라면 $a \equiv b \mod m$이다. 꽤 심플한 정의이다. "$a,b$을 $m$으로 나눈 나머지가 같다"라고도 표현할 수 있다. 예를들어 $5 \equiv 12 \mod 7$이다. 특히 $m=2$라면 짝홀을 구분할 수 있다. 그리고 $0 \le a < m$이고 $a \equiv b \mod m$이면 $b = a+mk (k \in \mathbb{Z})$라고 나타낼 수 있다. 1차 합동방정식 $ax \equiv b \mod m$꼴의 방정식을 1차 합동방정식이라고 한다. 실수세계에서는 단순히 양변을 나눔으로써 해결할 수 있었다. 정수세계에서는 $(\mathbb{Z}, /)$이 이항연산이 아니기 때문에(현대대수 참고) 양변을 나눌 수 없다. 우선 합동방정식을 해결하는 가장 편..

엄랭 레포 https://github.com/rycont/umjunsik-lang GitHub - rycont/umjunsik-lang: 어떻게 엄준식이 언어이름이냐🤣 어떻게 엄준식이 언어이름이냐🤣. Contribute to rycont/umjunsik-lang development by creating an account on GitHub. github.com 엄랭 온라인 컴파일러 https://www.ryugod.com/pages/ide/umm RyuGod www.ryugod.com 엄랭은 요즘 떠오르는 취업 필수 언어다. 여기저기서 엄랭을 공부하고 네카라쿠배에 취업했다는 소식을 심심찮게 들을 수 있다. 한번 학습해보자! 위 레포에 들어가면 기본적인 사용법이 써져 있다. 구조가 다음과 같다. 어떻게 ..

디오판투스 방정식 이름이 거창해보이지만 내용은 정수 계수 부정 방정식이다. 예를 들면 $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?] 배열에서 연속한 두 원소의..