[프로그래머스] 분수의 덧셈 : 유클리드 호제법

코딩테스트 입문
Day 3 - 2023.01.03

문제 설명

첫 번째 분수의 분자와 분모를 뜻하는 denum1, num1, 두 번째 분수의 분자와 분모를 뜻하는 denum2, num2가 매개변수로 주어진다. 두 분수를 더한 값을 기약 분수로 나타냈을 때 분자와 분모를 순서대로 담은 배열을 return 하도록 solution 함수를 완성하라.

제한 사항

1. 정수 num1, denum1, num2, denum2이 0보다 크고 1,000보다 작아야 한다.

문제 풀이

분수의 덧셈.swift

import Foundation

func solution(_ denum1: Int, _ num1: Int, _ denum2: Int, _ num2: Int) -> [Int] {
    // 제한 사항
	guard (1...999 ~= denum1), (1...999 ~= num1), (1...999 ~= denum2), (1...999 ~= num2) else
	{ return [-1] }
    
    // 문제 풀이
    var denum = (denum1 * num2) + (denume2 * num1)
    var num = (num1*num2)
    
    
    // 최대공약수(Greatest Common Factor)
    var denumGcf = denum
    var numGcf = num
    
    // 유클리드 호제법
    while(numGcf != 0) {
        var mod = denumGcf % numGcf
        denumGcf = numGcf
        numGcf = mod
    }
    
    // 최대 공약수 및 약분
    let gcf = denumGcf
    denum = denum / gcf
    num = num / gcf
    
    return [denum, num]
}

문제에서 주어진 soultion 함수와 num1, denum1, num1, denum2 , result를 변수 이름을 그대로 사용하였다.

먼저 guard문을 이용하여 제한사항을 설정해주고, 범위연산자(~=) 를 사용하여 가독성을 높이며 return 값으로 [-1]을 반환하였다.

이후 문제는 분자(denum1) / 분모(num1)와 분자(denum2) / 분모(num2)의 덧셈을 구하는 문제로 통분을 하여 분모를 num에 통분하여 더한 분자를 denum에 저장하였다.

    // 문제 풀이
    var denum = (denum1 * num2) + (denume2 * num1)
    var num = (num1*num2)
    
    
    // 최대공약수(Greatest Common Factor)
    var denumGcf = denum
    var numGcf = num

이후 최대공약수를 구하는 유클리드 호제법을 이용하여 약분하여 분모 분자값을 넘겨주었다.

    // 유클리드 호제법
    while(numGcf != 0) {
        var mod = denumGcf % numGcf
        denumGcf = numGcf
        numGcf = mod
    }
    
    // 최대 공약수 및 약분
    let gcf = denumGcf
    denum = denum / gcf
    num = num / gcf
    
    return [denum, num]
}

소인수분해

일반적으로 최대공약수를 구하기 위해서는 소인수분해를 해야한다.

28 = 7 * 2 * 2

24 = 3 * 2 * 2 * 2

두 공통된 소수 2 * 2 : 최대공약수 = 4 

두 수의 소인수분해한 후 공통된 소수를 찾아 곱한 것이 최대공약수가 된다.
다만, 수가 커질수록 소인수분해를 하기 어려운 단점이 있다.

유클리드 호제법

유클리드 호제법은 2개의 자연수 또는 정식의 최대공약수를 구하는 알고리즘이다.

호제법이란 두 수가 서로 상대 수를 나누어서 결국 원하는 수를 얻는 알고리즘으로이다.

2개의 자연수 a, b에 대하여 a를b로 나눈 나머지를 r이라고 하면 (단, a > b)
a와 b의 최대공약수는 b와 r의 최대공약수와 같다.

이 성질에 따라 b를 r로 나눈 나머지 r'을 구하고, 다시 r을 r'로 나누는 과정을 반복하여 나머지가 0이 되었을 때 나누는 수가 a와 b의 최대공약수다.

유클리드 호제법 예시

1240과 1030의 최대공약수를 구하고자 한다.

• 1240은 1030으로 나누어 떨어지지 않고 나머지는 210이다.
• 1030은 210으로 나누어 떨어지지 않고 나머지는 190이다.
• 210은 190으로 나누어 떨어지지 않고 나머지는 20이다.
• 190은 20으로 나누어 떨어지지 않고 나머지는 10이다.
• 20은 10으로 나누어 떨어지기 때문에 최대공약수는 10이 된다.