• 목록
  • 아래로
  • 위로

2021-10-31 01.33.27.jpg

실로 간만의 연재군요. 

 

타이틀 새로 그려야되는데 요즘 평일에는 다음날 일해야해서 그림을 못 그리고, 주말에는 귀찮아서 안 그립니다. 


1. GCD, LCM

영문 약자라서 이게 뭔 dog sound인가 싶으실텐데, 이거 최대공약수(GCD)랑 최소공배수(LCM)입니다. 초닥교때 다 배웠다 그죠? 근데 솔직히 까먹었다 그죠옹? 

 

약수는 어떤 수를 나머지 없이 나누는 수를 말합니다. 6의 약수는 1, 2, 3, 6이죠. 

공약수는 두 수의 공통된 약수를 말합니다. 6과 9의 공약수는 1, 3이죠. 그리고 최대공약수는 공약수 중에서 제일 큰 수입니다. 

배수는 어떤 수를 자연수로 곱하면 그게 배수입니다. 5, 10, 15, 20, 25,...는 전부 5의 배수죠. 

공배수는 두 수의 공통된 배수를 말합니다. 6과 9의 공배수는 18, 36, 54, ...입니다. 그리고 최소공배수는 공배수 중에서 제일 작은 공배수를 가리킵니다. 

 

반대되는 개념이 왜 없냐면 최소공약수는 1이고 최대공배수는 수가 끝이 없어서 없습니다. 

 

2. 유클리드 호제법? 

유클리드 호제법은 두 수를 서로(互) 나눠서(除) 최대공약수를 구하는 방법입니다. 기술된 알고리즘 중에서는 가장 오래된 알고리즘으로 알려져 있죠. 대충 호랑이 담배 배우던 시절에 나온겁니다. 

 

보통 최대공약수 구할 때 어떻게 하시나요? 

Untitled.png.jpg

그죠 초닥교때는 이렇게 했죠. 그리고 머리 좀 굵어지면 소인수분해로 구했다 그죠? 근데 생각해봅시다. 18과 30의 최대공약수는 얼마인가요? 하면 척수반사로 6! 하는데... 누가요 제가요 뜬금없이 210과 297의 최대공약수 이런거 물어보면 어떻게 하나요? 

 

jjvkx.jpg

질문자를 이러고 봅니다. 근데 우리가 유클리드 호제법을 알고 있다면 질문자를 이렇게 볼 필요가 없습니다. 

 

3. 어떻게 구하나요? 

제목_없음_-_2024년_1월_19일_22.20.23.jpg

위에서 두 수를 서로 나눠서 최대공약수를 구하는 방법이라고 했는데, 말 그대로입니다. 위 과정이 유클리드 호제법을 이용해서 210와 297의 최대공약수를 구하고 그걸 바탕으로 최소공배수를 계산하는 과정인데, 1번을 보면 297 = 210+87이죠? 그러면 이제 210을 87로 나누게 됩니다. 그래서 두번째 줄에서는 210을 87*2와 36으로 나타냈고, 세번째 줄에서는 87을 36과 15로, 그 다음 줄에서는 36을 15와 6으로, 또 그 다음 줄에서는 15를 6과 3으로, 그리고 마지막 줄에서는 6이 3의 배수이기 때문에 드디어 끝났습니다. 예. 그래서 210와 297의 최대공약수는 3이 되었습니다. 최소공배수는 최대공약수 구했으니까 나눠서 곱하면 됩니다. 

 

사실 297이 3의 배수이기때문에 일단 3은 끼고 들어가는 게 맞긴 합니다. 2+9+7=18이잖아요. 

 

제목_없음_-_2024년_1월_19일_22.20.23 (1).jpg

만약 어떤 수가 서로소라면 마지막 줄에서 0으로 나누어 떨어지지 않게 됩니다. 그래서 n * 1의 형태가 되는데 이렇게 나오면 두 수는 서로소인겁니다. 즉, 1025와 99는 서로소가 되겠습니다. (서로소: 두 수의 공약수가 1밖에 없는 수)

 

작성자
국내산라이츄 101 Lv. (89%) 830580/832320EXP

인생은 양자역학이외다

댓글 0

권한이 없습니다.
번호 제목 글쓴이 날짜 조회 수
46. 유클리드 호제법에 대해 알아보시츄 image 국내산라이츄 국내산라이츄 24.02.12.01:20 319
50 45. blue white screening에 대해 알아보시츄 image 국내산라이츄 국내산라이츄 23.06.11.22:40 2834
49 44. 지수와 로그츄 3 image 국내산라이츄 국내산라이츄 23.05.06.22:27 1345
48 특별편: 도덕책 자가검진키트의 원리는 무엇인가... image 국내산라이츄 국내산라이츄 23.04.29.00:30 2154
47 43. 산화와 환원에 대해 알아보시츄 1 image 국내산라이츄 국내산라이츄 23.04.25.00:36 469
46 42. 명제에 대해 알아보시츄 6 image 국내산라이츄 국내산라이츄 23.01.26.04:08 11470
45 41. 볼티모어 분류에 대해 알아보시츄 image 국내산라이츄 국내산라이츄 22.10.23.00:30 11680
44 40. SI 접두어에 대해 알아보시츄 (+IUPAC 접두어) 2 image 국내산라이츄 국내산라이츄 22.10.10.00:11 1512
43 39. 불 대수와 논리게이트에 대해 알아보시츄 image 국내산라이츄 국내산라이츄 22.09.26.02:18 1406
42 38. 감마퐝숀이었츄 1 image 국내산라이츄 국내산라이츄 22.04.25.23:41 3822
41 특별편: 저세상 코드 등⭐장 image 국내산라이츄 국내산라이츄 22.01.14.17:07 6510
40 37. VCF file image 국내산라이츄 국내산라이츄 22.01.06.14:56 7517
39 36. Bradford assay였츄 4 image 국내산라이츄 국내산라이츄 21.12.28.12:12 2439
38 35. FASTA와 FASTAQ 파일이었츄 image 국내산라이츄 국내산라이츄 21.12.09.13:27 2948
37 34. 단백질이 접히는 과정츄 5 image 국내산라이츄 국내산라이츄 21.11.16.12:38 3364
36 33. 그래프 이론이었츄 4 image 국내산라이츄 국내산라이츄 21.11.12.12:56 910
35 32. SMILES였츄 image 국내산라이츄 국내산라이츄 21.11.12.11:45 404
34 31. EC50과 IC50이었츄 12 image 국내산라이츄 국내산라이츄 21.10.31.23:32 2623
33 30. 밀도에 대해 알아보시츄 image 국내산라이츄 국내산라이츄 21.10.19.23:40 3329
32 29. 생활 속의 진법이었츄 5 image 국내산라이츄 국내산라이츄 21.02.25.23:43 649