유클리드 호제법

최대공약수를 구하는 대표적인 알고리즘

예시

12와 18의 최대공약수를 유클리드 호제법을 통해 구하시오

풀이

1. 12를 18로 나누어본다
   i) 나머지가 0이면 18이 최대공약수임
   ii) 아니면 다음 단계로 넘어감(나머지가 12임)
2. 18을 1에서 구한 나머지로 나누어본다
   i) 나머지가 0이면 1에서 구한 나머지가 최대공약수임
   ii) 아니면 나머지를 구함(나머지는 6)
3. 1에서 구한 나머지를 2에서 구한 나머지로 나누어본다
   i) 나머지가 0이면 2에서 구한 나머지가 최대 공약수
   ii) 아니면 계속...

정리

1. 다음 단계에서 분모는 분자가 된다
2. 다음 단계에서 나머지는 분모가 된다
   

출처 : https://chan-lab.tistory.com/34

활용

재귀함수를 사용하여 유클리드 호제법 구현

def gcd(a,b):
	# 만약 나눠서 0이면 분모가 최대공약수
	if a % b == 0:
    	return b
    # 그렇지 않으면 gcd 함수를 다시 호출함
    # 분모가 분자 자리로 가고 분자에는 전 단계 나머지가 들어간다
   else : 
   		return gcd(b, a%b)

만약 나머지가 0으로 나누어 떨어지면 그 단계의 분모가 바로 최대공약수임

소인수분해

어떤 자연수를 소수의 곱으로만 표현하는 것

예시

18을 소인수 분해 해보세요

풀이

1. 18을 나누어떨어지게 하는 숫자는?
   => 하나씩 구현해봐야한다
2. 하나씩 구현해보기
   -> for 문
   -> 1부터 할 필요는 없다.

활용

def factorization(x):
	d = 2
    output = []
    
    # 2부터 시작하여 매개변수 x보다 작으면 계속 반복
    while d <= x:
    	if x % d == 0:
        	# 나누어 떨어지면 output 리스트에 추가
        	output.append(d)
            # 나누어 떨어진 수로 x를 바꿈
            x /= d
        else:
        	# 나누어 떨어지지 않으면 1씩 더함
        	d += 1
    return output

유한소수 판별하기 풀이법

# 유클리드 호제법과 소인수분해 구하는 함수 작성
def gcd(a, b):
    if a % b == 0:
        return b
    else:
        return gcd(b, a % b)


def factorization(x):
    d = 2
    output = []

    while d <= x:
        if x % d == 0:
            output.append(d)
            x /= d
        else:
            d += 1

    return output


def solution(a, b):
	# 최대공약수 구하기
    divide_num = gcd(b, a)
    # b를 최대공약수로 나누면 기약분수가 적용된 분모의 형태
    result = b // divide_num

    for num in factorization(result):
    	# 문제에서 준 힌트 적용
		# 기약분수로 나타내었을때 (result) 소인수가 2와 5만 존재해야 유한소수임
        # 2와 5가 없다면 무한소수이기 때문에 2를 리턴
        if num not in [2, 5]:
            return 2
    # 아니면 유한 소수이기 때문에 1을 리턴함
    return 1


print(solution(7, 20))

문제에서 준 힌트

유한소수가 되기 위한 분수의 조건은 다음과 같습니다.
기약분수로 나타내었을 때, 분모의 소인수가 2와 5만 존재해야 합니다.