몽상실현개발주의

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

[종만북] 빠른 소인수 분해 (에라토스테네스의 체 사용) / 정수론 / 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..

[종만북] 소수 판별 O(N ^ 0.5 ) / 정수론 / Python 파이썬 주어진 수 N이 소수인지 판단하는 가장 단순한 방법은, 2부터 N-1 까지 모든 수를 순회하면서 이 중 N의 약수가 있는지 확인하는 것이다. N 이 합성수라면 N = p x q 이고, p = N ^ 0.5 이다. 그러므로 N-1 까지 순회하지 않고 N ^ 0.5 까지 순회하도록 최적화 할 수 있다. 그리고 2 보다 큰 모든 짝수는 2 를 약수로 가지고 있으므로, 짝수 중 2 와 홀수들만 소수가 될 수 있다. # O(N ** 0.5) 시간에 동작하는 소수 판별 알고리즘 def isPrime(N): if (N

따배씨 - 따라하며 배우는 C언어 16강 전처리기와 라이브러리 16.11 inline 함수 작은 함수가 반복하여 사용 될 때, 실행 속도를 높일 수 있는 방법 #include /* Function call has overhead - set up the call, pass arguments, jump to the function code, end return. inline function spectifier (함수 특성 지정자) - suggets inline replacements. (제안을 함) - function call overhead 가 없어짐 Inline functions should be short. A function with internal linkage can be made inline. ..

따배씨 - 따라하며 배우는 C언어 16강 전처리기와 라이브러리 16.10 _Generic 표현식 #include /* Generic selection expression - Generic programing : code is not specific to a particular type _Generic : C11 keyword */ #define MYPYPE(X) _Generic((X), \ int : "int", \ float: "float", \ double : "double", \ default: "other" \ ) int main() { int d = 5; printf("%s\n", MYPYPE(d)); // int printf("%s\n", MYPYPE(2.0 * d)); // double pr..

따배씨 - 따라하며 배우는 C언어 16강 전처리기와 라이브러리 16.9 #pragma 지시자 Compiler 에게 Complie 에 대한 지시를 내리는 전처리 지시자 #pragma once include header guard : 중복으로 header 를 include 하는것을 방지 #ifndef SAMPLE_HEADER #define SAMPLE_HEADER // header 내용 #endif 같은 동작을 정의, #pragma once 와 함께 사용 가능 #pragma pack(1) 구조체의 padding size 를 설정 #pragma warning( disable : 4477) Warning 을 disable #pragma warning( error : 4477) Warning 을 Error 처리 ..