안녕하세요, 개발감자입니다!
오늘은 알고리즘 중 <정수론>에 대해서 정리해보는 시간을 가져보겠습니다.
1. 정수론이란 무엇일까요?
수학에서 정수론은 말 그대로 수의 성질을 탐구하는 분야를 의미합니다.
정수론 굉장히 방대한 범위를 가지고 있습니다. 하지만, 코딩 테스트에서는 모든 분야는 나오지 않고, 아래에 나올 내용인 소수 구하기, 오일러 피, 유킬리드 호제법이 가장 빈출되는 분야라고 합니다. 이 분야들을 집중으로 다뤄보는 시간을 가져보도록 하겠습니다.
2. 정수론 알고리즘
2-1. 소수 구하기
소수는 약수가 1과 자기 자신뿐인 수를 의미합니다. 예를 들어 2,3,5,7,11 등이 습니다.
코딩테스트에서 소수를 구할 때에는 <에라토스테네스의 체>라는 대표적인 소수 판별법을 활용합니다.
<에라토스테네스의 체>의 원리는 다음과 같습니다.
1) 구하고자 하는 소수의 범위만큼 1차원 리스트를 생성합니다.
2) 2부터 시작하고 현재 숫자가 지워진 상태가 아닌 경우 현재 선택된 숫자의 배수에 해당하는 수를 리스트에서 탐색하며 지웁니다.
이때, 처음 선택된 숫자는 지우지 않는 것이 포인트 입니다.
3) 2번 과정을 끝까지 반복한 수 남은 모든 수를 출력하면 끝입니다.
2,4,5,7,8,10,11,16,19,20,22이라는 리스트가 있고, 이 리스트에 에라토스테네스의 체 원리를 적용하였을 때 2,5,7,11,19가 나오게 됩니다.
소수를 구하는 알고리즘이 이미 정해져있습니다. 직접 구현을 하는 것보다는 참고하여 암기한 후 활용하는 것이 더 빠르게 코딩 테스트에 저굥할 수 있을 것입니다.
- 소수구하기 알고리즘
def isitPrime(k): # 소수인지 판별하는 알고리즘
if k < 2:
return False
for i in range(2, int(k ** 0.5) + 1):
if k % i == 0:
return False
return True아래는 에라토스테네스의 체 원리를 활용하여 소수를 구하는 알고리즘입니다. 개발감자가 직접 구현하였습니다.
백준 소수 구하기 문제(1929번)의 답이기도 합니다.
import sys
input = sys.stdin.readline
m, n = map(int, input().split())
a = []
# m 이상 n 사이의 숫자 중에서 소수를 모두 출력하여라
for i in range(0,n+1):
a.append(i)
for i in range(len(a)):
if i == 0 or i == 1 :
a[i] = 0
continue
else:
for j in range(2*i,len(a),i):
a[j] = 0
# 답 출력
for i in range(m,n+1):
if a[i] != 0:
print(a[i])2-2. 오일러 피
오일러 피 함수 P[N]의 정의는 1부터 N까지의 범위에서 N과 서로소인 자연수의 개수를 의미합니다.
코딩 테스트에서는 어떻게 구현하고 활용하는지 같이 알아볼까요?
<오일러 피 함수>의 원리는 다음과 같습니다.
1) 구하고자 하는 오일러 피의 범위만큼 리스트를 자기 자신의 인덱스값으로 초기화합니다.
2) 2부터 시작해 현재 리스트의 값과 인덱스가 같으면(= 소수일 때) 현재 선택된 숫자(K)의 배수에 해당하는 수를 리스트에 끝까지 탐색하며 P[i] = P[i] - P[i]/K 연산을 수행합니다(i는 K의 배수).
3) 리스트의 끝까지 를 반복하여 오일러 피 함수를 완성합니다.
오일러 피 함수 구현하기(백준 11689번) 문제를 풀어보며 알고리즘을 살펴보도록 할게요.
11689번: GCD(n, k) = 1
자연수 n이 주어졌을 때, GCD(n, k) = 1을 만족하는 자연수 1 ≤ k ≤ n 의 개수를 구하는 프로그램을 작성하시오.
www.acmicpc.net
2-1-1. 오일러 피 함수를 그대로 구현하여 만든 알고리즘
제출한 결과, 실패한 알고리즘입니다. 그 이유는 n보다 작은 수에 대한 모든 오일러 피 값을 구하기 때문에 메모리 초과 문제가 생깁니다.
그래서 n을 입력하면 바로 오일러 피 값을 입력할 수 있는 알고리즘을 생각해내야 합니다. 저는 혼자 생각하기에는 무리가 있어 다른 자료를 참고하여 풀었습니다.
# n의 오일러 피에 해당하는 K의 개수 구하기
# -> n과 k의 공통된 자연수 개수가 1인 경우의 개수 구하기
P = []
for num in range(1,n+1):
P.append(num)
for k in range(1,len(P)):
index = k+1
if P[k] == index :
for i in range(k,len(P),index):
pp = P[k]
temp =int (P[i] // index)
P[i] = P[i] - int (P[i] / index)
print(P[-1])2-1-2. 오일러의 Totient 함수를 직접 사용한 알고리즘
오일러 피 함수 (Euler's Totient Function 또는 Euler's Phi Function)은 어떤 자연수 n에 대해, n과 서로소인(공약수가 없는) 자연수의 개수를 반환하는 함수입니다. 이 함수를 기호로 나타내면 ϕ(n)이라고 합니다.
오일러 피 함수의 값은 다음과 같이 계산됩니다.
1) 기본 값 설정: ϕ(n)을 n으로 초기화합니다.
2) 소인수 분해: n을 소인수로 분해합니다. (예를 들어, n = p1^a1 * p2^a2 * ... * pk^ak)
3) 계산: ϕ(n) = n * (1 - 1/p1) * (1 - 1/p2) * ... * (1 - 1/pk)
여기서 p1, p2, ..., pk는 n의 소인수이고, a1, a2, ..., ak는 각 소인수의 지수입니다.
import sys
input = sys.stdin.readline
n = int(input())
def euler_phi(n):
result = n # Initialize result as n
# Consider all prime factors of n and subtract their multiples
# from result
p = 2
while p * p <= n:
if n % p == 0:
while n % p == 0:
n //= p
result -= result // p
p += 1
# If n has a prime factor greater than sqrt(n)
if n > 1:
result -= result // n
return result
answer = euler_phi(n)
print(answer)
2-3. 유클리드 호제법
유클리드 호제법은 두 수의 최대 공약 수를 구하는 알고리즘입니다.
유클리드 호제법 이론을 활용하기 위해서는 MOD 연산을 알고 있어야 합니다. A MOD B 는 A와 B값을 나눈 나머지를 구하는 계산입니다.
예를 들어 10 MOD 4 = 10 % 4 = 2 로 계산이 될 것입니다.
아래는 유클리드 호제법을 구현하는 원리입니다.
1) 큰 수를 작은 수로 나는 MOD 연산을 수행합니다.
2) 앞 단계에서의 작은 수와 MOD 연산 결괏값으로 MOD 연산을 다시 수행합니다.
3) 2번을 반복하다 나머지가 0이 되는 순간의 작은 수를 최대 공약수로 선택합니다.
최소공배수 구하기 (백준 1934번) 문제를 보며 유클리드 호제법을 이해해볼까요?
import sys
input = sys.stdin.readline
def gcd(n1, n2):
if n2 == 0:
return n1
else:
return gcd(n2, n1 % n2)
t = int(input())
lst = []
for i in range(t):
a, b = map(int, input().split())
lst.append([a,b])
for i in range(t):
a,b = lst[i][0], lst[i][1]
# Calculate GCD
temp2 = gcd(b, a)
# Calculate LCM
temp = a * b // temp2
print(temp)
중학교 때 배웠던 유클리드 호제법을 그대로 적용하면 쉽게 풀 수 있는 문제입니다. 최소공배수는 두 수(a,b)가 주어졌을 때, a*b/최대공약수로 구할 수 있습니다. 유클리드 호제법을 이용해 최대공약수를 구하고 두 수와의 계산을 완료하여 최소공배수를 구할 수 있었습니다.
2-4. 확장된 유클리드 호제법
2-3번은 두 수의 최대공약수만 구하는 것이었다면 확장된 유클리드 호제법에서는 방정식의 해를 구하는 것입니다.
아래가 구하고자 하는 방정식입니다.
ax + by = c (a,x,b,y,c는 정수)
위의 방정식인 c로 a와 b의 최대공약수(gcd(a,b)) 로 나누었을 때 나머지가 0인 경우에만 정수의 해를 가질 수 있습니다.
Ax + By = C (백준 21568번)을 보며 한 번 이해해볼까요?
import sys
input = sys.stdin.readline
a, b, c = map(int, input().split())
lst = []
record = []
def gcd_lst(n1, n2):
global record
if n2 == 0:
return n1
else:
r, q = n1%n2 , n1//n2
record.append([r,q])
return gcd_lst(n2, r)
def gcd (n1,n2):
if n2 == 0:
return n1
else:
return gcd(n2, n1 % n2)
if c % gcd(a,b) != 0: # x,y가 존재하지 않는 경우
print(-1)
else: # x,y가 존재하는 경우
temp = gcd_lst(a,b)
# x와 y 구하기
x_ = 1
y_ = 0
for i in range(len(record)-1,-1,-1):
q = record[i][1]
x = y_
y = x_-y_* q
x_ = x
y_ = y
k = c / temp
x = int(k*x)
y = int(k*y)
print(x,y)
아직 채점 준비 중인 문제 맞았는지 확인할 수는 없지만, 모든 예제에서 알맞은 예제 출력을 한 코드 예시입니다.
오늘은 정수론에 대해서 한 번에 정리해보는 시간을 가져보았습니다. 이해가 잘 되셨을지 모르겠네요ㅎㅎ
또 다른 알고리즘 정리로 돌아올게요! 개발감자였습니다 :)
'알고리즘' 카테고리의 다른 글
| 이진트리의 개념과 종류 / 전위순회, 중위 순회, 후휘 순회 알아보기 (0) | 2024.01.18 |
|---|---|
| [알고리즘 마스터] 14. 트리와 트라이 (0) | 2024.01.16 |
| [알고리즘 마스터] 12. 스택과 큐 (1) | 2024.01.08 |
| [알고리즘 마스터] 11. 슬라이딩 윈도우 (1) | 2024.01.07 |
| [알고리즘 마스터] 10. 투 포인터 (1) | 2024.01.05 |
