나름 개발자의 IT블로그

inverse modulo $ax \equiv 1 \mod p$일 때 $x$를 inverse modulo(모듈러 역원)라고 한다. 하지만 언제나 존재하는 것은 아니다. 예를들어 $2x \equiv 1 \mod 4$일 때는 존재하지 않는다. $ax - py = 1$로 나타낼 수 있으니 $\gcd(a,p) = 1$인 경우에만 inverse modulo가 존재한다. $p$가 소수라면 $0 < a < p$에서 $\gcd(a,p) = 1$이니 언제나 존재할 것이다. 고차 합동 방정식 $x^2+1 \equiv 0 \mod m$을 보자. $m = 5$일 때 $x = 2, 3$인 해를 가진다. 그런데 $m = 3$일 때는 해를 가지지 않는다. 이처럼 고차 합동방정식은 $m$이 소수이더라도 해가 존재하지 않을 수 있다...

brainfuck(brainf**k, 브레인퍽) 브레인퍽 사용법 https://ko.wikipedia.org/wiki/%EB%B8%8C%EB%A0%88%EC%9D%B8%ED%8D%BD 브레인퍽 - 위키백과, 우리 모두의 백과사전 브레인퍽(Brainfuck)은 우어반 뮐러(Urban Müller)가 1993년 경에 만든 최소주의 컴퓨터 프로그래밍 언어이다. 이름에 포함된 fuck이 욕설이기 때문에, 정중한 표현을 위해서 때때로 Brainf*ck, Brainf***, 혹 ko.wikipedia.org 브레인퍽 온라인 컴파일러 https://www.ryugod.com/pages/ide/bf RyuGod www.ryugod.com 자체 개발 브레인퍽 컴파일러 https://github.com/riroan/bra..

예전부터 엘릭서 언어를 배워보고 싶었다. 이름이 예쁘기도 하고 함수형 프로그래밍 언어이기 때문이었는데 한국어 자료는 별로 없고 외국자료도 그렇게 많지 않았다. 지금은 아는 사람이 많지는 않겠지만 시간이 지나면 C, python같은 주류 언어가 될 수도 있을 것이다. 그럼 엘릭서 언어를 공부해보자! https://elixir-lang.org/install.html Installing Elixir Website for Elixir elixir-lang.org 우선 설치는 저 사이트에 가서 하자. 엘릭서는 파이썬같이 interactive 모드와 script 모드를 제공한다. 터미널에서 iex를 입력하면 interactive 모드를 시작한다. 또한 엘릭서의 확장자는 ex, exs이고 ex는 컴파일된 파일, ex..

합동 만약 $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$이 주어지고 각 수를 빨간색, 파란색, 색칠하지 않음 중 하나의 상태로 만들 때 빨간..