코.알.못 홍 기자의 코딩 도전기
코딩의 ‘코’자도 모르는 코.알.못. 홍 기자가 수학 문제를 코딩으로 푸는 오일러 프로젝트 문제를 하나하나 해결해 나갈 예정입니다. 오일러 프로젝트는 수학과 프로그래밍 실력을 모두 키울 수 있도록 2001년에 만든 수학 문제 웹사이트로, 수학 문제를 프로그래밍으로 해결하는 게 목적이지요. 홍 기자와 함께 한다면 수학과 파이썬 모두 정복할 수도…? 같이 한번 풀어봐요!
‘전대미문의 진짜 재난을 만나다!’
영화 ‘엑시트’는 유독가스 테러에서 살아남기 위한 두 주인공의 모습을 그립니다. 탈출이라는 목표 하나로 온갖 기지를 발휘해 고비를 넘고 또 넘죠. 홍 기자의 코딩 도전기에도 재난급 오일러 프로젝트 문제가 등장했습니다. 이 문제를 해결하고 코딩 왕초보를 탈출할 수 있을까요?
<오일러 프로젝트 5번 문제>
1~10 사이의 어떤 수로도 나눠떨어지는 가장 작은 수는 2520입니다.
그러면 1~20 사이의 어떤 수로도 나눠떨어지는 가장 작은 수는 얼마일까요?
이번 문제는 두 수의 공통 배수 중 가장 작은 값인 '최소공배수'를 구하는 문제입니다. 하지만 파이썬에서는 최소공배수를 구하는 명령어를 지원하지 않죠. 다만 최대공약수를 구하는 명령어는 있어서 이를 이용해 구해야합니다. 자연수 a, b가 있을 때, 두 수의 최대공약수와 최소공배수 사이의 관계식을 이용하면 해결할 수 있죠. 아래의 관계식을 코딩으로 표현해 문제를 풀어봅시다!
a × b = 최대공약수 × 최소공배수
파이썬 완전정복! 필수 명령어
1. math 모듈 속 최대공약수(gcd) 함수 불러오기
두 수 a, b의 최대공약수를 구하는 함수는 gcd(a, b)입니다. 영어로 최대공약수(Greatest Common Divisor)의 앞글자를 따 gcd라고 쓰지요. 하지만 파이썬 표준 라이브러리에 이 명령어는 있지 않아서, 명령어가 포함된 모듈을 불러와야 쓸 수 있습니다. 파이썬에서 모듈을 불러오는 명령어는 ‘import’이고, gcd 함수는 math 모듈에 있으니 아래와 같이 씁니다.
이 코드를 실행하더라도 항상 모듈의 이름인 math를 gcd 앞에 붙여서 math.gcd(a, b)로 써야 합니다. 예를 들어 4와 6의 최대공약수를 구하려면 math.gcd(4, 6)으로 씁니다.
2. 최소공배수 구하는 함수 만들기
최소공배수는 영어로 Least 또는 Lowest Common Multiple로, 각 단어의 앞글자를 따 lcm이라고 씁니다. 불러온 gcd 함수를 이용해서 lcm 함수를 만들려면 새롭게 함수를 만드는 ‘def’ 명령어를 써야 합니다. 그다음 a, b의 곱을 최대공약수로 나눠 최소공배수를 구하는 lcm(a, b) 함수의 식을 ‘return’ 명령어를 써서 입력합니다.
TIP 1. 4, 6 대신 4.0과 6.0을 넣으면 어떻게 될까요? 역시나 파이썬이 오류를 뭉텅이로 내뱉습니다. 알고 보니 gcd 함수는 자연수라도 소수점 아랫수까지 표기해 넣으면 자연수라는 걸 모르는 함수였지 뭐예요?
TIP 2. 수학에서 나눗셈을 표현할 때 보통 ‘/’이나 ‘÷’ 기호를 씁니다. 하지만 이번에는 ‘//’를 사용했죠? /은 소수점 아랫수까지 있을 때 , //은 없을 때 쓰는 연산자예요. 따라서 a, b가 자연수여야 하는 이번 문제를 풀 때는 //를 써야만 하는 거죠. /를 쓰면 a, b가 자연수가 아닌 줄 알고 오류라고 떠요.
도전! 오일러 프로젝트 5번 문제 뽀개기
* 코딩 언어는 Python으로 두고 실행하세요!
#1. 최대공약수를 구하는 명령어가 담긴 math 모듈을 불러옵니다.
#2. 파이썬에 없는 최소공배수를 구하는 함수 lcm(a, b)를 새로 만듭니다.
#3. a×b = 두 수의 최소공배수 × 최대공약수라는 관계식을 이용해 lcm 함수를 정의합니다.
#4. 1부터 20까지 자연수의 최소공배수를 ‘ans’라는 변수로 나타내고, 1부터 시작합니다.
#5. ans의 초깃값이 1이므로 1은 제외하고, 2부터 20까지의 수를 i라는 변수로 나타냅니다. 이때 나타내는 범위는 (시작 숫자, 마지막 숫자+1)이므로 (2, 21)이 됩니다.
#6. ans와 i, 두 수 사이의 최소공배수를 구하는 함수를 이용해 1과 2의 최소공배수를 구하고, 그다음 1, 2의 최소공배수와 3의 최소공배수를 구하는 방식을 반복해 20까지 실행합니다.
#7. 1부터 20까지 자연수의 최소공배수를 출력합니다.
Bonus! 오일러 퀴즈
오일러 프로젝트 5번 문제를 위 코딩창에서 풀어보고, 다음 예제 문제에도 도전해 보세요!
1. 1부터 30까지 자연수들의 최소공배수는 얼마일까?
Hint ‘for i in range(2, 21):’에서 수를 바꿔보세요!
2. 두 수 a, b의 합을 구하는 함수를 def와 return을 이용해 만들어보자.
Hint ‘def lcm(a, b):’, ‘return (a * b) // math.gcd(a, b)’를 바꿔보세요!
혹시 더 좋은 코딩 아이디어가 있거나,
코딩을 빠르게 익힐 수 있는 좋은 방법이 있다면
댓글을 남겨 코.알.못 홍아름 기자를 도와주세요!
P. S., 오일러 프로젝트 1번 문제에서 썼던 명령어를 응용해, 정말 제가 직접 만든 코드입니다...(쭈굴)
답은 안나와요... 그러니 Evaluate 버튼 안누르셔도 됩니다... 왜 안 되는 걸까요!ㅜ.ㅜ
-
문제를 풀고 싶지만 제 코딩 실력이... 오일러 프로젝트 기사를 보고 올해 파이썬을 정복하겠습니다!
-
확인요청중
더 간단한 코드를 소개합니다.
원리는 거의 같습니다. 그러나 함수를 사용하지 않습니다.
같은 코드를 여러번 쓸 땐 함수가 편하지만, 이번처럼 함수를 1번만 쓸때는 함수를 안쓰는게 더 낫습니다.
코드는 다음과 같습니다.
import math
ans = 0
for i in range(2, 21):
ans = (i * ans) // math.gcd(i, ans)
print(ans)
(정답확인요청은 그냥 기자님 지식(?) 조금이라도 더 얻으시라고 한 것입니다.) -
역시 코딩은 대단하네요. 1부터 1000까지 2초 만에 구했습니다. 답은 아래 링크에서 보세요.
-
확인요청중
1. 1부터 30까지의 자연수의 최소공배수는 얼마일까?
import math
def lcm(a, b):
return (a * b) // math.gcd(a, b)
ans = 1
for i in range(2, 31):
ans = lcm(ans, i)
print(ans)을 계산 하면,
2329089562800 입니다.
2.두 수 a, b의 합을 구하는 함수를 def와 return을 이용해 만들어보자.
def add(a,b):
return a+b
로 하면 됩니다.
홍아름 기자님, 맨 아래있는 코드는 잘 작동 됩니다.
그러나 답이 나오는데 까지의 시간이 오래 걸립니다.
아무래도 기자님 컴퓨터에서는 너무나 오랜 시간(?) 이 걸려서 답이 안나오는 것 같습니다.
기자님 열심히 코딩 공부해서 오일러 프로젝트 정복합시다!!
-
아, 1부터 입력한 수까지의 최소공배수 코드는
import math
while True:
a = input('몇까지 구할까여?')
a = int(a)
a = a + 1
sum = 1
for i in range(1, a):
sum = sum * i // math.gcd(sum, i)
print(sum)
-
기자님, 이 코딩창 말고 파이썬 깔아서 보면 IDLE라고 있는데요, 거기에 코드 복붙해서 저장후 그거 더블클릭해 실행하면(cmd로) 돼요.
아, 참고로 중간에 공백은 다 지워야돼요) -
-
확인요청중
제가 오일러 프로젝트를 풀때 썼던 c언어 코드입니다. 입력한 수 까지 최소공배수를 구합니다.
#include<stdio.h>
int what(int a, int b)
{
int temp;
while (b)
{
temp = a % b;
a = b;
b = temp;}
return a;
}
int main()
{
int res=1;
int i=0;
int n=0;
printf("몇까지?:");
scanf("%d",&n);
for (i=1;i<=n;i++)
{
res*=i/what(res, i);
}
printf("%d", res);
}
