나름 개발자의 IT블로그

지금까지 고속푸리에변환(이하 FFT)의 원리를 잘 모르고 썼는데 오늘 각잡고 공부해서 깨달았다. 아직 완벽히 이해한건 아닌것 같지만 잊어버리기 전에 남겨놓고자 한다. (쓰다보니 길어져서 파트를 나누었다. part1은 필요한 지식, part2에 FFT 원리에 대해 포스팅한다.) 감사한 곳 https://codeforces.com/blog/entry/43499 https://codeforces.com/blog/entry/43499 codeforces.com FFT는 다항식을 빠르게 계산하는 알고리즘이다. $A(x) = \sum_{i=0}^{n-1} a_ix^i, B(x) = \sum_{i=0}^{n-1} b_ix^i$일 때 $C(x)=A(x)B(x)$를 빠르게 구하는 알고리즘이다. 그냥 단순 알고리즘으로 구..

엘릭서의 여러가지 자료형들에 대해서 알아보자. 정수 엘릭서는 2, 8, 10, 16진수를 사용할 수 있다. a=10 b=0b1010 c=0o123 d=0x1af 또한 파이썬과 같이 숫자사이에 _를 넣어 자릿수를 구분할 수 있다. a=1_000_000 b=1_0_0_0 # 꼭 3자리 단위로 끊을 필요는 없다. 실수 다른 언어와 마찬가지로 과학표기법을 사용하여 나타낼 수 있다. a=1.0 b=5.6123 c=1.2e5 d=6.02e-23 아톰 재미있는 변수이다. 변수이름 자체가 값이 된다. 일종의 enum역할을 대신한다고 봐도 될 것 같다. 이제 방향을 정의할때 LEFT = 1, RIGHT = 2, UP = 3, DOWN = 4 같이 개발하던 기억은 안녕... 변수 앞에 :을 붙여서 정의한다. 특히 :tru..

패턴매칭 엘릭서는 = 연산자 부터 다르다. 지금까지 프로그래밍하면서 대입연산자로 사용했는데 엘릭서는 대입연산자로 쓰지 않고 패턴매칭이라는 개념으로 사용한다. 일종의 assert문이라고 한다. (사실 여기서부터 어질어질했다.) a=1 list = [1,2,3] 1=a 2=a [x,y,z] = [1,2,[3,4,5]] 파이썬에서 저 순서대로 실행시킨다면 3, 4번째 줄만 에러가 날 것이다. 하지만 엘릭서는 4번줄만 에러가 난다. =연산자가 하는 일이 대입이 아니라 좌변과 우변을 매칭하는 역할을 하기 때문이다. 여기에 두가지 성질이 있다. 1. 변수가 좌변에 있으면 우변의 값을 좌변에 대입한다. 2. 좌변과 우변을 매칭할 수 있는지 확인한다. 1번은 프로그래밍에서의 =연산, 2번은 수학에서의 =연산이라고 보면..

전설로만 존재하는 줄 알았던 div. 4가 열린다길래 다른 일 다 뒤로 하고 보러 왔다. 난이도는 백준 기준으로 브론즈 4 ~ 실버 2? 정도 되는 거 같다. 가장 비슷한 사람의 퍼포를 보니 1800 정도 나오는 거 같다. A - Division? [Solved!] 레이팅에 따라서 조건에 해당하는 Division을 출력하는 문제이다. if문을 빠르고 정확하게 타이핑하자! B - Triple [Solved!] 주어진 배열에서 같은 수가 3개 이상 나오는 수가 있는지 출력하는 문제이다. 파이썬 기준으로 Counter, dict, list 등을 사용해 배열에 존재하는 숫자의 개수를 세고 3개 이상이 있다면 출력하면 된다. C - Odd/Even Increments [Solved!] 배열이 주어질 때 다음 연산..

어렸을 때 이런 문제를 푼 기억이 있다. "사탕 $N$개를 나눠주는데 $a$개씩 나눠주면 $m_1$개가 남고 $b$개씩 나눠주면 $m_2$개가 남을 때 사탕의 수를 구하시오." 그때는 직접 대입하거나 식을 세워서 풀었던거 같은데 중국인의 나머지정리로도 풀 수 있다. 중국인의 나머지 정리(Chinese Remainder Theorem) >> Theorem) $\gcd(m,n) = 1$이고 $x \equiv b \mod m$이고 $x \equiv c \mod n$이면 $x \equiv d \mod mn$인 $d$가 유일하게 존재한다. proof $x \equiv b \mod m$은 $x = my + b$로 쓸 수 있고 이를 두번째 식에 대입하면 $my + b = nz + c$가 된다. 이는 곧 $my - n..

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 엄랭은 요즘 떠오르는 취업 필수 언어다. 여기저기서 엄랭을 공부하고 네카라쿠배에 취업했다는 소식을 심심찮게 들을 수 있다. 한번 학습해보자! 위 레포에 들어가면 기본적인 사용법이 써져 있다. 구조가 다음과 같다. 어떻게 ..