1. 문제1 https://atcoder.jp/contests/abc341/tasks/abc341_d D - Only one of two AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online. atcoder.jp 2. 풀이 n,m,k가 주어지는데 n이나 m중 어느 하나만으로 나누어 떨어지는 정수들을 오름차순 정렬할때, k번째로 작은 양의 정수를 찾는 문제 예를 들어 n = 2, m = 3, k = 5이면 2,3,4,8,9,10,...은 각각 2나 3중 어느 하나만으로 나누어 떨어지는 정수들이다. 4는 2로 나누어 떨어지지만 3으로 나누어 떨어지지 ..
https://atcoder.jp/contests/abc340/tasks/abc340_f F - S = 1 AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online. atcoder.jp 확장 유클리드 알고리즘으로 선형방정식 ax+by = 1의 해를 구하는 전형적인 문제인데... 어설프게 알다보니 해결하지 못했다.. 문제탓?을 하자면 스페셜저지라는 언급을 안해주니.. 여러개 있으면 하나만 출력해도 된다는 언급을 해줘야하는데 그런게 없어서 헷갈리기도.. 문제 핵심은 (x,y)가 주어질때 평면상 (0,0), (x,y), (a,b)이 이루는 삼각형의 넓이가 ..
1. n번째 페리수열의 i번째 항이 주어질 때 i+1번째 항을 찾는 방법 n번째 페리 수열의 한 원소 $\frac{a}{b}$가 주어졌다고 하자. 이 수보다 크면서 이웃한 바로 다음 항 원소를 구할 수 있을까? 예를 들어 $\frac{2}{5}$ 바로 다음 항에 존재하는 분모가 6이하인 기약분수를 찾으라한다면, $\frac{1}{2}$가 답이다. n번째 페리수열에서 $\frac{a}{b}$와 $\frac{c}{d}$가 서로 이웃하다면, bc - ad = 1이다. 이때 b와 a를 알기 때문에 bx - ay = 1을 만족하는 서로소인 정수 x,y를 구하는 문제이다. https://deepdata.tistory.com/576 확장된 유클리드 알고리즘(extended euclidean algorithm) 구현해..
1. 페리 수열의 대칭성(symmetry) n번째 페리 수열의 분수 $\frac{a}{b}$에 대해 생각해보자. 먼저 기약분수이므로 a,b가 서로소이고 0과 1 사이에 있으므로 a < b이다. https://deepdata.tistory.com/1104 페리 수열(farey sequence) 조금 더 깊게1 - 페리 수열의 길이 - 1. 페리 수열의 길이 n번째 페리 수열은 분모가 n 이하인 0과 1 사이의 모든 기약분수를 오름차순으로 나열한 것이다. 기약분수가 무엇인가? $\frac{a}{b}$가 기약분수라면 a와 b가 서로소라는 뜻이다. deepdata.tistory.com 이전에 관찰했던 것처럼 n번째 페리 수열에는 분모가 n 이하인 정수 b에 대하여 b보다 작은 서로소인 모든 정수 a에 대해 $\..
1. 페리 수열의 길이 n번째 페리 수열은 분모가 n 이하인 0과 1 사이의 모든 기약분수를 오름차순으로 나열한 것이다. 기약분수가 무엇인가? $\frac{a}{b}$가 기약분수라면 a와 b가 서로소라는 뜻이다. 이때, 0과 1 사이에 존재하는 기약분수이므로 a < b이다. 그러므로 n번째 페리수열에 존재하는 기약분수들은 다음과 같이 만들수도 있다. "양 끝에는 $\frac{0}{1}, \frac{1}{1}$이 있고, 분모가 b = 2,3,4,5,..,n에 대하여 분자는 k보다 작으면서 서로소인 모든 정수 a에 대해 $\frac{a}{b}$를 나열한 것이다." 예를 들어, 5번째 페리 수열을 보자. 분모가 2이면 2와 서로소인 1에 대해 $\frac{1}{2}$ 분모가 3이면 3과 서로소인 1,2에 대해..
1. n번째 페리 수열 0부터 1사이의 분모가 n이하인 모든 기약분수를 오름차순으로 나열한 수열 n = 1부터 8까지의 경우를 나열하면 다음과 같다. 2. 두 분수 사이에 있는 분수 theorem1) 0과 1 사이의 두 분수 $\frac{a}{b}$와 $\frac{c}{d}$에 대하여 $\frac{a}{b} 0$이다. 그런데 $$\frac{a+c}..
딥러닝/머신러닝, 통계학, IT프로그래밍, 알고리즘을 좋아하는 사람 https://github.com/yundaehyuck
