몽상실현개발주의

[종만북] 두 수의 최대공약수 구하기 / 정수론 / 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) = .....

따배씨 - 따라하며 배우는 C언어 16강 전처리기와 라이브러리 16.13 표준 수학 라이브러리 #include #include int main() { printf("%f\n", cos(3.141592)); double c = 5.0, b = 4.0, a; a = sqrt(c * c - b * b); printf("a = %f\n", a); float cf = 5.0f, bf = 4.0f, af; af = sqrtf(cf * cf - bf * bf); printf("af = %f\n", af); return 0; } #include #include // type generic macros #define SQRT(X) _Generic((X),\ long double: sqrtl, \ default: sqrt..

따배씨 - 따라하며 배우는 C언어 16강 전처리기와 라이브러리 16.12 라이브러리 Library : 필요한 책들이 잔뜩 모여있는 도서관 참고 Compile : 책을 출판하기 위해 ''편집하다'' 라는 의미 Library 는 Main 함수가 없음 Library 의 종류 Static Library : 프로그램에 Library 가 포함되어 있음 Dynamic Library : 프로그램의 실행 도중 필요 할때, 동적으로 Library 를 가져다 사용함 확장자별 종류 .a : 리눅스/정적 라이브러리 .so : 리눅스/동적라이브러리 .lib : 윈도우/정적라이브러리 .dll : 윈도우/동적라이브러리 Library 와 Header 의 차이 라이브러리 : 기계어로 번역된 것 헤더파일은 : 컴파일 하기 전, 프로그래머..

[종만북] 약수의 개수 구하기 / 정수론 / 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 ..

[종만북] 에라토스테네스의 체 / 정수론 / Python 파이썬 N 까지의 모든 소수를 구하는 방법이다. 소수 판별을 위하여 (N ^ 0.5) 까지의 모든 수로 나눠보는 대신, (N ^ 0.5) 까지 순회하며 소수를 찾을 때마다 그 배수들을 지우는 형태로동작하기 때문에 훨씬 빠르게 수행된다. 최적화 N 이 아니라 (N ^ 0.5) 까지만 순회. i 의 배수들을 모두 지울 때 2xi 에서 시작하는 것 이 아니라 (i X i) 에서 시작 / 2Xi, 3Xi 는 2 와 3의 배수를 지울때 삭제되기 때문 # 에라토스테네스의 체 def eratosthenes(N): nums = [1] * (N+1) nums[0] = 0 nums[1] = 0 sqrtn = int(N ** 0.5) for i in range(sqr..

[종만북] 간단한 소인수 분해 / 정수론 / Python 파이썬 2부터 (N ^ 0.5) 까지의 수를 더이상 나눠지지 않을 때까지 나누는 것으로 소인수 분해를 진행한다. n이 소수 인 경우 (N ^ 0.5) 번 반복문을돌기 때문에 시간복잡도는 O(N ^ 0.5)가 된다. # 간단한 소인수 분해 알고리즘 # 시간복잡도 O( N ** 0.5 ) def factorSimple(N): ret = [] sqrtn = int(N ** 0.5) # 소수가 아닌 [2, N**0.5] 범위의 모든 정수로 시도 for div in range(2, sqrtn+1): while(N % div == 0): N //= div ret.append(div) if (N > 1): ret.append(N) return ret print..