[BOJ] 9613: GCD 합

이슬비·2022년 6월 14일

boj 수학 유클리드 호제법 자료구조&알고리즘

Algorithm

목록 보기

41/110

gcd... 처음에 뭔지 몰랐음 ㅎㅎ

9613: GCD 합

1. 내 풀이: 성공

import sys

test = int(sys.stdin.readline())
cnt = 0

while cnt!=test:
    gcd = list()
    num = list(map(int, sys.stdin.readline().strip().split()))
    num.remove(num[0])
    for a in range(len(num)):
        for b in range(a+1, len(num)):
            i = num[a]
            j = num[b]
            while True:
                r = i%j
                if r == 0:
                    gcd.append(j)
                    break
                else:
                    i = j
                    j = r
    print(sum(gcd))
    cnt += 1

좋아... for문에 while문까지 더해져서 생각보다 코드도 길어져버렸다. 그래서 당연히 시간 초과가 나지 않을까 생각했는데 ~ 다행히 통과.

구현 방법은,

gcd = list()
num = list(map(int, sys.stdin.readline().strip().split()))
num.remove(num[0])

일단 gcd를 담을 통을 만들어 주고, 숫자들을 받아온다. 이때 첫 숫자는 숫자들의 개수이므로 첫 번째 인덱스는 지워준다.

for a in range(len(num)):
    for b in range(a+1, len(num)):
        i = num[a]
        j = num[b]
        while True:
           r = i%j
           if r == 0:
              gcd.append(j)
              break
           else:
              i = j
              j = r

이제 gcd를 구해주는데... 모든 쌍을 다 판단해야하므로 for문을 두 번 돌아준다. 이 알고리즘은 유클리드 호제법이라고 불리우는, 최대공약수와 최소공배수를 쉽게 구할 수 있는 알고리즘이다.

🙋 유클리드 호제법?

최대공약수

x % y = r에서 r이 0일 때,
y는 최대공약수이다.

다시 설명하면, 만약 4와 10의 최대 공약수를 유클리드 호제법으로 구한다고 하자.

4 % 10 = 4

이고, 이때 y 자리에 있는 10과 r 자리에 있는 4를 x와 y 자리로 가져와서,

10 % 4 = 2

로 계산한다. 아직 r이 0이 안되었으므로,

4 % 2 = 0

로 계산을 하면 r이 0이 되므로 이때의 y, 즉 2가 10과 4의 최대공약수가 되는 것이다.

최소공배수

최소공배수의 경우, x와 y의 곱을 x와 y의 최대공약수로 나눈 것이다.

유클리드 호제법으로 최대공약수 구하기
x, y 곱하기
구한 최대공약수로 x*y 나누기

참고로 유클리드 호제법으로 gcd 함수를 구현하면,

def gcd(x, y):
    while(y):
        x, y = y, x%y
    return x

꼭 기억해두자!

2. 다른 풀이

1. math 모듈

import sys
import math
n=int(input())

for i in range(n):
    arr=list(map(int, sys.stdin.readline().split()))
    total=0
    for j in range(1,len(arr)):
        for k in range(j+1,len(arr)):
            total+=math.gcd(arr[j],arr[k])

    print(total)

gcd를 직접 구현하지 않아도 된다! 이미 math에 다 구현이 되어 있기 때문... 시간도 크게 다르지 않다고 하니, gcd 구현이 익숙해지면 math 모듈을 사용해보도록 하자.

출처는 아래의 블로그.
https://youjin86.tistory.com/90

2. 조합 구하기

from itertools import combinations

def gcd(x, y):	# 최대공약수 계산 함수
    while y:
        x, y = y, (x % y)
    return x

n = int(input())
lists = []
result = 0
for _ in range(n):
    lists = list(map(int, input().split()))	# 조합 만들 숫자들 받기
    lists = lists[::-1]	# 내림차순 정렬
    del lists[len(lists) - 1]	# 마지막 요소 필요 없으니 제거
    ncr = combinations(lists, 2)	# 조합 생성
    
    for i in ncr:
        result += gcd(i[0], i[1])	# 조합을 통해 최대공약수들 result에 더하기
    print(result)	# 프린트 해 두고
    result = 0	# 초기화