최대공약수와 최소공배수 구하기

1. 최대공약수와 최소공배수의 개념 소개

최대공약수(Greatest Common Divisor, GCD)와 최소공배수(Least Common Multiple, LCM)는 두 개 이상의 수에 대해 자주 사용되는 개념입니다. 각각 두 수의 공통된 약수 중 가장 큰 수와 공통된 배수 중 가장 작은 수를 나타냅니다.

최대공약수(GCD)

두 수의 최대공약수는 두 수를 모두 나눌 수 있는 가장 큰 정수입니다. 즉, 어떤 수 A와 B의 최대공약수를 GCD(A, B)로 표기합니다. 최대공약수를 구하는 가장 일반적인 방법은 유클리드 호제법을 사용하는 것입니다. 유클리드 호제법은 두 수를 나누어가며 나머지가 0이 될 때까지 반복하여 나머지가 0이 되었을 때의 나누는 수가 최대공약수가 됩니다.

최소공배수(LCM)

두 수의 최소공배수는 두 수를 모두 나눌 수 있는 가장 작은 정수입니다. 즉, 어떤 수 A와 B의 최소공배수를 LCM(A, B)로 표기합니다. 최소공배수를 구하는 가장 일반적인 방법은 최대공약수를 활용하는 것입니다. 두 수의 최소공배수는 두 수를 곱한 값에 최대공약수로 나누어 준 것과 같습니다. 따라서 다음과 같이 표현할 수 있습니다.

LCM(A, B) = (A * B) / GCD(A, B)

최대공약수와 최소공배수는 수학 문제뿐만 아니라 프로그래밍에서도 다양한 문제를 해결하는 데 활용됩니다. 알고리즘 문제를 푸는 과정에서 최대공약수와 최소공배수를 구하는 기능은 자주 사용되므로 알고있는 것이 유용합니다.

2. 최대공약수 구하는 방법

최대공약수(GCD)를 구하는 가장 일반적인 방법은 유클리드 호제법(Euclidean algorithm)을 사용하는 것입니다. 유클리드 호제법은 대표적인 재귀 알고리즘으로, 두 수의 최대공약수를 구하는 데 효과적입니다.

유클리드 호제법

두 수 A와 B의 GCD를 구하는 과정은 다음과 같습니다.

1. A를 B로 나눈 나머지를 구합니다. 이를 R이라고 합시다.
2. R이 0이라면, B가 최대공약수입니다. 즉, GCD(A, B) = B가 됩니다.
3. R이 0이 아니라면, B를 R로 나눈 나머지를 구합니다. 이를 새로운 B로 정합니다.
4. 2번 과정부터 반복합니다.

반복을 진행하다가 R이 0이 되는 순간, 그때의 B가 최대공약수가 됩니다. 이 알고리즘의 핵심은 A와 B의 최대공약수는 B와 R의 최대공약수와 같다는 점입니다.

예시

두 수 36과 24의 최대공약수를 구하는 과정을 예시로 들어보겠습니다.

1. 36을 24로 나눈 나머지는 12입니다.
2. 12를 24로 나눈 나머지는 0입니다. 따라서 최대공약수는 24입니다.

따라서 GCD(36, 24) = 24가 됩니다.

위 예시와 같이 유클리드 호제법은 나머지 연산을 사용하여 두 수를 점차적으로 줄여나가는 방법이므로, 두 수가 매우 큰 경우에도 효과적으로 최대공약수를 계산할 수 있습니다.

3. 최소공배수 구하는 방법

두 수의 최소공배수(LCM)를 구하는 가장 일반적인 방법은 최대공약수(GCD)를 활용하는 것입니다. 최소공배수는 두 수의 곱에 최대공약수를 나눈 값과 같습니다.

최소공배수 구하는 공식

최소공배수(LCM)를 구하는 공식은 다음과 같습니다.

LCM(A, B) = (A * B) / GCD(A, B)

따라서 두 수 A와 B의 최소공배수를 구하기 위해서는 다음과 같은 단계를 따릅니다.

1. 두 수 A와 B의 최대공약수(GCD(A, B))를 구합니다.
2. 두 수 A와 B를 곱한 값(A * B)을 최대공약수로 나눕니다. 이 값이 최소공배수입니다.

예시

두 수 12와 20의 최소공배수를 구하는 과정을 예시로 들어보겠습니다.

1. 최대공약수 GCD(12, 20)를 구합니다. 유클리드 호제법을 사용하여 GCD(12, 20) = 4입니다.
2. 최소공배수 LCM(12, 20) = (12 * 20) / GCD(12, 20) = 240 / 4 = 60입니다.

따라서 두 수 12와 20의 최소공배수는 60이 됩니다.

위와 같이 최소공배수는 두 수의 곱에 최대공약수를 나누어줌으로써 구할 수 있습니다. 이를 활용하여 더 많은 수들의 최소공배수도 계산할 수 있습니다.

4. 최대공약수와 최소공배수의 활용 예시

최대공약수와 최소공배수는 수학적으로 중요한 개념이며, 다양한 문제에서 유용하게 활용될 수 있습니다. 아래 예시를 통해 최대공약수와 최소공배수의 활용 방법을 살펴보겠습니다.

예시 1: 분수의 기약분수화

두 수 A와 B의 최대공약수를 구하는 것은 주어진 분수를 기약분수로 화하는 데에 사용될 수 있습니다. 분모와 분자의 최대공약수를 구하여, 둘을 나누면 기약분수가 됩니다. 예를 들어, 분수 6/15의 최대공약수를 구하면 GCD(6, 15) = 3입니다. 따라서 6/15은 2/5로 기약분수로 화할 수 있습니다.

예시 2: 분수의 사칙연산

두 분수의 덧셈, 뺄셈, 곱셈, 나눗셈을 하기 전에, 분모와 분자를 기약분수로 화해야 할 수도 있습니다. 이때 최소공배수를 활용하여 분모의 공통 분모를 구할 수 있습니다. 예를 들어, 3/4와 2/5를 더하기 위해 최소공배수 LCM(4, 5) = 20을 구하고, 분모를 20으로 맞추어 계산할 수 있습니다.

예시 3: 배수 구하기

두 수의 최소공배수는 두 수의 공통 배수 중에서 가장 작은 값입니다. 따라서 두 수의 배수를 구할 때에도 최소공배수를 활용할 수 있습니다. 예를 들어, 3과 4의 배수를 구하고 싶다면, 최소공배수 LCM(3, 4) = 12의 배수를 구하면 됩니다.

예시 4: 시간 계산

최대공약수와 최소공배수는 시간 단위를 계산하는 데에도 사용될 수 있습니다. 예를 들어, A와 B가 각각 속도로 움직이고 있다고 할 때, 두 가지 속도가 동시에 반복되는 최소한의 시간 단위를 구하고자 한다면, A의 주기와 B의 주기의 최소공배수를 계산하면 됩니다.

위 예시들처럼 최대공약수와 최소공배수는 다양한 문제에서 유용하게 활용될 수 있습니다. 이러한 개념을 잘 이해하고 숙지하여 수학적인 문제를 효과적으로 해결할 수 있습니다.

5. 최대공약수와 최소공배수 구하는 알고리즘

최대공약수와 최소공배수를 구하기 위해서는 다양한 알고리즘들이 존재합니다. 아래에서는 가장 기본적인 알고리즘인 유클리드 호제법을 통해 최대공약수와 최소공배수를 구하는 방법을 소개하겠습니다.

유클리드 호제법

1. 입력으로 받은 두 수 A와 B 중 A가 B보다 크다고 가정합니다. 만약 A가 B보다 작다면 A와 B를 서로 바꿔줍니다.
2. A를 B로 나눈 나머지 R을 구합니다.
3. R이 0이 되면, B가 최대공약수입니다. 이때 B의 값이 0이면 A가 최대공약수입니다.
4. R이 0이 아니라면, B를 A로, R을 B로 바꿔줍니다. 그리고 다시 2단계로 돌아가 R이 0이 될 때까지 반복합니다.

위 알고리즘을 통해 최대공약수(GCD)를 구한 후, 최소공배수(LCM)는 다음과 같은 공식을 활용하여 계산할 수 있습니다.

• LCM(A, B) = (A * B) / GCD(A, B)

예시

두 수 18과 24의 최대공약수와 최소공배수를 구하는 과정을 예시로 들어보겠습니다.

1. A = 24, B = 18로 가정합니다.
2. 24를 18로 나눈 나머지는 6입니다.
3. 6을 B로, B를 나머지인 6으로 대체합니다.
4. 18을 6으로 나눈 나머지는 0이므로, 최대공약수는 6입니다.
5. 최소공배수는 (18 * 24) / 6 = 72입니다.

따라서 두 수 18과 24의 최대공약수는 6이고, 최소공배수는 72입니다.

유클리드 호제법은 재귀 함수를 사용하여 구현할 수도 있으며, 성능적으로도 우수한 알고리즘입니다. 따라서 최대공약수와 최소공배수를 구하는 알고리즘으로 가장 많이 사용되고 있습니다.