07-2 오일러 피
- 오일러 피 함수 P[N]의 정의는 1부터 N까지 범위에서 N과 서로소인 자연수의 개수를 뜻한다.
- 오일러 피 함수는 증명 과정을 공부해야 완벽하게 알 수 있지만, 이 책에서는 실제 코딩 테스트에 사용하기 위한 구현 부분만 알아보자.
[오일러 피의 핵심 이론]
1. 구하고자 하는 오일러 피의 범위만큼 리스트를 자기 자신의 인덱스 값으로 초기화한다.
2. 2부터 시작해 현재 리스트의 값과 인덱스가 같으면(= 소수일 때) 현재 선택된 숫자(K)의 배수에 해당하는 수를 리스트 끝까지 탐색하며 P[i] = P[i] - P[i]/K 연산을 수행한다. (i는 K의 배수)
3. 리스트의 끝까지 2번 과정을 반복하여 오일러 피 함수를 완성한다.
📌 문제 041) 오일러 피 함수 구현하기
시간 제한 1초, 골드 I, 백준 11689번
자연수 n이 주어졌을 때, GCD(n, k) = 1을 만족하는 자연수 1 ≤ k ≤ n 의 개수를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 자연수 n (1 ≤ n ≤ 10^12)이 주어진다.
10 # n
출력
GCD(n, k) = 1을 만족하는 자연수 1 ≤ k ≤ n 의 개수를 출력한다.
4
1단계 문제 분석
- 문제에서 요구하는 GCD(n, k) = 1을 만족하는 자연수의 개수가 바로 오일러 피 함수의 정의이다. 즉, 오일러 피 함수 구현 문제이다.
- 서로소 개수를 표현하는 변수 result와 현재 소인수 구성을 표시하는 변수 n을 선언한다.
- 2~N의 제곱근까지 탐색하면서 소인수일 때 result = result - (result + 소인수) 연산으로 result값을 업데이트 한다. 이때, n에서 이 소인수는 나누기 연산으로 삭제한다.
- P(현재 수) = 2 -> n(45) % P(2) != 0 -> 소인수가 아님.
- P(현재 수) = 3 -> n(45) % P(3) == 0 -> 소인수이므로 값 업데이트
-> result = 45 - 45/30 = 30
-> n = 45 / 3^2 = 5 - P(현재 수) = 4 -> 현재 n(5)의 제곱근보다 4가 크므로 반복문 종료
- 반복문 종료 후 현재 n이 1보다 크면, n이 마지막 소인수라는 뜻이다. result = result - (result/n) 연산으로 result 값을 마지막으로 업데이트한 후, 출력한다.
-> result(30) = 30 - (30 / 5) = 24
2단계 슈도 코드
n(소인수 표현) result(결괏값)
for 2 ~ n의 제곱근:
if 현재 값이 소인수라면:
결괏값 = 결괏값 - 결괏값 / 현재 값
n에서 현재 소인수 내역을 제거((2^7)*11*13 -> 현재 소인수가 2일 때 11*13으로 변경)
if n > 1: # n이 마지막 소인수일 때
결괏값 = 결괏값 - 결괏값 / n
결괏값 출력3단계 코드 구현
import math
N = int(input())
result = N
for p in range(2, int(math.sqrt(N)) + 1): # 제곱근까지만 진행
if N % p == 0: # p가 소인수인지 확인
result -= result / p # 결괏값 업데이트
while N % p == 0: # (2^7)*11이라면 2^7을 없애고 11만 남김
N /= p
if N > 1: # 반복문에서 제곱근까지만 탐색했으므로 1개의 소인수가 누락되는 케이스 처리
result -= result / N
print(int(result))07-3 유클리드 호제법
- 유클리드 호제법은 두 수의 최대 공약수를 구하는 알고리즘이다.
- 일반적으로 최대 공약수를 구하는 방법은 소인수 분해를 이용한 공통된 소수들의 곱으로 표현할 수 있지만 유클리드 호제법은 좀 더 간단한 방법을 제시한다.
- MOD 연산: 두 값을 나눈 나머지를 구하는 연산
- ex) 10 MOD 4 = 2 # 10 % 4 = 2
[MOD 연산으로 구현하는 유클리드 호제법]
1. 큰 수를 작은 수로 나누는 MOD 연산을 수행한다.
2. 앞 단계에서의 작은 수와 MOD 연산 결괏값(나머지)으로 MOD 연산을 수행한다.
3. 2번 과정을 반복하다가 나머지가 0이 되는 순간의 작은 수를 최대 공약수로 선택한다.
📌 문제 042) 최소 공배수 구하기
시간 제한 1초, 실버 V, 백준 1934번
두 자연수 A와 B에 대해서, A의 배수이면서 B의 배수인 자연수를 A와 B의 공배수라고 한다. 이런 공배수 중에서 가장 작은 수를 최소공배수라고 한다. 예를 들어, 6과 15의 공배수는 30, 60, 90등이 있으며, 최소 공배수는 30이다.
두 자연수 A와 B가 주어졌을 때, A와 B의 최소공배수를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 테스트 케이스의 개수 T(1 ≤ T ≤ 1,000)가 주어진다. 둘째 줄부터 T개의 줄에 걸쳐서 A와 B가 주어진다. (1 ≤ A, B ≤ 45,000)
3 # 테스트 케이스 개수 1 45000 # A, B 6 10 13 17
출력
첫째 줄부터 T개의 줄에 A와 B의 최소공배수를 입력받은 순서대로 한 줄에 하나씩 출력한다.
45000 30 221
1단계 문제 분석
- 최소 공배수는 A와 B가 주어졌을 때, 'A * B / 최대 공약수'를 계산해 구할 수 있다. 결국 최대 공약수를 구하기 위해 유클리드 호제법을 이용하는 것이다.
- 유클리드 호제법을 이용해 A, B의 최대 공약수를 구한다.
- 두 수의 곱을 최대 공약수로 나눈 값을 정답으로 출력한다.
ex) gcd(6, 10) = 2, 최소 공배수 = 6 * 10 / 2 = 30
2단계 슈도 코드
# 최대 공약수 gcd() 함수 구현
gcd(a, b):
if b가 0이면:
a가 최대 공약수
else:
gcd(작은 수, 큰 수 % 작은 수) # 재귀 함수 형태로 구현
t(테스트 케이스)
for t만큼 반복:
a(1번째 수) b(2번째 수)
결괏값 = a * b / gcd(a, b)
결괏값 출력3단계 코드 구현
def gcd(a, b):
if b == 0:
return a
else:
return gcd(b, a % b) # 재귀 형태로 구현
t = int(input())
for i in range(t):
a, b = map(int, input().split())
result = a * b / gcd(a, b)
print(int(result))