기본 수학

나머지 연산 (Modulo Operation)

나머지 연산(Modulo Operation)은 나눗셈의 나머지를 구하는 연산을 의미한다.
나머지 연산을 표현할 때는 mod로 표현하고, 프로그래밍 언어에서는 보통 %에 해당한다.

`python`

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진수)

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

**10진수 → k진수 변환**

시간 복잡도: $O(log_k(n))$
수학적으로는 10진법으로 표기된 숫자를 k로 나누어 그 나머지를 표시하고 더 이상 나눌 수 없을 때까지 반복하여 표기하는 방식이다.
예를 들어, 10진수 13을 2진수로 변환하는 과정은 다음과 같다.
따라서, 10진수 13은 2진수로 1011이 된다.
이 과정에서 구한 나머지들을 역순으로 읽으면 변환된 2진수를 얻을 수 있다.

`python`

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

**k진수 → 10진수 변환**

시간 복잡도: $O(n log k)$
수학적으로는 각 자리의 숫자에 해당 진법의 거듭제곱을 곱한 후 모두 더하는 방식이다.
- 예를 들어, 2진수 “1010”을 10진수로 변환하면 (1×2³) + (0×2²) + (1×2¹) + (0×2⁰) = 8 + 0 + 2 + 0 = 10이 된다.

`python`

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)

어떤 수 $n$ $n$ 의 약수는 $n$ $n$ 을 나누어 떨어지게 하는 수를 의미한다.
- 예를 들어, 12의 약수는 1, 2, 3, 4, 6, 12가 존재한다.
n의 약수를 구하는 법
- 시간 복잡도: $O(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의 약수를 구하는 법
- 시간 복잡도: $O(\sqrt{n})$
- 1부터 $\sqrt{n}$ 까지의 모든 수를 살펴보며 나누어떨어지는지 확인하면 구할 수 있다.
- $\sqrt{n}$ 까지만 살펴봐도 되는 이유는 $a \times b = n$ 에서 $min(a,b) ≤ \sqrt{n}$ 이기 때문이다.

`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개라면 그 수는 소수라고 할 수 있다.
따라서, 어떤 수 $n$ 이 소수인지를 판단하고 싶다면 약수를 구하면 된다.
$n$ $n$ 이 소수인지 아닌지 판단하는 법
- 시간 복잡도: $O(n)$
- $n$ 의 약수를 구하는 과정은 1부터 $\sqrt{n}$ 까지 살펴보면 된다.
- $n$ 의 약수를 구한 후에 개수가 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의 최대 공약수를 구하는 법
  - 시간 복잡도: 약 $O(\sqrt{max(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))

유클리드 알고리즘을 이용하면 $O(log(min(a, b)))$ 에 구할 수 있다.

최소 공배수 (LCM, Least Common Multiple)
- 어떤 두 수 $a$ $a$ , $b$ $b$ 의 최소 공배수는 $a$ $a$ , $b$ $b$ 의 공배수 중에서 가장 작은 수를 의미한다.
  - 공배수: 두 수에 대해 모두 배수인 수를 의미
  - 예를 들어, 12와 8의 경우에 공배수가 {24, 48, 72, …} 이므로 최소 공배수는 24이다.
- a와 b의 최소 공배수를 구하는 법
  - 두 수의 최대 공약수를 G, 최소 공배수를 L이라고 할 때 아래와 같은 관계를 만족한다.
    
    $a \times b = G \times L$
  - 즉, $L = \frac{a \times b}{G}$ 로 쓸 수 있으니 최대 공약수 G를 구하면 최소 공배수 L을 구할 수 있다.
  - 시간 복잡도: 최대 공약수를 구하는 시간 복잡도와 동일

`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)

def get_LCM(a, b):
	return (a * b // get_GCD(a, b))

print(get_LCM(12, 8))

소인수분해 알고리즘

소인수분해는 어떤 수 $n$ 을 소수(prime number)의 곱으로만 나타내는 것을 의미한다.
시간 복잡도: $O(N)$
어떤 수 n을 소인수분해하는 방법은 2부터 n까지 살펴 보면서 소수로 나누어보면 된다.

`python`

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))

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

에라토스테네스의 체 알고리즘을 이용하면 $N$ 이하의 자연수를 소수인지 빠르게 판별할 수 있다.
에라토스테네스의 체 알고리즘 원리 (자세한 설명 링크)
- 자연수 $i$ $i$ 에 대해 다음과 같은 과정을 반복한다. ($2 ≤ i ≤ \sqrt{N}$)
  - $i$ 를 제외한 $i$ 의 배수를 소수에서 제외시킨다.
  - $i$ 에 1을 더한다.
- 시간 복잡도: $O(N \cdot log(\small{logN}))$

`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])

유클리드 알고리즘

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

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

시간 복잡도: $O(logN)$

`python`

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

print(gcd(12, 8))

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

`python`

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

print(16, 18)

나머지 연산 (Modulo Operation)

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

약수 (Divisor)

소수 (Prime Number)

최대 공약수와 최소 공배수

소인수분해 알고리즘

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

유클리드 알고리즘

Command Palette

Choose Theme