문자열 hashing function 빠르게 계산하는 방법

1. 왜 문자열의 hashing이 필요한가? https://deepdata.tistory.com/960 문자열 해싱(hashing) 기본 개념 배우기String Hashing - Algorithms for Competitive Programming (cp-algorithms.com) String Hashing - Algorithms for Competitive Programming String Hashing Hashing algorithms are helpful in solving a lot of problems. We want to solve the problem of comparing stringdeepdata.tistory.com  두 문자열 S1, S2가 서로 같은지 다른지 비교하고 싶을 때가 있..

• format_list_bulleted 문자열 알고리즘
• · 2024. 5. 18.
• textsms

100부터 1000000000000000까지 모든 정수의 최대공약수는 어떻게 구할 수 있을까

SW Expert Academy SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com a이상 b이하의 모든 정수의 최대공약수를 구하는 문제 a,b는 1부터 $10^{100}$까지이다. 예를 들어 {70, 105, 42}의 최대공약수는... 70과 105의 최대공약수는 35이고, 35와 42의 최대공약수는 7이므로, 70,105,42의 최대공약수는 7이다. 그러면 gcd(a,a+1,a+2,...,b)를 구하는 문제인데 a,a+1의 최대공약수를 g라 하면 g,a+2의 최대공약수 g, g,b의 최대공약수를 구하면 된다. 그런데 a,b가 최대 $10^{100}$이므로, 이렇게 구하면 시간초과 날것이다 https://deep..

• format_list_bulleted 정수론
• · 2024. 3. 29.
• textsms

페리 수열(farey sequence) 조금 더 깊게2 - 페리 수열의 대칭성과 페리 수열의 합 -

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에 대해 $\..

• format_list_bulleted 정수론
• · 2024. 2. 7.
• textsms

페리 수열(farey sequence) 조금 더 깊게1 - 페리 수열의 길이 -

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에 대해..

• format_list_bulleted 정수론
• · 2024. 2. 7.
• textsms

페리 수열(Farey sequence) 문제를 해결하기 위해 알아야 할 기본 성질 간단하게

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}..

• format_list_bulleted 정수론
• · 2024. 2. 7.
• textsms

gcd와 xor의 성질, 연속하는 두 자연수는 서로소, dict보다 list를 먼저 고려하기

1. 문제 21004번: GCD vs. XOR (acmicpc.net) 21004번: GCD vs. XOR For each test case output a single integer: the number of pairs $(a_i, a_j)$ with $i y이면 p-q ..

• format_list_bulleted 정수론
• · 2023. 8. 13.
• textsms