[AlgorithmSolving][수학] JUNGOL_1002: 최대공약수, 최소공배수
1. 문제 내용
-
문제
N개의 정수를 입력받아서 최대공약수와 최소공배수를 구하는 프로그램을 작성하여 보자
-
입력
첫째 줄에 N (2≤N≤10) 을 입력 받고 다음 줄에 N개의 정수를 공백으로 구분하여 입력 받는다.
입력 받는 정수는 2이상 10,000 이하이다. 데이터의 크기가 주어진 범위를 벗어나는 입력은 없다.
-
출력
입력받은 정수들의 최대공약수와 최소공배수를 공백으로 구분하여 출력한다. 최소공배수는 20억 이하의 정수이다.
-
예제
입력:
3 2 8 10출력:
2 40
2. 추상화 정의
N개의 정수가 주어졌을 때, 앞에서부터 순차적으로 두 수의 최대공약수(GCD)와 최소공배수(LCM)을 누적하여 최종적으로 전체 배열의 GCD와 LCM을 구하는 문제
3. 트리거 & 조건
-
“N개의 정수”, “최대공약수와 최소공배수”
-
판단: 2개의 수에 대한 유클리드 호제법을 단순히 N개로 확장(누적 연산)하는 기본 수학 템플릿 문제
4. 해결 과정 (Boilerplate)
-
두 수에 대한 최대공약수와 최소공배수를 구하는 방법만 알고 있었지만 문제에서 제공한 힌트를 통해 두 수 이상일 경우에는 누적으로 해결할 수 있다는 것을 알게 되어 누적으로 풀이를 진행
-
최소공배수의 경우 각 수의 곱에서 모든 수의 최대공약수를 나눠주는 것으로 잘못 알고 있어 최소공배수를 구하는 방식이 잘못되어 0점 오답처리를 받음 아래는 오답을 받은 코드
import sys
import math
input = sys.stdin.readline
n = int(input())
num_list = list(map(int, input().split()))
num_list.sort()
def get_gcd(l, m):
check = False
remain_value = 0
for i in l:
if i % m != 0:
check = True
remain_value = i
break
if check:
remain_value = remain_value % m
return get_gcd(l, remain_value)
else:
return m
gcd_value = get_gcd(num_list, num_list[0])
print(gcd_value)
result = 1
for i in num_list:
result *= i
print(result // int(math.pow(gcd_value, n-1)))
- 최소공배수는 이전에 구했던 최소공배수 값과 새로운 값과의 최대공약수를 구한 후 이전 최소공배수와 새로운 값의 곱에서 최대공약수를 나눠주는 방식으로 구해야 한다는 것을 알게 되어 문제를 해결함 아래는 만점을 받은 코드
import sys
import math
input = sys.stdin.readline
n = int(input())
num_list = list(map(int, input().split()))
def get_gcd(n, m):
remain_value = n % m
if remain_value == 0:
return m
else:
return get_gcd(m, remain_value)
gcd_value = lcm_value = num_list[0]
for i in range(1, n):
gcd_value = get_gcd(num_list[i], gcd_value)
lcm_value = lcm_value // get_gcd(lcm_value, num_list[i]) * num_list[i]
print(gcd_value, lcm_value)
5. 복기 및 최적화
파이썬의 내장 라이브러리와 reduce를 활용하면 N개에 대한 누적 연산을 매우 간결하게 작성할 수 있다는 것을 알게 되었고 그 코드는 다음과 같습니다.
import sys
from functools import reduce
import math
input = sys.stdin.readline
n = int(input())
num_list = list(map(int, input().split()))
# N개의 최대공약수 누적
final_gcd = reduce(math.gcd, num_list)
# N개의 최소공배수 누적 함수
def lcm(a, b):
return (a * b) // math.gcd(a, b)
final_lcm = reduce(lcm, num_list)
print(final_gcd, final_lcm)
Comments