[백준/Python]9417번: 최대 GCD

1. 문제 

9417번: 최대 GCD

2. 해결방법

- 문제에서 큰 힌트를 직접 주었다. GCD 알고리즘을 이용하자 ! 

 

- 우선 우리가 구해야할 값은  두 쌍의 GCD의 최댓값이다. 

• 각 테스트 케이스에서 주어진 수 중 2쌍씩 묶자 → 2중 for 문을 사용하고 중복은 제거해주었다.
• 묶은 2쌍들의 최대 공약수(GCD)를 구한 뒤 →유클리드 알고리즘 
• 최댓값을 출력 ! 

 

3. 코드 

n = int(input())
numList = [list(map(int,input().split())) for _ in range(n)]

# 최대 GCD
def gcd(a,b):
    while b>0:
        a,b = b, a%b
    return a


for list in numList:
    ansList=[]
    for i in range(len(list)):
        for j in range(i,len(list)):
            if i!=j:
                ansList.append(gcd(list[i],list[j]))
    print(max(ansList))

4. 잊지말자 

유클리드 알고리즘 

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

단순하지만 강력한 알고리즘이다. 

다음 포스팅에서 자세히 다루어보겠다 ~ !