99클럽 코테 스터디 2일차 TIL - 최대공약수

x만큼 간격이 있는 n개의 숫자 (미들러)

https://school.programmers.co.kr/learn/courses/30/lessons/12954

• 제출한 코드

def solution(x, n):
    return [x * i for i in range(1, n + 1)]

리스트 컴프리헨션으로 한 줄 코드를 작성했다. 처음 보고 함정이 있나 싶었지만, 없었다.

---

숫자 카드 나누기 (챌린저)

https://school.programmers.co.kr/learn/courses/30/lessons/135807

알고리즘 & 설계

유클리드 호제법을 사용하여 두 배열의 최대공약수를 각각 구하고, 구한 최대공약수로 각자 다른 배열을 순회하며 배열의 원소마다 최대공약수로 나누어 떨어지는지 확인한다. 하나의 원소라도 나누어 떨어지게 된다면, 조건에 맞지 않으므로 0을 반환한다. 모든 원소가 나누어 떨어지지 않으면, 조건에 부합하므로 해당 최대공약수를 반환한다.

• 제출한 코드

def solution(arrayA, arrayB):
    answer = 0
    gcd_a = find_gcd_in_arr(arrayA)
    gcd_b = find_gcd_in_arr(arrayB)
    
    if not_div(arrayA, gcd_b):
        answer = max(answer, gcd_b)
        
    if not_div(arrayB, gcd_a):
        answer = max(answer, gcd_a)
        
    return answer

def gcd(a, b):  # 유클리드 호제
    while b:
        a, b = b, a % b
    return a

def find_gcd_in_arr(arr):   # 배열 안에서 최대공약수를 구함
    arr_gcd = arr[0]
    for num in arr[1:]:
        arr_gcd = gcd(arr_gcd, num)
    return arr_gcd

def not_div(arr, p_gcd):   # 하나라도 나누어떨어지는지 확인
    for i in arr:
        if i % p_gcd == 0:
            return False
    return True

파이썬에는 최대공약수를 구해주는 라이브러리가 있다. import math 에서 math.gcd()를 사용할 수 있다.

1. 유클리드 호제법으로 최대공약수를 구하는 메소드
2. 리스트에서 최대공약수를 구하는 메소드
3. 리스트를 순회하며 나누어 떨어지는지 확인하는 메소드
로 각각 추출하여 최대한 가독성 높은 코드를 작성했다.

solution에서 두 if 문에 걸리지 않으면 조건을 만족하지 않으므로 0을 반환하고, 두 if 문에 각각 걸리게 된다면 최대공약수 중 최댓값을 반환하게 된다.

회고

• 최대공약수 구하기

유클리드 호제법으로 구할 수 있다.
두 수 a, b (a > b)에 대해 a를 b로 나눈 나머지를 r이라고 할 때,
a와 b의 최대공약수와 b와 r의 최대공약수가 같다.

즉, b를 r로 나눈 나머지 r’를 구하고 다시 r을 r’로 나눈 나머지를 구하는 과정을 반복하여 나머지가 0이 되었을 때 나누는 수가 a와 b의 최대공약수이다.

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