[프로그래머스][C++] 분수의 덧셈
분수의 덧셈
문제 링크
분석
두 분수를 더한 값을 최대공약수로 나눠 기약 분수를 반환하는 문제입니다.
우선 두 분수의 합은 다음과 같이 구합니다.
$ \frac {a}{b} \times \frac{c}{d} = \frac {a \times d + c \times b}{b \times d} $
입출력 예#1을 대입해보면 다음과 같은 식이 나옵니다.
$ \frac {1}{2} \times \frac{3}{4} = \frac {1 \times 4 + 3 \times 2}{2 \times 4} $
이제 이 식을 더하면 다음과 같은 값이 나옵니다.
$ \frac {4 + 6}{8} = \frac{10}{8} $
이 값을 최대 공약수로 나눈다면 기약분수가 될겁니다.
최대공약수를 구하는 방법은 값을 하나씩 확인하거나 유클리드 호제법을 사용하여 찾을 수 있습니다.
값을 하나씩 확인하는 방법은 숫자를 2에서부터 1씩 증가시키거나, 두 값 중 작은 값에서 1씩 감소시키며 찾을 수 있습니다.
유클리드 호제법은 C++17이상에서 std::gcd를 사용할 수 있지만, 해당 함수는 사용하지 않고 직접 구현하고, 문제를 풀어보겠습니다.
유클리드 호제법의 구현은 반복문을 사용하거나 재귀호출을 사용하여 구현할 수 있습니다.
우선 유클리드 호제법을 설명하기 전에 mod(modulo)연산에 대해 이해해야 합니다.
mod연산은 나머지 연산으로 C++의 %의 연산자와 같은 역할을 합니다.
즉, mod연산은 두 수를 나눈 나머지를 구하는 연산입니다.
유클리드 호제법이란 두 수의 최대공약수(GCD)를 구하는 알고리즘입니다.
두 수 A와 B에서 A > B일 경우로 가정하겠습니다.
A를 B로 나눈 나머지 R을 구합니다.
이때, R이 0일 경우 최대공약수입니다.
이때, R이 0이 아닐 경우 A를 B로 바꾸고 B를 R로 바꿔서 반복합니다.
예시를 들어보겠습니다.
$A = 12, B = 8$
$12 \mod 8 = 4$
$8 \mod 4 = 0$
최대 공약수는 4입니다.
이렇게 나머지가 0이 될 때까지 반복하며, 마지막에 남은 나누는 수가 최대 공약수입니다.
그럼 최대 공약수를 구하고, 나누면 다음과 같은 결과값이 나옵니다.
$ \frac{10}{8} \div 2 = \frac{5}{4} $
풀이
최대공약수를 찾을 때 값을 하나씩 확인하는 방법을 사용한 풀이입니다.
#include <vector>
std::vector<int> solution(int numer1, int denom1, int numer2, int denom2) {
std::vector<int> answer;
int numerator = numer1 * denom2 + numer2 * denom1;
int denominator = denom1 * denom2;
for (int i = std::min(denominator, numerator); i >= 2; i--)
{
if (denominator % i == 0 && numerator % i == 0)
{
denominator /= i;
numerator /= i;
break;
}
}
answer.push_back(numerator);
answer.push_back(denominator);
return answer;
}
int numerator = numer1 * denom2 + numer2 * denom1;와 int denominator = denom1 * denom2;는 분수의 합을 구합니다.
std::min(denominator, numerator)는 2에서부터 1씩 증가하며 찾는 것 보다 분모와 분자 중 작은 수를 찾아 1씩 작아지는게 좀 더 빠르게 찾을 수 있기 때문에 이렇게 작성했습니다.
만약 2에서부터 찾을경우 모든 공약수를 확인해야하지만, 뒤에서부터 찾을 경우 처음 찾은 공약수가 최대공약수입니다.
i >= 2는 i가 1이면 반복문을 할 필요가 없기 때문입니다.
denominator % i == 0 && numerator % i == 0 이것은 분자와 분모의 나머지가 0이된다면 최대공약수를 찾은것입니다.
이후 if문의 바디에서 반환할 값을 저장하고, for문에서 탈출합니다.
반복문을 사용하여 유클리드 호제법을 구현한 풀이는 다음과 같습니다.
#include <vector>
std::vector<int> solution(int numer1, int denom1, int numer2, int denom2) {
std::vector<int> answer;
int numerator = numer1 * denom2 + numer2 * denom1;
int denominator = denom1 * denom2;
int a = numerator;
int b = denominator;
while (b != 0) {
int temp = b;
b = a % b;
a = temp;
}
int gcdResult = a;
numerator /= gcdResult;
denominator /= gcdResult;
answer.push_back(numerator);
answer.push_back(denominator);
return answer;
}
반복문을 돌면서 최대공약수를 찾고, 최대공약수로 기약분수를 만든 후 반환값을 저장합니다.
a는 나누어지는 수이므로 초기화에 numerator값을 가져야합니다.
b는 a를 나누는 수이므로 denominator의 값을 가져야합니다.
while문에서 b는 나누는 수이므로 나누는 수가 0이라면 최대공약수를 찾았으므로 탈출 조건에 해당됩니다.
b는 다음 반복문에서 나누어지는 수가 되므로 temp에 저장해두어야 합니다.
a % b 연산을 수행해 최대공약수를 찾고, 값을 b에 저장합니다.
다음 연산을 위해 a에 나누어지는 수를 저장한 temp의 값을 저장합니다.
while문이 끝난 후 최대공약수를 구했으므로, 기약분수를 만들어준 후 반환값을 저장합니다.
재귀함수를 사용하여 유클리드 호제법을 구현한 풀이는 다음과 같습니다.
#include <vector>
int GetGCD(int a, int b) {
if (a % b == 0)
{
return b;
}
return GetGCD(b, a % b);
}
std::vector<int> solution(int numer1, int denom1, int numer2, int denom2) {
std::vector<int> answer;
int numerator = numer1 * denom2 + numer2 * denom1;
int denominator = denom1 * denom2;
int gcdResult = GetGCD(numerator, denominator);
numerator /= gcdResult;
denominator /= gcdResult;
answer.push_back(numerator);
answer.push_back(denominator);
return answer;
}
GetGCD 함수가 재귀함수이므로 반환값인 최대공약수로 기약분수를 만들어주고 반환값을 저장합니다.
성능 요약
최대공약수를 찾을 때 값을 하나씩 확인하는 방법의 성능은 다음과 같습니다.
해당 방법은 브루트 포스(Brute Force)알고리즘이며, 가능한 모든 경우를 하나씩 검사하는 방식입니다.
시간 복잡도는 $O(N)$입니다.
테스트 1 〉 통과 (0.30ms, 4.2MB)
테스트 2 〉 통과 (0.01ms, 4.21MB)
테스트 3 〉 통과 (0.01ms, 4.13MB)
테스트 4 〉 통과 (0.01ms, 4.18MB)
테스트 5 〉 통과 (0.01ms, 4.14MB)
테스트 6 〉 통과 (0.01ms, 4.14MB)
테스트 7 〉 통과 (0.04ms, 3.68MB)
테스트 8 〉 통과 (0.64ms, 4.19MB)
테스트 9 〉 통과 (0.54ms, 4.14MB)
테스트 10 〉 통과 (0.88ms, 4.21MB)
테스트 11 〉 통과 (0.01ms, 4.14MB)
테스트 12 〉 통과 (0.01ms, 4.13MB)
테스트 13 〉 통과 (0.01ms, 3.67MB)
테스트 14 〉 통과 (0.02ms, 4.14MB)
테스트 15 〉 통과 (0.02ms, 4.14MB)
유클리드 호제법의 시간 복잡도는 $O(Log\;N)$으로 매우 빠른 알고리즘에 속합니다.
반복문을 사용하여 유클리드 호제법을 구현한 성능은 다음과 같습니다.
테스트 1 〉 통과 (0.01ms, 3.66MB)
테스트 2 〉 통과 (0.01ms, 4.13MB)
테스트 3 〉 통과 (0.01ms, 4.2MB)
테스트 4 〉 통과 (0.01ms, 4.18MB)
테스트 5 〉 통과 (0.01ms, 4.16MB)
테스트 6 〉 통과 (0.01ms, 4.14MB)
테스트 7 〉 통과 (0.01ms, 4.2MB)
테스트 8 〉 통과 (0.01ms, 4.17MB)
테스트 9 〉 통과 (0.01ms, 4.14MB)
테스트 10 〉 통과 (0.01ms, 4.02MB)
테스트 11 〉 통과 (0.01ms, 4.14MB)
테스트 12 〉 통과 (0.01ms, 4.2MB)
테스트 13 〉 통과 (0.01ms, 3.61MB)
테스트 14 〉 통과 (0.01ms, 4.14MB)
테스트 15 〉 통과 (0.01ms, 4.14MB)
재귀함수를 사용하여 유클리드 호제법을 구현한 성능은 다음과 같습니다.
테스트 1 〉 통과 (0.01ms, 4.2MB)
테스트 2 〉 통과 (0.01ms, 4.13MB)
테스트 3 〉 통과 (0.01ms, 4.2MB)
테스트 4 〉 통과 (0.01ms, 4.21MB)
테스트 5 〉 통과 (0.01ms, 4.21MB)
테스트 6 〉 통과 (0.01ms, 4MB)
테스트 7 〉 통과 (0.01ms, 4.2MB)
테스트 8 〉 통과 (0.01ms, 4.16MB)
테스트 9 〉 통과 (0.01ms, 4.21MB)
테스트 10 〉 통과 (0.01ms, 4.17MB)
테스트 11 〉 통과 (0.01ms, 3.67MB)
테스트 12 〉 통과 (0.01ms, 4.01MB)
테스트 13 〉 통과 (0.01ms, 4.14MB)
테스트 14 〉 통과 (0.01ms, 4.2MB)
테스트 15 〉 통과 (0.01ms, 4.02MB)
댓글남기기