[Alg] GCD 계산 알고리즘

유클리드 호제법 (Euclidean algorithm)

2개의 자연수의 최대 공약수를 구하는 알고리즘으로 명시적으로 기술된 가장 오래된 알고리즘이다.
a > b 이고 a % b = r 이라 할 때, a와 b의 최대 공약수는 b 와 r의 최대 공약수와 같고 이와 같은 과정을
하나의 수가 0이 될 때까지 반복하면 나머지 한 수가 최대 공약수가 된다는 법칙.

def gcd(a,b):
    while a != 0 and b != 0:
        if a > b:
            a %= b
        elif a < b:
            b %= a
        else:
            b = 0
    return a + b

재귀를 활용하여 gcd 함수 구현하기

def gcd(a,b):
    if a == 0 or b == 0: return a+b
    elif a > b: return gcd(a-b,b)
    else: return gcd(b-a, a)
def lcm(a,b): return int(a*b/gcd(a,b))

BOJ_9417 : 최대 GCD

문제
정수 M개가 주어졌을 때, 모든 두 수의 쌍 중에서 가장 큰 최대공약수 찾는 프로그램을 작성하시오.

입력
첫째 줄에 테스트 케이스의 개수 N (1 < N < 100)이 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있으며, 양의 정수 M (1 < M < 100)개가 주어진다. 모든 수는 -231보다 크거나 같고, 231 -1보다 작거나 같다.

출력
각 테스트 케이스마다, 입력으로 주어진 수의 모든 두 수의 쌍의 최대공약수 중 가장 큰 값을 출력한다.

def gcd(a,b):
    while a != 0 and b != 0:
        if a > b:
            a %= b
        elif a < b:
            b %= a
        else:
            b = 0
    return a + b

import sys

n = int(input())
inputs = [list(map(int,sys.stdin.readline().split())) for i in range(n)]
outputs = []

for i in range(n):
    max = 0
    size = len(inputs[i])
    if size == 1:
        continue
    for a in range(1,size):
        for b in range(size-a):
            if gcd(inputs[i][b],inputs[i][b+a]) > max:
                max = gcd(inputs[i][b],inputs[i][b+a])
    outputs.append(max)

for i in outputs:
    print(i)

리스트에 있는 모든 수의 모든 두 쌍을 비교하는 방법

1. 리스트의 size를 len(list)로 먼저 구한다.
2. for - range(1,size)문으로 가능한 간격의 범위를 돌린다.
예) list = [1, 2, 3, 4]일 경우 가능한 간격의 범위는 1칸, 2칸, 3칸
3. 1칸인 경우 list[0]에서 list[2]까지 for문을 돌리면서 1칸 뒤와 비교한다.
4. 2칸인 경우에도 마찬가지로 list[0]에서 list[1]까지 for문을 돌리며 2칸 뒤와 비교한다.
5. 위의 과정을 반복하면 리스트에 있는 모든 수의 모든 두 쌍을 비교할 수 있다.