몽상실현개발주의

[종만북] 모듈라 연산 / 정수론 모듈라 연산 (Modular Arithmetic) 모듈라 M 에 도달 하면, 다시 0으로 돌아가는 정수들로 하는 연산 모듈라 연산에서 모든 정수는 M 으로 나눈 나머지로 표현됨 ex) 시계 모듈라 덧셈 두 수의 합의 모듈라 연산은, 두 수의 모듈라 연산 결과의 합과 같다. (a + b) % M = (a' + b') % M a % M = a' , b % M = b' -> (a + b) % M = ? a = Mx + a' , b = My + b' (a + b) = (Mx + a') + (My + b') = M(x+y) + ( a'+b') (a + b) % M = ( M(x+y) + a' + b') % M = (a' + b') % M -> (a + b) % M = (a' + ..

https://www.algospot.com/judge/problem/read/POTION# algospot.com :: POTION 마법의 약 문제 정보 문제 마법의 약 수업 시간에 교수님의 설명을 안 듣고 졸던 헤리는 실수로 냄비에 몇 가지 재료의 양을 잘못 넣고 말았습니다. 약의 색깔이 심상치 않게 변하는 것을 눈치챈 www.algospot.com [종만북] POTION / solution 효율적인 알고리즘 / Python 파이썬 Solution 효율적인 알고리즘 - r_list 들의 약수를 찾아 해결 1. 모든 재료 중 가장 많이 들어간 재료 찾기 -> X = max( p_list[i] / r_list[i] ), 모든 재료는 X 배 이상 들어야가한다. 2. r_list[i] * X 는 항상 정수 ..

https://www.algospot.com/judge/problem/read/POTION# algospot.com :: POTION 마법의 약 문제 정보 문제 마법의 약 수업 시간에 교수님의 설명을 안 듣고 졸던 헤리는 실수로 냄비에 몇 가지 재료의 양을 잘못 넣고 말았습니다. 약의 색깔이 심상치 않게 변하는 것을 눈치챈 www.algospot.com [종만북] POTION / solution 직관적인 알고리즘 / Python 파이썬 Solution 직관적인 알고리즘 - 비율이 맞을 때까지 재료들을 계속 더 넣어보는 방법 1. 첫번째 재료는 4숟가락을 넣어야 하는데, 7 숟가락을 넣음 -> 다른 재료들도 최소 7/4 배 넣어야 함 2. 두번째 재료는 6 x ( 7/4 ) = 10.5 숟가락 넣어야 하는..

https://www.algospot.com/judge/problem/read/POTION# algospot.com :: POTION 마법의 약 문제 정보 문제 마법의 약 수업 시간에 교수님의 설명을 안 듣고 졸던 헤리는 실수로 냄비에 몇 가지 재료의 양을 잘못 넣고 말았습니다. 약의 색깔이 심상치 않게 변하는 것을 눈치챈 www.algospot.com 풀이 주어진 정수 배열의 최대공약수를 구하여 해결하는 문제이다. 최대공약수를 구하기위해 유클리드 알고리즘 을 활용하였다. c = int(input()) def get_gcd(p, q): if q == 0: return p return get_gcd(q, p % q) def get_r_gcd(r_list): for i in range(1000, 0, -1)..

[종만북] 두 수의 최대공약수 구하기 / 정수론 / Python 파이썬 1. 유클리드 알고리즘 - 유클리드 알고리즘 (Euclidean algorithm) p, q (p > q) 의 공약수의 집합 == p-q, q 의 공약수 집합 gcd(p, q) == gcd(p-q, q) gcd(6, 15) = gcd(9, 6) = gcd(3, 6) = gcd(3, 3) = gcd(3, 0) def get_gcd(p, q): if p < q: p, q = q, p if q == 0: return p return get_gcd(p-q, q) gcd = get_gcd(6, 15) print(gcd) # 3 2. 유클리드 알고리즘 최적화 gcd(1024, 6) = gcd(1018, 6) = gcd(1012, 6) = .....

[종만북] 약수의 개수 구하기 / 정수론 / Python 파이썬 1. 에라토스테네스의 체를 이용 에라토스테네스의 체를 이용하여 가장작은 소인수를 구하고 이를 이용하여 약수의 개수를 구함 # 1천만 이하의 모든 수의 약수의 개수를 계산하는 알고리즘 Max = 10000000 # 가장 작은 소인수 minFactor = [x for x in range(Max+1)] minFactor[0] = 0 minFactor[1] = 1 sqrtn = int(Max ** 0.5) for i in range(2, sqrtn+1): if minFactor[i] == i: for j in range(i*i, Max+1, i): if minFactor[j] == j: minFactor[j] = i # minFactorPower[..

https://www.algospot.com/judge/problem/read/PASS486# algospot.com :: PASS486 비밀번호 486 문제 정보 문제 재훈이는 한 번 담배를 끊겠다고 다짐할 때마다 이메일 계정 비밀번호를 바꾸는 습관이 있습니다. 재훈이는 비밀번호를 항상 "no-smok**X**" 와 같이 정하는데, 여기서 X www.algospot.com 풀이 주어진 범위안의 수 중, 약수의 개수가 n 개가 되는 수의 개수를 구하는 문제이다. 먼저, 에라토스테네스의 체를 사용하여 1천만 이하의 모든 수의 가장 작은 소인수를 구한 뒤 주어진 범위의 약수의 개수를 구해주었다. # 1천만 이하의 모든 수의 약수의 개수를 계산하는 알고리즘 Max = 10000000 # 가장 작은 소인수 mi..

[종만북] 빠른 소인수 분해 (에라토스테네스의 체 사용) / 정수론 / Python 파이썬 체에서 각 숫자가 소수인지 합성수인지를 기록하는 대신, 각숫자의 가장작은 소인수를 기록 기록된 가장작은 소인수를 이용하여, 빠르게 소인수 분해를 진행 # 에라토스테네스의 체를 이용하여 빠른 소인수 분해 # 체 에서 소수 여부 뿐만 아니라, 가장 작은 소인수를 기록하여 최적화 def eratosthenes2(N): nums = [1] * (N+1) for i in range(N+1): nums[i] = i nums[0] = 0 nums[1] = 0 sqrtn = int(N ** 0.5) for i in range(2, sqrtn+1): if nums[i] == i: # 가장 작은 소인수를 기록하여 최적화 for j ..