알고리즘 풀이를 위해서 자주 쓰이는 수학 공식에 대해 정리해두려고 합니다. 암기보다는 이해의 관점에서 글을 작성하도록 하겠습니다.
약수
약수의 개념은 n이라는 어떤 수가 존재할 때, 나누어 떨어지게 하는 수를 의미합니다. 12의 약수는 1, 2, 3, 4, 6, 12 이런 개념입니다.
n = int(input())
arr = set()
for i in range(1, n + 1):
if (n % i == 0): arr.add(i)
print(arr)해당 코드처럼 구현한다면 약수를 구할 수 있습니다. 다만 이 때의 시간 복잡도는 \(O(n)\)입니다.
from math import sqrt
n = int(input())
arr = set()
for i in range(1, int(sqrt(n)) + 1):
if (n % i == 0):
arr.add(i)
arr.add(n // i)
print(arr)다음과 같이 구현할 수도 있습니다. 위의 코드와 차이는 시간 복잡도가 \(O(\sqrt{n})\)입니다. 따라서 시간 복잡도를 더 낮게 가져갈 수 있게되어 더 효율적인 코드라고 볼 수 있겠습니다.
소수
소수는 1보다 큰 자연수 중에 1과 자기 자신만을 약수로 가지는 수를 의미합니다. 소수를 구하는 것은 어떤 수의 약수의 개수가 2개라면 그것은 소수라고 볼 수 있기에 약수를 먼저 구해주는 것이 해결법이 되겠습니다.
from math import sqrt
n = int(input())
arr = set()
result = False
for i in range(1, int(sqrt(n)) + 1):
if (n % i == 0):
arr.add(i)
arr.add(n // i)
if (len(arr) == 2): result = True
print(result)
최대 공약수와 최소 공배수
최대 공약수는 어떤 두 수 간의 공약수 중에서 가장 큰 수를 의미합니다. 공약수는 두 수가 공통적으로 나누어 떨어지는 수를 말합니다. 구현하는 경우에 두 수의 약수를 구하고 그들의 교집합 간에서 가장 큰 수를 출력하면 될 것입니다.
from math import sqrt
a, b = map(int, input().split())
a_arr = set()
b_arr = set()
for i in range(1, int(sqrt(a)) + 1):
if a % i == 0:
a_arr.add(i)
a_arr.add(a // i)
for i in range(1, int(sqrt(a)) + 1):
if b % i == 0:
b_arr.add(i)
b_arr.add(b // i)
print(max(a_arr & b_arr))
최소 공배수는 어떤 두 수 간의 공배수 중에서 가장 작은 수를 의미합니다. 공배수는 두 수에 대해 모두 배수를 말합니다. 마찬가지로 구현에 있어서는 최소공배수를 구하는 법이 존재합니다. \( a \times b = G \times L \) 이런 식을 만족하기 때문에 최소 공배수를 구할 수 있습니다.
from math import sqrt
a, b = map(int, input().split())
a_arr = set()
b_arr = set()
for i in range(1, int(sqrt(a)) + 1):
if a % i == 0:
a_arr.add(i)
a_arr.add(a // i)
for i in range(1, int(sqrt(a)) + 1):
if b % i == 0:
b_arr.add(i)
b_arr.add(b // i)
print(int((a * b) / max(a_arr & b_arr)))
소인수분해
어떤 수 n을 소수의 곱으로만 나타내는 것을 의미합니다. 6의 경우에는 2, 3이라는 소수의 곱으로 나타낼 수 있는 것처럼 그것을 말합니다. 구현의 방법은 2부터 n까지의 수를 모두 n에 나누어서 나누어 떨어지는 경우를 담아서 처리하면 될 것 같습니다.
n = int(input())
arr = []
for i in range(2, n + 1):
while n % i == 0:
arr.append(i)
n //= i
print(arr)
에라토스테네스의 체
에라토스테네스의 체를 활용하면 주어진 수에 대해 소수 판별을 더 빠르게 진행할 수 있습니다. 구현의 방법은 배열의 인덱스가 숫자를 의미하며 그 값은 boolean형으로 처리합니다.
from math import sqrt
MAX = 120
n = int(input())
arr = [True] * (MAX + 1)
arr[1] = False
for i in range(2, int(sqrt(MAX) + 1)):
if not arr[i]: continue
for j in range(2 * i, MAX + 1, i):
arr[j] = False
print(arr[n])
유클리드 알고리즘
유클리드 알고리즘은 최대 공약수를 빠르게 구하는 알고리즘입니다. 해당 알고리즘을 구현하기 위해서는 재귀함수의 개념에 대해 먼저 알고있어야 합니다. https://choidevvv.tistory.com/143 로 정리해두었습니다.
유클리드 알고리즘을 또 다른 말로 정리하면 a, b라는 어떤 수 두 수 가 생성되었다고 가정하겠습니다. a를 b로 나눌 수 있다 가정했을 때, 생기는 나머지 값(r)이 생길 것입니다. 이 때, a와 b의 최대공약수가 b와 r의 최대공약수와 같습니다. 즉 이 식을 구하기 위해서는 계속해서 b와 r을 구해 r이 0이 되는 순간의 값이 최대공약수임을 만들어주면 됩니다.
a, b = map(int, input().split())
def gcd(a, b):
if (b == 0): return a
return gcd(b, a % b)
print(gcd(a, b))