최소공배수

백준 1934 풀이 (최소공배수, 유클리드 호제법)

저번 2609문제에서 최대공약수와 최소공배수를 구했다. 이번에는 최소 공배수만 구하는 문제이기 때문에 저번에 사용했던 코드를 재활용해주면 아주 쉽게 구할 수 있다. 최소 공배수를 노가다로 구하게 되면 불필요한 연산이 너무 많아진다. 따라서 최대 공약수를 유클리드 호제법으로 구하고 이후에 최소 공배수를 구하는 방식이 효율적이다. 따라서 저번에 활용한 코드를 재활용하는 것이다. 그냥 함수로 묶어 주기만 하면 된다. n = int(input()) def find(tmp): if tmp[0] < tmp[1]: t = tmp[0] tmp[0] = tmp[1] tmp[1] = t a = tmp[0] b = tmp[1] # get 공약수 yak = 0 while 1: c = tmp[0] % tmp[1] tmp[0] ..

백준 2609 풀이 (최대공약수와 최소공배수, 유클리드 호제법)

쉬운문제였다. 물론 한번 틀려서 유클리드 호제법 공부하고 왔다. 처음에는 a와 b중에 작은 수에서 1씩 빼면서 둘다 나누어 떨어지는지 확인하는 방식을 통해 최대 공약수를 구하려고 했다. 물론 그 방법이 틀렸다고는 할 수 없지만, 문제는 시간도 오래걸리고 좋은 방법 같지 않았다. 그래서 찾아보니 유클리드 호제법이라는 엄청난 방법이 있었다. (a,b)가 존재할때 a%b를 하여 나머지를 계속해서 나누어주는 방법이다. (24, 18) => 24 % 18 = 6 (18, 6) => 18 % 6 = 0 (6, 0) => 최대 공약수는 6 이러한 방식으로 몇개의 연산으로 최대 공약수를 찾을 수 있는 것이다. 기존보다 연산의 횟수가 획기적으로 줄어들게 된다. 요 방식으로 최대 공약수를 찾으면 최소 공배수는 쉬워진다. ..