✅

정수론

소수 판별

소수(prime number)인지 판별하는 기본 알고리즘

# 시간복잡도 : O(N ** 0.5)
def is_prime(n):
	if n < 2:
		return False
	
	for i in range(2, int(n**0.5)+1):
		if n % i == 0:
			return False
	return True
Python
복사

에라토스테네스의 체

다수의 소수를 빠르게 구하는 방법

# 시간복잡도 : O(N * log(logN))
def eratosthenes(n):
	is_prime = [True] * (n+1) # 0 ~ n
	is_prime[0], is_prime[1] = False # 0,1은 소수X
	
	for i in range(2, int(n ** 0.5)+1):
		if is_prime[i] == True:
			for j in range(i*i, n+1, i):
				is_prime[j] = False
	
	return [i for i,val in enumerate(is_prime) if val]
Python
복사

최대공약수(GCD)

두 수 a, b의 공통 약수 중에서 가장 큰 값

유클리드 호제법

두 수의 최대공약수(GCD)를 구하는 대표적인 알고리즘

# 반복문
def gcd(a,b):
	while b != 0:
		a,b = b, a%b
	return a
Python
복사

# 재귀함수
def gcd(a,b):
	return b != 0 ? gcd(b, a%b) : a
Python
복사

추가 설명

두 수 a,b가 있을 때 우리는

a = bq + r(0<=r<b, a>b)

라고 할 수 있습니다. 이때 어떤 수 d가 a,b의 공약수라고 생각해볼게요. 그렇다면

a - bq = r

에 대해서 d로 양변을 나눌 수 있습니다.

a = bq + r

과

r = -bq + a

를 같이 살펴볼까요? 비슷하다는 느낌을 받으실 겁니다. 맞습니다. a,b의 공약수가 있다를 나타내는 GCD(a,b)는 b,r의 공약수가 있다를 나타내는 GCD(b,r)과 동일하다는 겁니다.

좀 더 수학적으로 말하자면,

d | a이고 d|b라면, d|(a-bq) = r이다. 따라서 d|r이고 d|b, 즉 d는 gcd(b,r)의 공약수이다

결론을 말하자면, GCD(a,b) == GCD(b,r)이 되는거죠.

최소공배수(LCM)

최소공배수 : 두 수 A,B 모두의 배수 중 가장 작은 공통 배수

LCM의 공식

두 수의 곱을 최대공약수로 나눈 것

LCM(A,B) = (A*B) // GCD(A,B)

최대공약수와 최소공배수의 정의를 살펴보겠습니다 :

최대공약수 : 두 수의 공통 약수 중 최대
최소공배수 : 두 수의 공통 배수 중 최소

따라서 두 수의 곱은 항상 최대공약수 * 최소공배수입니다. 그럼 이제 다음 식을 만족하겠죠?

A * B = GCD(A,B) * LCM(A,B)

. 이 식의 양변을 GCD로 나눠주면 위의 식이 나옵니다.

def gcd(a,b):
	while b != 0:
		a,b = b, a%b
	return a
	
def lcm(a,b):
	return (a*b) // gcd(a,b)
Python
복사

def gcd(a,b):
	return (b != 0) ? gcd(b, a%b) : a
	
def lcm(a,b):
	return (a*b) // gcd(a,b)
Python
복사

거듭제곱(빠른 제곱법)

지수승을 로그 시간에 구하는 알고리즘

def fast_pow(base, exp):
	# 기저조건
	if exp == 0:
		return 1
	
	half = fast_pow(base, exp // 2)
	if exp % 2 == 0:
		return half * half
	else:
		return fast_pow(base,exp-1) * base
Python
복사

def fast_pow(base, exp):
	# 기저조건
	if exp == 0:
		return 1
	
	half = fast_pow(base, exp // 2)
	if exp % 2 == 0:
		return half * half
	else:
		return half * half * base
Python
복사

모듈러 연산(mod)

나머지 연산 관련 규칙들 (분배, 곱셈 역원 등)

# 어떤 수열의 합이 매우 커질 수 있을 때, 결과를 1,000,000,007로 나눈 값을 출력하시오
MOD = 10**9 + 7
arr = list(map(int, input().split())

total = 0
for num in arr:
	total += ((total + num) % MOD) # 모듈러 연산 적용
Python
복사

소인수분해

정수를 소수들의 곱으로 표현(EX : 60 = 2^2 * 3 * 5)

def prime_factors(n):
	factors = []
	sosu = 2 # 소수를 찾기 위한 정수값
	
	# 루트n 범위까지만 탐색
	while sosu * sosu <= n:
		while n % sosu == 0:
			factors.append(sosu)
			n //= sosu
			
		# 해당 소수의 개수를 구해냈으면 다음으로 넘어감
		sosu += 1
	
	# 마지막에 남은 값도 소인수
	if sosu > 1:
		factors.append(sosu)
	return factors
Python
복사