유클리드호제법 썸네일형 리스트형 기약분수, 서로소, 최대공약수(GCD), 유클리드 호제법, 추가) 최소공배수(LCM) 알고리즘 풀이중에 "기약분수로 출력하세요" 란 문제를 만났습니다. 수학용어들이 낮설게 다가옵니다. 기약분수(Irreducible fraction) 분자와 분모의 공약수가 1뿐이어서 더 이상 약분되지 않는 분수. 공약수가 1뿐인 두 수를 서로소 라고 함. 기약(旣約) : 이미 약분된 '그럼 a/b의 기약분수를 구하려면 둘 중 작은 수부터 1씩 줄여가면서 둘다 나누어 떨어지는 수로 나누어 가면 되겠다.' 라고 생각했다가, 그게 공약수일테고, 최대공약수(Greatest Common Divisor)를 구하면 되겠구나로 이어집니다. 1식 줄여가면서 둘다 나누어 떨어지는 첫번째 수가 최대공약수 이겠네요.. 그런데 이렇게 무식하게 처리하면.. 100,98의 경우는 최대공약수 2를 구하기 위해서 많은 계산을 하게 됩니.. 더보기 이전 1 다음