몽상실현개발주의

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

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

[알고리즘 기초] 09_SW 문제해결 응용_2 / Python 1. 완전 검색 & 그리디 1.1 반복과 재귀 반복(Iteration)과 재귀(Recursion) 반복과 재귀는 유사한 작업을 수행할 수 있다. 반복은 수행하는 작업이 완료 될때까지 계속 반복 루프(for, while 구조) 재귀는 주어는 문제의 해를 구하기 위해 동일하면서 더 작은 문제의 해를 이용하는 하나의 방법 하나의 큰 문제를 해결할 수 잇는 (해결하기 쉬운) 더 작은 문제로 쪼개고 그 결과들을 결합한다. 재귀 함수로 구현 반복 구조 초기화 반복되는 명령문을 실행하기 전에 조건 검사에 사용할 변수의 초기값 설정 조건검사 반복할 명령문 실행 업데이트 무한루프가 되지 않게 조건이 거짓이 되게 한다 재귀적 알고리즘 재귀적 정의는 두 부분으로..

[알고리즘 기초] 08_SW 문제해결 응용_1 / Python 1. SW 문제 해결 문제 해결 역량 프로그램을 하기 위한 많은 제약조건과 요구사항을 이해하고 최선의 방법을 찾아내는 능력 프로그래머가 사용하는 언어나 라이브러리, 자료구조, 알고리즘에 대한 지식을 적재적소에 퍼즐을 배치하듯 이들을 연결하여 큰 그림을 만드는 능력 추상적인 기술 훈련이 필요하다 문제 해결 과정 문제를 읽고 이해한다. 문제를 익숙한 용어로 재정의 한다. 어떻게 해결할지 계획을 세운다. 계획을 검증한다. 프로그램으로 구현한다. 어떻게 풀었는지 돌아보고, 개선할 방법을 찾는다. 문제 해결 전략 직관과 체계적인 접근 2. 복잡도 분석 알고리즘 유한한 단계를 통해 문제를 해결하기 위한 절차나 방법이다. 주로 컴퓨터용어로 쓰이며, 컴퓨터..