반응형
문제
첫 번째 분수의 분자와 분모를 뜻하는 numer1, denom1, 두번째 분수의 분자와 분모를 뜻하는 numer2, denom2가 매개변수로 주어집니다. 두 분수를 더한 값을 기약 분수로 나타냈을 때 분자와 분모를 순서대로 담은 배열을 return 하도록 solution 함수를 완성 해보세요.
원리
이 문제의 핵심 원리는 두 분수의 덧셈과 최대공악수 구하는 것입니다.
최대 공약수 구하기
유클리드 호제법은 두 개의 자연수에 대한 최대 공약수를 구하는 알고리즘 입니다. 원리는 다음과 같습니다
- 두 수 A와 B(A > B)가 있을때, A를 B로 나눈 나머지를 R이라고 할 때, A와 B의 최대공약수는 B와 R의 최대 공약수와 같다는 원리 입니다.
- A는 B가 되고 B는 나머지(A = B, B = R) 가 되며, 이 원리를 반복적으로 적용하면, 나머지가 0이 되는 순간의 나누는 수가 두수의 최대 공약수(GCD)가 됩니다.
예를 들어 A가 24, B가 18일때 나눈 나머지가 R이 6이 됩니다. A가 B가 되고 B가 R이 되고 이원리를 반복해 R이 0이 되면, R와 B가 최소의 A,B의 최대 공약수가 됩니다.
분수의 덧셈
- 공통 분모 찾기
두 분수의 분모를 곱하여 공통 분모를 찾습니다. 예를 들어 1/2와 3/4 경우, 공통 분모는 2 * 4 = 8입니다. - 분자 계산하기
각 분수의 분자에 다른 분소의 분모를 곱하고 더합니다. 예를 들어 1/2와 3/4의 경우, 분자는 1 * 4 + 3 * 2 = 10입니다. - 기약 분수로 만들기
분자와 분모의 최대 공약수를 찾아 분자와 분모를 나눕니다. 예를 들어 10 / 8의 경우, 분자와 분모의 최대 공약수는 2이므로, 분자와 분모에 2로 나누면 5/4의 값이 얻어 집니다.
풀이
Python
def gcd(a, b):
while b != 0:
a, b = b, a % b
return a
def solution(numer1, denom1, numer2, denom2):
# 두 분수의 합을 구한다.
numer = numer1 * denom2 + numer2 * denom1
denom = denom1 * denom2
# 분자와 분모의 최대공약수를 구한다.
gcd_value = gcd(numer, denom)
# 분자와 분모를 최대공약수로 나눠 기약분수를 만든다.
numer //= gcd_value
denom //= gcd_value
return [numer, denom]gcd함수는 최대공약수 구하는 역할이고 solution은 두 분수의 합을 구하고 기약분수로 만듭니다.
출처
https://school.programmers.co.kr/learn/courses/30/lessons/120808
반응형
