[python/알고리즘] 최대 공약수 구하기

 

약수(Common Divisor)란?

---

나누었을 때 나머지가 0인 수  -> n % d == 0

 

최대공약수(Greatest Common Divisor)란?

---

두 개 이상의 자연수(또는 정수)가 가지는 공통의 약수 중 최댓값

 

 

---

Q1. 공책 20개, 연필 12개를 학생들에게 똑같이 나누어 주는데 최대 몇 명의 학생들에게 나누어줄 수 있는가?

 

A. 4명

1. math 내장함수 사용

  
  import math
  
  print(math.gcd(20,12))
    

2. 유클리드 호제법 사용

  
  # 1. 최대 공약수 구하기
  note = 20
  pen = 12

  # 유클리드 호제법 사용
  while note:
      pen, note = note, pen % note
      
  print(pen)
    

 

 

유클리드 호제법이란?

---

최대공약수를 구하는 알고리즘으로, 유클리드에 의해 발견된 방법이다.

호제법은 두 수가 서로 상대방 수를 나누어서 결국 원하는 수를 얻는 방법을 뜻한다.

 

---

< 추가 문제 > 

Q2. 어떤 자연수로 77을 나누면 나머지가 2이고, 92를 나누어도 나머지가 2이다. 어떤 자연수는 무엇인가?

 

A. 3

 
  x=77
  y=92

  while x:
      y, x = x, y % x

  print(y+2)
    

 

 

Q3. 땅콩 78,696개, 호두 19,332개, 해바라기 73,500개를 사람들에게 똑같이 나누어 주려고 한다. 최대 몇 명에게 똑같이 나누어 줄 수 있는가?

 

A. 12명

  
  # 세 가지 수의 최대 공약수 구하기
  num1 = 78696
  num2 = 19332
  num3 = 73500

  def gcd(a,b):
      while b:
          a, b = b, a%b

      return a

  print(gcd(gcd(num1,num2),num3))
 

 

 

Q4. <심화 문제> 1에서 100까지의 번호가 각각 붙어 있는 사물함이 번호 순서대로 있고, 100명의 학생이 있다.

- 사물함은 처음에 모두 닫혀있다.

- 학생은 한 명씩 사물함을 지나가며 사물함이 닫혀있으면 열고, 열려 있으면 닫고 지나간다.

- 2번 학생은 2의 배수 번호의 사물함만 건들 수 있다. 3번도 3의 배수 번호의 사물함만 건들 수 있으며 즉, 각 학생 번호의 배수인 번호가 붙어 있는 사물함만 건들 수 있다.

- 이와 같은 규칙으로 1번부터 100번까지의 학생들이 사물함을 지나간다면 열려 있는 사물함의 개수는 몇 개인가?

 

A. 10개

  
  # 사물함 문제 1~100번까지
  # 닫혀있는게 0
  locker = [ 0 ] * 101
  for i in range(1,101):  # 1번부터 100번의 학생
      for j in range(i,101,i):  # 사물함 열림 여부
          if locker[j] == 0 :
              locker[j] = 1  # 1은 열린 사물함
          else :
              locker[j] = 0

  print(locker)
    
  cnt = []
  # 열린 사물함(1)만 카운트
  for i in locker:
      if i == 1:
        cnt.append(i)
        
  print(len(cnt))
    

 

-> 이 문제는 자세히 보면 1부터 100까지 약수의 개수가 홀수이면 사물함이 열리게 된다. 

즉, 완전 제곱수를 구하는 문제로 아래와 같이 간단하게 풀 수도 있다.

  
  # 완전제곱수를 활용하여 구하기
  locker2 = []
  n= 100  
  i = 1
  
  while( i**2 <= n ):
    locker2.append(i**2)
    i += 1

  print('locker : ',locker2)
  print(len(locker2))
    

 

완전 제곱수란?

---

정수의 제곱으로 된 수를 말한다. ex) 2의 2승, 3의 2승, 4의 2승,,,

 

출처 : Youtube 주니온TV 아무거나연구소의 코린아, 코딩하자! with 파이썬

---

수학을 알면 코드가 한결 가벼워진다.

공부를 하면서 초등학교 수학 문제를 풀던 때가 새록새록 떠올랐다.