가치투자자

백준 2609번 : 최대공약수와 최소공배수 🔗 문제 링크 https://www.acmicpc.net/problem/2609 2609번: 최대공약수와 최소공배수 첫째 줄에는 입력으로 주어진 두 수의 최대공약수를, 둘째 줄에는 입력으로 주어진 두 수의 최소 공배수를 출력한다. www.acmicpc.net 💬 문제 최대공약수 와 최소공배수 에 대한 이해가 있다면, 충분히 풀 수 있는 문제다. 첫 번째 줄에 공백을 기준으로 두 개의 자연수(a, b)가 주어진다. 두 수의 최대 공약수와 최소 공배수를 구해 출력해준다. - a의 약수면서 b의 약수인 수 중에서 가장 큰 수가 최대공약수 다 - a의 배수면서 b의 배수인 수 중에서 가장 작은 수가 최소공배수 다 💡 입력값 받아오기 JavaScript로 풀 경우, 입력..

유클리드 호제법 (유클리드 알고리즘, Euclidean algorithm) 1. 유클리드 호제법이란? 유클리드 호제법 은 두 수 A와 B의 최대공약수를 구하는 알고리즘이다. 여기서 호제법 이란 두 수가 서로 상대방을 나누어 결국 원하는 수를 얻어내는 알고리즘을 말한다. 1-1. 일반적으로 최대공약수 구하기 보통 최대공약수를 구하기 위해 소인수분해 를 사용한다. 22와 8의 경우, 각각 소인수분해하여 최대공약수 2를 구할 수 있다. 22 = 11 x 2 8 = 2 x 2 x 2 그러나 이 방법의 경우, 숫자가 너무 크거나 숫자가 난해한 경우 소인수분해를 하기 어렵다. 1. 수가 너무 큰 경우 : 2304와 1440 => 최대공약수 288 2. 숫자가 난해한 경우 : 403과 155 => 최대공약수 31 이..