0. 문제 설명 - 코테 문제를 풀다가 갑자기 기약분수가 튀어나왔다.. 너무 오랜만에 보는 단어라 순간 기약분수가 뭐지..? 하고 검색해봤는데 초등학교 5학년 때 배우는 수학.. ㅋㅋ 다 까먹었다 🤣 - 손으로 풀라하면 풀 수 있는데 이걸 코딩으로 구현해야 하니 막막함이 올라왔다.. 그래서 구글링 후 유클리드 호제법이라는 알고리즘을 학습! 1. 유클리드 호제법이란? - 두 양의 정수, 혹은 두 다항식의 최대공약수를 구하는 방법 - 2개의 자연수(또는 정식) a, b에 대해서 a를 b로 나눈 나머지를 r이라 하면(단, a>b), a와 b의 최대공약수는 b와 r의 최대공약수와 같다. 이 성질에 따라, b를 r로 나눈 나머지 r'를 구하고, 다시 r을 r'로 나눈 나머지를 구하는 과정을 반복하여 나머지가 0이..