최대공약수, 최소공배수 구하기 #1 - 코딩수업#18
앞서 배웠던 문제 풀이의 방법과 마찬가지로 컴퓨터의 빠른 처리속도와 반복 작업을 이용하여 간단한 수학 문제 풀이 두 가지에 도전해 보자.
두 개의 숫자를 입력하고, 이 두 숫자의 최대 공약수와 최소 공배수를 구하는 간단한 문제이다.
반복과 비교라는 두 가지 기법을 이용하여 이 문제를 풀어보자.
1. 최대공약수 구하기
최대공약수는 두 개의 숫자를 나누었을 때 나머지 없이 나눌 수 있는 가장 큰 수이다.
구하는 방법은 두 숫자 중 작은 숫자를 골라서 1씩 줄여가며 자기 자신을 나누어 보고 나누어지면, 이 숫자가 큰 숫자도 나눌 수 있는지 확인하여 이를 최대 공약수로 답을 찾으면 된다.
예) 아래의 그림과 같이, 두 숫자 480과 270 이 있다고 하자.
step #1
- 두 숫자 중 작은 숫자를 고른다. 480 > 270 이므로 270이 선택되었다.
step #2
- 270 은 스스로를 나눌 수 있으므로 이를 가지고 큰 숫자 480을 나누어 본다.
몫 1과 나머지 210이 남으므로 나누어지지 않는다.
step#3
- 숫자 270을 나누기 위한 가장 큰 수는 그 절반인 숫자 이므로 그 절반인 숫자 135를 구한다.
만일 그 숫자가 홀수일 경우 소수점 아래는 버려도 된다.
step#4
- 구해진 135로 작은 숫자인 270을 나누어 보고 나누어지면 큰 숫자 480도 나누어 본다.
270은 당연히 나누어지지만 480은 나눌 수 없다.
step#5
- 135가 보관된 변수에서 1을 줄이고 이를 가지고 step#4를 반복한다.
두 숫자가 모두 나누어지면 이 변수의 값이 최대 공약수이고 아니면 다시 step#4를 반복한다.
step#4를 반복하고 이를 확인하는 작업을 통하여 최대 공약수를 구할 수 있다.
270과 480의 최대공약수 구하기2. 최소공배수 구하기
최소공배수는 두 개의 숫자로 나눌 수 있는 가장 작은 숫자이다.
구하는 방법은 두 개 중 큰 숫자의 가장 작은 배수를 구하고 이 배수가 작은 숫자로도 나누어지는 지를 찾아보고, 두 개의 숫자 모두가 나눌 수 있으면 이 숫자가 최소 공배수가 되는 형식으로 답을 찾을 수 있다.
예) 아래의 그림과 같이, 두 숫자 480과 270 이 있다고 하자.
step #1
- 두 숫자 중 큰 숫자를 고른다. 480 > 270 이므로 480이 선택되었다.
큰 숫자를 고르는 이유는 두 숫자의 공통 배수 중 큰 숫자의 배수를 순서대로 찾아가는 것이 작은 숫자의 배수를 순서대로 찾아가는 단계보다 적을 것이기 때문이다.
step #2
- 480의 1 배수인 480이 270으로 나누어지는 지를 확인한다.
나누어지면 480이 최소공배수가 되겠지만 나누어지지 않으므로 다음 단계로 간다.
step #3
- 배수를 1 증가시킨다.
- 480의 증가된 배수(처음의 경우 2 배수인 960)가 270으로 나누어지는 지를 확인한다.
step #4
- 나누어지지 않으면 480의 다음 배수로 동일한 검증을 반복하기 위하여 step#3을 반복한다.
나누어지면 이 숫자가 최소 공배수이다.
아래의 그림을 통하여 최소 공배수를 구하는 방법을 확인해 보자.
이제 다음 수업에서 위의 그림을 코드로 옮겨 보자.
