염딩코

[문제] & [결과] [해설] 이 문제는 백준 2609번 문제에 나왔던 유클리드 호제법을 이용해 최대공약수를 먼저 구해야한다. 최소공배수는 두 수를 곱하고 최대공약수로 나누면 얻을 수 있기 때문이다. 그래서 gcd라는 함수를 만들어 두 정수를 매개변수로 받는다. 이전 게시글 중 2609번을 참고하면 gcd, 최대공약수에 대한 추가 설명이 있다. 그렇게 최대공약수를 반환하고 반환된 값을 곱한 두 수로부터 나누면 최소공배수를 얻을 수 있다.

[문제] [결과] [해설] 유클리드 호제법(유클리드 알고리즘)은 2개의 자연수 또는 정식의 최대공약수를 구하는 알고리즘의 하나이다. 호제법이란 두 수가 서로 상대방의 수를 나누어서 결과적으로 원하는 수를 얻는 알고리즘을 의미한다. 원리는 이렇다. 큰 수를 작은 수로 나눈다 -> 나누는 수를 나머지로 계속 나눈다 -> 나머지가 0이 나올 때까지 반복한다. -> 나머지가 0이 나온다면, 그때 나누는 수가 최대공약수이다.