[제로베이스] CH2. 기초 수학 - 최대공약수, 최소공배수, 진법

최대공약수

공약수란 두 수 이상의 여러 수의 공통된 약수를 의미한다. 최대공약수(GCD)란 두 수 이상의 여러 수의 공약수 중 최대인 수를 가리킨다.

최대공약수 파이썬

## 두 수를 공백을 기준으로 입력 받아 공약수와 최대공약수를 구하는 방법
num1, num2 = map(int,input().split)
GCD = 0

for i in range(1, max(num1,num2)+1):
	if ( num1 % i == 0 and num2 % i == 0 ):
    	print(f'공약수 = {i}')
        GCD = i

print(f'최대공약수 = {GCD}')

위와 같은 방식은 최대공약수를 1부터 찾게 된다. 근데 최대공약수를 구해보면 항상 두 수중 작은 수보다 최대공약수가 작거나 같다. 이 생각을 반영하면 더 효율적인 방법으로 최대공약수를 구할 수 있다.

두 수의 최대공약수는 어차피의 두 수에서 작은 수와 같거나 작게 나온다.
def gcd(a, b):
    # 두 수 중에서 작은 수를 기준으로 -1로 줄여나가며 구하면 최대공약수를 더 빠르게 구할 수 있다.
    for i in range(min(a, b),1,-1):
        if a % i == 0 and b % i == 0:
            return i
                        
print(f'GCD is : {gcd(12,36)}')

최대공약수 유클리드 호제법

최대공약수를 구하는 알고리즘 중 하나이다. 구하는 방법은 두 수에서 작은 수로 큰 수로 나누고 나눈 값이 0이 아니라면 나머지 값과 방금 나눈 작은 수에서 다시 작은수로 큰수를 나눈다. 계속 나누어 나눈 값이 0이 될때 까지 진행한다.(글로 보면 이해가 안갈듯..)

예시) 12와 30의 최대공약수를 구해보겠다.

먼저 30을 12로 나누면 나머지가 6가 나온다.
30/12 .... 6

그럼 6와 12중 작은 수가 6이므로 12를 6으로 나눈다.
12/6 .... 0

그럼 나머지가 0이 나온다, 이때 0을 나오게 한 6이 최대 공약수가 된다.

위 방식으로 최대공약수를 구하는 알고리즘을 짜보면 다음과 같다.

def gcd(a,b):
    if (a == 0 or b == 0):
        return a+b
    
    if a >= b :
        return gcd(b,a%b)
    else:
        return gcd(a,b%a)

print(gcd(12,30))

최소공배수

최소공배수란 두 수의 공통 배수 중 가장 작은 수를 말한다. 예를 들어 3과 5의 최소공배수는 15가 된다.

최소공배수 파이썬

def lcm(a, b):
    for i in range(max(a, b), (a * b) + 1):
        if i % a == 0 and i % b == 0:
            return i

최소공배수는 최대공약수와 연관있다. 최소공배수는 두 수를 곱하고 두 수의 최소공약수로 나누면 된다.

(a*b) / GCD(a,b)

def gcd(a,b):
    if (a == 0 or b == 0):
        return a+b
    
    if a >= b :
        return gcd(b,a%b)
    else:
        return gcd(a,b%a)

def lcm(a,b):
	return (a*b)/gcd(a,b)

진법

진법이란, 특정 숫자 몇 개를 사용하여 수를 표시하는 방법이다.

진법 변환 예시

진법 변환 파이썬

intnum = 30

print(f'2진수 : {bin(intnum)}')
print(f'8진수 : {oct(intnum)}')
print(f'16진수 : {hex(intnum)}')

print('\n')

print(f'2진수 : {format(intnum, "#b")}')
print(f'8진수 : {format(intnum, "#o")}')
print(f'16진수 : {format(intnum, "#x")}')

## 출력 
2진수 : 0b11110
8진수 : 0o36
16진수 : 0x1e

2진수 : 0b11110
8진수 : 0o36
16진수 : 0x1e