기본 수학

나머지 연산 (Modulo Operation)

• 나머지 연산(Modulo Operation)은 나눗셈의 나머지를 구하는 연산을 의미한다.

• 나머지 연산을 표현할 때는 mod로 표현하고, 프로그래밍 언어에서는 보통 %에 해당한다.

print(5 % 3)
print(10 % 3)
print(10 % 2)

• 나머지 연산의 특징 (링크)



python

A = 24
B = 15
C = 7

print((A + B) % C, (A % C + B % C) % C) # addition
print((A - B) % C, (A % C - B % C) % C) # subtraction
print((A * B) % C, ((A % C) * (B % C)) % C) # multiplication

진수 변환 알고리즘 (10진수 ↔ k진수)

• 진수 변환은 어떤 수를 한 진법에서 다른 진법으로 바꾸는 과정을 말한다.

def convert(num, k):
    ret = []
    
    while num != 0:
        ret.append(str(num % k))
        num //= k
    
    return ''.join(ret[::-1]) if ret else '0'

def convert_to_decimal(num_str, k):
    decimal_value = 0
    power = len(num_str) - 1
    
    for digit in num_str:
        decimal_value += int(digit) * (k ** power)
        power -= 1
    
    return decimal_value

약수 (Divisor)

• 어떤 수 의 약수는 을 나누어 떨어지게 하는 수를 의미한다.
• 예를 들어, 12의 약수는 1, 2, 3, 4, 6, 12가 존재한다.

• n의 약수를 구하는 법
• 시간 복잡도:
• 1부터 n까지의 모든 수를 살펴보며 나누어떨어지는지 확인하면 구할 수 있다.
python

def get_divisors(n):
	s = set()
	for i in range(1, n + 1):
		if n % i == 0:
			s.add(i)
	return s

print(get_divisors(12))

• 더 효율적으로 n의 약수를 구하는 법
• 시간 복잡도:
• 1부터 까지의 모든 수를 살펴보며 나누어떨어지는지 확인하면 구할 수 있다.
• 까지만 살펴봐도 되는 이유는 에서 이기 때문이다.
python

from math import sqrt

def get_divisors(n):
	s = set()
	for i in range(1, int(sqrt(n)) + 1):
		if n % i == 0:
			s.add(i)
			s.add(n // i)
	return s

print(get_divisors(18))

소수 (Prime Number)

• 소수란 1보다 큰 자연수 중 1과 자기 자신만을 약수로 가지는 수이다.

• 즉, 어떤 수의 약수의 개수가 2개라면 그 수는 소수라고 할 수 있다.

• 따라서, 어떤 수 이 소수인지를 판단하고 싶다면 약수를 구하면 된다.

• 이 소수인지 아닌지 판단하는 법
• 시간 복잡도:
• 의 약수를 구하는 과정은 1부터 까지 살펴보면 된다.
• 의 약수를 구한 후에 개수가 2개인지(1과 자기 자신뿐인지) 확인하면 된다.
python

from math import sqrt

def get_divisors(n):
	s = set()
	for i in range(1, int(sqrt(n)) + 1):
		if n % i == 0:
			s.add(i)
			s.add(n // i)
	return s

def is_prime(n):
	return (len(get_divisors(n)) == 2)

print(is_prime(7))
print(is_prime(8))

최대 공약수와 최소 공배수

• 최대 공약수 (GCD, Greatest Common Divisor)
• 최대 공약수란 두 정수의 공통된 약수 중에서 가장 큰 수를 의미한다.
• 예를 들어, 12와 8의 경우에 공약수가 {1, 2, 4}이므로 최대 공약수는 4이다.
 
• a와 b의 최대 공약수를 구하는 법
• 시간 복잡도: 약
• a와 b에 대해 공약수를 구한 후에 그 중에서 가장 큰 값을 구하면 된다.
python
from math import sqrt

def get_divisors(n):
	s = set()
	for i in range(1, int(sqrt(n)) + 1):
		if n % i == 0:
			s.add(i)
			s.add(n // i)
	return s

def get_GCD(a, b):
	set_a = get_divisors(a)
	set_b = get_divisors(b)
	return max(set_a & set_b)

print(get_GCD(12, 8))
• 유클리드 알고리즘을 이용하면 에 구할 수 있다.

• 최소 공배수 (LCM, Least Common Multiple)
• 어떤 두 수 , 의 최소 공배수는 , 의 공배수 중에서 가장 작은 수를 의미한다.
• 공배수: 두 수에 대해 모두 배수인 수를 의미
• 예를 들어, 12와 8의 경우에 공배수가 {24, 48, 72, …} 이므로 최소 공배수는 24이다.

소인수분해 알고리즘

• 소인수분해는 어떤 수 을 소수(prime number)의 곱으로만 나타내는 것을 의미한다.

• 시간 복잡도:

• 어떤 수 n을 소인수분해하는 방법은 2부터 n까지 살펴 보면서 소수로 나누어보면 된다.

def get_primes(n):
	primes = []
	for i in range(2, n + 1):
		while n % i == 0:
			primes.append(i)
			n //= i
	return primes

print(get_primes(60))
print(get_primes(37))

에라토스테네스의 체 알고리즘

• 에라토스테네스의 체 알고리즘을 이용하면 이하의 자연수를 소수인지 빠르게 판별할 수 있다.

• 에라토스테네스의 체 알고리즘 원리 (자세한 설명 링크)



• 자연수 에 대해 다음과 같은 과정을 반복한다. ()
• 를 제외한 의 배수를 소수에서 제외시킨다.
• 에 1을 더한다.
• 시간 복잡도:
python

from math import sqrt

N = 120
is_prime = [True] * (N + 1)  # 처음에는 모두 true로 초기화
is_prime[1] = False  # 1은 소수가 아니므로

# 에라토스테네스의 체 알고리즘
for i in range(2, int(sqrt(N)) + 1):
    if not is_prime[i]: 
    	continue
    for j in range(2 * i, N + 1, i):
        is_prime[j] = False

for i in range(1, N + 1):
    print(i, is_prime[i])

유클리드 알고리즘

• 유클리드 알고리즘은 최대 공약수를 빠르게 구하는 알고리즘이다.

유클리드 호제법을 코드로 구현하면 된다.

• 시간 복잡도:

def gcd(a, b):
    if b == 0:
        return a
    return gcd(b, a % b)

print(gcd(12, 8))

• 이를 활용해서 기약 분수를 빠르게 구할 수 있다.

if gcd(a, b) != 1:
    a, b = a // gcd(a, b), b // gcd(a, b)

print(16, 18)