[프로그래머스]코딩테스트 입문 | 분수의 덧셈 | 최대공약수

[알고리즘]프로그래머스_Python

• 문제를 풀 때 필요한 파이썬 개념, 문법을 기록함으로써 코드 작성에 익숙해진다.
• 알고리즘, 파이썬을 공부하고 복습하는 것이 목적이다.

문제

첫 번째 분수의 분자와 분모를 뜻하는 numer1, denom1, 두 번째 분수의 분자와 분모를 뜻하는 numer2, denom2가 매개변수로 주어집니다. 두 분수를 더한 값을 기약 분수로 나타냈을 때 분자와 분모를 순서대로 담은 배열을 return 하도록 solution 함수를 완성해보세요.

입출력 예시

풀이 방법

다양한 문제로 풀수가 있는데 나는 math 모듈의 gcd() 함수를 사용했다. math 모듈은 거의 쓴 적이 없어서 최대공약수 구하는 방법을 찾아보다가 gcd() 함수를 알게 되었다.

from math import gcd

def solution(numer1, denom1, numer2, denom2):
    numerator = (denom1*numer2) + (numer1*denom2) 
    denominator = (denom1*denom2)
    gcd_value = gcd(numerator, denominator)
    answer = [numerator/gcd_value, denominator/gcd_value]
    return answer

개념

최대공약수 GCD(Greatest Common Divisor)
최소공배수 LCM(Least Common Multiple)
유클리드 호제법 : 2개의 자연수 또는 정식(整式)의 최대공약수를 구하는 알고리즘

2개의 자연수(또는 정식) a, b에 대해서 a를 b로 나눈 나머지를 r이라 하면(단, a>b), a와 b의 최대공약수는 b와 r의 최대공약수와 같다. 이 성질에 따라, b를 r로 나눈 나머지 r'를 구하고, 다시 r을 r'로 나눈 나머지를 구하는 과정을 반복하여 나머지가 0이 되었을 때 나누는 수가 a와 b의 최대공약수이다. (a, b) = (b, r) r은 a를 b로 나눈 나머지
https://ko.wikipedia.org/wiki/%EC%9C%A0%ED%81%B4%EB%A6%AC%EB%93%9C_%ED%98%B8%EC%A0%9C%EB%B2%95

그 외의 다른 풀이

• 모듈을 사용하지 않고 최대공약수를 구하는 방법
• fractions 모듈을 사용하는 방법