1. 최대공약수 / 최소공배수
파이썬에서는 math 라이브러리를 import 하여 쉽게 최대공약수 및 최소공배수를 구할 수 있다. 최대공약수 및 최소공배수를 구하는 방법까지만 알아보고, 예제 풀이는 생략하기로 하자.
① 최대공약수
- math 라이브러리의 gcd(Greatest Common Divisor) 메서드를 이용한다.
import math
a, b = 45, 15
print(math.gcd(a, b)) # 15 출력② 최소공배수
- 두 수의 곱을 최대공약수로 나누어 최소공배수를 구할 수 있다.
- 파이썬 3.9 버전부터는 math.lcm(Least Common Multiple)으로 최소공배수를 구할 수 있게 되었는데, 코딩 테스트 환경에서 사용하지 못할 수도 있으므로, 아래의 방법을 사용할 것을 권장한다.
import math
a, b = 45, 15
print(a * b // math.gcd(a, b)) # 45 출력2. 에라토스테네스의 체
1) 개념
소수를 구하는 가장 대표적인 방법으로, 에라토스테네스의 체가 있다. 예를 들어 1부터 30까지의 숫자 중 소수를 구해야 하는 상황을 가정해보자. 에라토스테네스의 체는 아래와 같은 방법으로 소수를 판별해낸다.
① 1부터 30까지의 숫자를 배열에 넣는다.
② 1은 소수가 아니므로, 2부터 시작한다. 배열에서 2의 배수인 원소를 모두 제거한다.
- 참고로 여기서의 제거는 pop()을 의미하는 것이 아니라, 0으로 Overwrite 하는 것을 말한다.
③ 다음 원소인 3으로 이동하고, 이어서 3의 배수인 원소를 모두 제거한다.
④ 다음 원소인 4는 이미 2의 배수를 지우는 과정에서 0이 되었으며, 4의 배수 또한 모두 0이 된 상태이다. 이처럼 이미 지워진 원소에 대해서는 배수를 제거하는 연산을 생략할 수 잇다.
- 이미 지워진 원소의 배수 제거 연산을 생략함으로써, 실행시간을 크게 단축시킬 수 있다.
⑤ 위와 같은 과정을 충분히 반복한 후, 배열에서 0이 아닌 모든 원소를 순차적으로 출력한다.
※ 원소를 pop()하지 않고 Overwrite 하는 이유
배열의 끝에서 원소를 삭제하는 것은 어려운 일이 아니지만, 배열의 중간에 위치해있는 원소를 제거하는 비용은 최악의 경우 O(N)이므로, 매우 비효율적이다. 따라서, 실제로 원소를 제거하는 방식 대신 무의미한 값으로 덮어 쓰는 것이다. 또한, 에라토스테네스의 체는 반복적인 작업을 수행해야 하는데, 반복문을 수행할 때마다 배열의 인덱스가 변경된다면, 예상과 다른 결과가 도출될 수도 있다. 이러한 이유에서, 실제 원소를 제거하는 방식은 별로 권장되지 않는다.
그렇다면 배열의 size가 N이라고 할 때, 소수가 아닌 모든 수를 지우기 위해 몇 번의 루프를 반복해야 할까? 결론부터 이야기하면, N의 제곱근까지만 반복하면 된다. 그 이유는 아래와 같다.
- N의 제곱근을 n이라고 할 때,
N = a * b를 만족하는 a와 b가 모두 n보다 클 수는 없다. (a가 n보다 크다면, b는 n보다 작아야 한다. 또는a = b = n이어야 한다.) - N보다 작은 수 중에서 소수가 아닌 수 M이
M = c * d로 나타난다면, 반드시 c와 d 중 하나는 n보다 작아야 한다. - 즉, N 이하의 소수가 아닌 모든 수는 n 이하의 약수를 가져야만 한다.
그러므로 n까지만 반복문을 수행하면, N 이하의 소수가 아닌 모든 수를 제거할 수 있는 것이다.
2) 개념 문제
import sys
input = sys.stdin.readline
M, N = map(int, input().split())
arr = [0] * (N + 1)
# 항상 2부터 시작해야 함. M부터 시작할 경우, 아래의 if arr[i] == 0: continue에 의해 M보다 작은 숫자의 배수가 지워지지 않음.
for i in range(2, N + 1):
arr[i] = i
for i in range(2, int(N ** 0.5) + 1):
if arr[i] == 0:
continue
for j in range(i + i, N + 1, i):
arr[j] = 0
for i in range(M, N + 1):
if arr[i] != 0:
print(arr[i]) 3) 심화 문제
>> 백준 1456번
일단 위 문제도 동일한 방식으로 풀이해보자.
M, N = map(int, input().split())
arr = [0] * (N + 1)
for i in range(2, N + 1):
arr[i] = i
for i in range(2, int(N ** 0.5) + 1) :
if arr[i] == 0:
continue
for j in range(i + i, N + 1, i):
arr[j] = 0
count = 0
for i in range(2, int(N ** 0.5) + 1):
if arr[i] != 0:
temp = arr[i]
# arr[i]의 거듭제곱이 B보다 커지기 전까지 제곱을 반복하되, A보다 큰 경우에만 count++
while arr[i] <= B/temp:
if arr[i] >= A/temp:
count+=1
temp = temp * arr[i]
print(count) 위 코드를 실행할 경우, 메모리 초과가 발생한다. 이 문제의 메모리 제한은 256MB(=2.56 X 10^8 Bytes)인데, arr의 크기만 해도 최대 4 X 10^14 Bytes(A = 1, B = 10^14, sizeof(int) = 4로 가정)이다보니 메모리 초과가 발생하는 것은 매우 당연한 일이다. 이처럼 에라토스테네스의 체 알고리즘은 공간 활용이 다소 비효율적이기 때문에, 반드시 문제를 풀이하기 이전에 메모리 제약을 먼저 계산해보아야 한다.
사실 이 문제는 조금만 생각해도 쉽게 해결책을 찾을 수 있다. 소수의 N제곱(N >= 2)이 10^14 이하라는 것은 10^7 이상의 소수에 대해서는 고려할 필요가 없다는 의미이다. 즉, 10^7까지의 숫자 중에서 소수를 찾아낸 이후에 해당 소수를 N제곱한 결과가 A와 B 사이의 존재하는지 확인하면 된다. 10^7까지의 숫자를 저장하는 데에는 4 X 10^7 정도의 메모리만 소요되므로, 메모리 제약 조건을 충족할 수 있을 것으로 판단된다.
import sys
input = sys.stdin.readline
A, B = map(int, input().split())
arr = [0] * (int(10 ** 7) + 1)
for i in range(len(arr)):
arr[i] = i
for i in range(2, int(10 ** 7) + 1):
if arr[i] == 0:
continue
else:
for j in range(i + i, len(arr), i):
arr[j] = 0
count = 0
# range를 2부터 시작하는 이유는 arr[1] = 1이어서 무한루프에 빠지기 때문. 반드시 2부터 시작해야 함.
for i in range(2, int(10 ** 7) + 1):
if arr[i] != 0:
temp = arr[i]
while arr[i] <= B/temp:
if arr[i] >= A/temp:
count+=1
temp = temp * arr[i]
print(count) 3. 오일러 Phi 함수
1) 개념
오일러 피 함수 P[N]은 1부터 N까지의 자연수 중, N과 서로소인 자연수의 개수로 정의된다. 소인수분해의 개념을 알고 있다면, 모든 자연수는 소수의 곱으로 표현될 수 있다는 사실도 알고 있을 것이다. 예를 들어, 16 = 2^4으로 표현될 수 있고, 18 = 2^1 * 3^2으로 표현될 수 있다. 이 때, 우리가 사용하고자 하는 원리는 "N을 구성하는 소인수들의 배수는 N과 서로소가 아니다"라는 것이다.
1부터 18까지의 서로소를 구해야 하는 상황을 가정해보자. 에라토스테네스의 체에서 소수가 아닌 수를 지워나갔던 것과 비슷하게, 이번에는 서로소가 아닌 수를 차례로 지워나갈 것이다. 18과 서로소가 아닌 수는 2, 3, 4, 6, 8, 9, 10, 12, 14, 15, 16인데, 이는 모두 2의 배수이거나 3의 배수이다. 즉, 1부터 18로 구성된 배열에서 2의 배수와 3의 배수를 하나씩 지워나가다보면, 자연히 서로소의 개수를 얻게 된다는 것이다. 오일러 피 함수는 아래와 같은 단계로 구성된다.
① 배열 초기화
- 초기의 P[N] 배열은, 인덱스를 값으로 갖는 배열이다.
- 예를 들어, P = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]으로 초기화된다.
- 즉, P[N] = N이므로, 일단 모든 수와 서로소라고 가정하는 것이다.
② 소수 찾기
- 에라토스테네스의 체와 동일하게 2번 인덱스부터 제곱근까지 소수를 찾는 일을 반복한다.
- 2번 인덱스부터 시작하는 이유는 1이 소수가 아니기 때문이며, 제곱근까지 반복하는 이유는
N = A * B꼴에서 A와 B가 모두 N의 제곱근보다 클 수 없기 때문이다. (제곱근 이하의 약수를 반드시 포함한다.)
③ 배열 원소 갱신
- 소수(K)를 찾으면, 해당 소수의 배수에 해당하는 인덱스(i)의 원소를
P[i] = P[i] - P[i] // K로 업데이트한다. - 여기서,
P[i] // K는 i 이하의 K의 배수의 개수를 의미한다. 예를 들어 9 이하의 3의 배수의 개수는9 // 3 = 3으로 구할 수 있다. - 초기 배열에서 모든 수와 서로소라고 가정했으나, i는 K의 배수들과 서로소가 아니므로, 기존 P[i] 값에서 해당 소수의 배수의 개수만큼을 빼주어야 한다.
④ N 값 갱신
- 위 연산까지 완료되었다면, N에서 해당 소수의 거듭 제곱만큼을 나누어주어야 한다.
- 예를 들어 18에서 2의 배수의 개수를 모두 빼주었다면,
2^1 * 3^2에서3^2으로 갱신해주어야 한다. - 만약 반복문이 종료되었음에도 갱신된 N(N')이 1보다 크다면, 이는 N'이 소수임을 의미한다.
- 예를 들어
N = 34 = 2 * 17일 때, 34의 제곱근인 5까지 반복문을 수행한 결과는N = 17일 것이다. 그러므로 N' > 1일 경우, 반복문의 결과 값에서 34 이내에 17의 개수만큼을 뺴주어야 한다.
2) 문제 풀이
GCD(N, K) = 1이라는 말은 N과 K의 최대 공약수가 1이라는 의미이므로, 이 문제는 N과 서로소인 K의 개수를 구하는 문제이다. 즉, 오일러 Phi 함수를 구현하라는 문제인 것이다.
위 문제의 시간 제약은 1초이고, 메모리 제약은 256MB이다. 하지만, 입력 값 n의 최대 값이 10^12이므로, 배열을 직접적으로 사용하는 방식은 시간 초과 및 메모리 초과 문제를 유발할 것이다. 하지만 이 문제는 P 배열을 구하는 것은 아니고, P[N] 값만 구하면 되므로, 위에서 배운 오일러 피 함수의 원리를 이용하여 쉽게 풀이할 수 있다.
import sys
input = sys.stdin.readline
N = int(input())
result = N
for K in range(2, int(N ** 0.5) + 1):
# 단순히 K가 N의 약수인지를 검사하는 식이지만,
# 소인수 분해의 원리에 의해 K는 항상 소수가 됨.
if N % K == 0:
result -= result // K # N에서 K의 배수의 개수만큼 뺌.
while N % K == 0: # N 값 갱신
N //= K
if N > 1: # 갱신된 N이 소수
result -= result // N # N이 소수이므로, 위 식에 K 대신 N을 대입
print(result)