[프로그래머스] 분수의 덧셈 풀이 (Python3)

Sage·2023년 2월 27일
0

코테 풀이

목록 보기
1/5

[프로그래머스] 분수의 덧셈 - 문제 페이지

  • 직접 작성하여 해결한 파이썬 코드입니다. 더 나은 풀이가 존재할 수 있습니다.
  • 유클리드 호제법을 활용한 방법입니다. 증명이 궁금하면 아래 링크에서 확인하실 수 있습니다. 복잡하진 않습니다.
    위키백과 - 유클리드 호제법
  • 유클리드 호제법의 핵심
    - GCD(a, b) = GCD(b, a%b)
    - a와 b의 최대공약수 = b와 (a를 b로 나눈 나머지)의 최대공약수
    - GCD: 최대공약수 (Greatest Common Divisor)

Q) 2개의 분수를 더한 값을 기약 분수로 표현하기

def gcd(num1, num2):
    if num1<num2:
        num1, num2 = num2, num1
    while num1%num2 != 0:
        remainder = num1%num2
        num1 = num2
        num2 = remainder
    return num2

def solution(numer1, denom1, numer2, denom2):
    denom_gcd = gcd(denom1, denom2)
    sum_denom = denom_gcd * (denom1//denom_gcd) * (denom2//denom_gcd)
    sum_numer = numer1*(sum_denom//denom1) + numer2*(sum_denom//denom2)
    
    sum_gcd = gcd(sum_numer, sum_denom)
    sum_numer //= sum_gcd
    sum_denom //= sum_gcd
    answer = [sum_numer, sum_denom]
    return answer
  • 실행 결과
  • 해설
    - gcd(num1, num2) → 최대공약수를 구하는 함수
    - 나눗셈에서의 몫: quotient, 나머지: remainder
    - 분수의 분자: numerator, 분모: denominator
profile
Wanna know everything I need

0개의 댓글