알고리즘 - 최대공약수, 완전제곱수

코딩은 어려운 수학 문제를 푸는 강력한 도구다!

$x$의 이차 방정식 $3x^2 - 2x -1 = 0$의 해를 구하여라. 라는 수학 문제가 있다.

이 문제는 근의 공식에 대입해서 풀면 된다.

• $ax^2 - bx -c = 0 (a\ne0)$ -> $x = {-b \pm \sqrt{b^2-4ac} \over 2a}$

• $\sqrt{x} = x^{1/2}$

이를 코딩으로 하면 아래와 같다.

a = 3
b = -2
c = -1

x1 = (-b + (b**2 - 4*a*c)**(1/2)) / (2 * a)   # 근의 공식
x2 = (-b - (b**2 - 4*a*c)**(1/2)) / (2 * a)
print(x1, x2)

이처럼 수학 문제를 코딩으로 풀 수 있고,
코딩을 하면 복잡하고 어려운 수학 문제를 편리하게 풀 수 있다.

---

최대공약수 문제 풀기

• 약수 : 어떤 수를 나누었을 때 나머지가 0인 수
• 공약수 : 두 개 이상의 자연수(또는 정수)가 가지는 공통인 약수
• 최대공약수 : 공약수 중에서 최댓값

문제 1

공책 x권과 연필 y자루를 학생들에게 똑같이 나누어 주려고 한다. 최대 몇 명의 학생들에게 똑같이 나누어 줄 수 있는가?
x = 1071, y = 1029

x = 1071
y = 1029

x_div = []
y_div = []
cd = []

for i in range(1, x+1):   # 1071의 약수를 찾아내는 과정
    if x % i == 0:
        x_div.append(i)
        
for i in range(1, y+1):   # 1029의 약수를 찾아내는 과정
    if y % i == 0:
        y_div.append(i)
        
for i in y_div:           # 1071과 1029의 공약수를 찾아내는 과정
    for j in x_div:
        if i == j:
            cd.append(i)
            
print(max(cd))    # 최대공약수를 출력

문제 2

어떤 자연수로 77을 나누어도 나머지가 2이고, 92를 나누어도 나머지가 2이다. 이러한 자연수 중에서 가장 큰 수를 구하시오.

x = 77
y = 92

x_div = []
y_div = []
cd = []

for i in range(1, x+1):   # 1071의 약수를 찾아내는 과정
    if x % i == 2:
        x_div.append(i)
        
for i in range(1, y+1):   # 1029의 약수를 찾아내는 과정
    if y % i == 2:
        y_div.append(i)
        
for i in y_div:           # 1071과 1029의 공약수를 찾아내는 과정
    for j in x_div:
        if i == j:
            cd.append(i)
            
print(max(cd))    # 최대공약수를 출력

문제 1처럼 나머지가 2인 최대공약수를 구하는 문제이다.
파이썬 내장함수인 math를 사용하면 훨씬 더 쉽게 구할 수 있다.

import math

g1 = math.gcd(77-2, 92-2)   # math.gcd(자연수, 자연수)를 사용하면 최대공약수를 계산해서 구해준다.
print(g1)

문제 3

땅콩 78696개, 호두 19332개, 해바라기씨 73500개를 사람들에게 똑같이 나누어 주려고 한다. 최대 몇 명의 사람들에게 나누어 줄 수 있는지 구하시오.

import math

g2 = math.gcd(78696, 19332)

g3 = math.gcd(g2, 14700)
print(g3)

이 문제도 똑같이 최대공약수를 구하는 문제이다. 그러나 3개의 값을 비교해야 하기 때문에 먼저 두 값의 최대공약수를 구하고 구한 값으로 남은 한 값과 비교해서 최대공약수를 구하면 된다.

최대공약수를 구하는 문제는 유클리드 호제법을 사용해서 풀 수도 있다.
유클리드 알고리즘은 2개의 자연수 또는 정식의 최대공약수를 구하는 알고리즘의 하나이다. 호제법이란 말은 두 수가 서로 상대방 수를 나누어서 결국 원하는 수를 얻는 알고리즘을 나타낸다.

peanut = 78696
walnut = 19332
sunflower = 73500

def gcd(a,b):
    if b > a: 
        a,b = b,a

    while b != 0:
        a = a%b
        a,b = b,a

    return a
    
print(gcd(gcd(peanut, walnut), sunflower))

---

열린 사물함의 개수

문제

100개의 사물함이 있다. (번호는 1번에서 100번)
100명의 학생들이 있다. (번호는 1번부터 100번)
N번의 학생이 N의 배수 번째 사물함의 문을 열거나 닫는다.(만약 문이 열려 있으면 닫고, 닫혀 있으면 연다.)
처음에 모든 사물함의 문이 닫혀 있다고 생각해보자.
모든 학생들이 다 지나갔을 때, 열려 있는 사물함의 개수는? 그리고, 열린 사물함의 번호는?

n = 100
# 0이 닫힌 사물함

lockers = [0] * (n+1)            # 101개의 사물함(0번째 제외)
for i in range(1, n+1):          # 101개의 사물함 번호 지정(0번째 제외)
    lockers[i] = 0

for N in range(1, 101):
    for j in range(N, 101, N):   # N번의 학생이 지나가며 문을 열고 닫는다.
        if (lockers[j] == 0):    # 문이 닫혀있으면 문을 열고
            lockers[j] = j
        else:
            lockers[j] = 0       # 문이 열려있으면 닫는다.
        
open_lockers = []                # 열려있는 문
for i in lockers:
    if (i != 0):
        open_lockers.append(i)
        
print(len(open_lockers))
print(open_lockers)
 ->
 10
 [1, 4, 9, 16, 25, 36, 49, 64, 81, 100]

열었다, 닫았다를 짝수번 하면 닫힘
열었다, 닫았다를 홀수번 하면 열림
-> 약수의 개수가 홀수인 사물함의 문이 열림 (9의 약수는 1,3,9)
= 완전제곱수 : 정수의 제곱으로 된 수 (2의 제곱, 3의 제곱...)

즉, 완전제곱수는 약수의 개수가 홀수이고, 이 문제는 제곱수의 개수를 묻는 문제이다.

완전제곱수를 구하는 방식

n = 100
i = 1

open_lockers = []
while (i**2 <= n):
	open_lockers.append(i**2)
    i += 1
    
print(len(open_lockers))
print(open_lockers)

** 출처

• 주니온TV 아무거나연구소 - 코린아, 코딩하자 (with 파이썬)