[BOJ/Math] 9613: GCD 합

⚡ 풀이

from itertools import combinations
import sys
import math

input = sys.stdin.readline
result = list()

t = int(input())

for i in range(t):
  sum = 0
  numbers = list(map(int, input().split()))
  del numbers[0]
  
  for x, y in combinations(numbers, 2):
    gcd = math.gcd(x, y)
    sum += gcd
      
  result.append(sum)

for i in range(t):
  print(result[i])

.
.
.

💡 유클리드 호제법과 gcd, lcm

• 최대공약수 = gcd = greatest common divisor
  최소공배수 = lcm = least common multiple
• 이 문제에서는 math 라이브러리를 이용해 gcd를 구했지만,
  아래처럼 유클리드 호제법으로 직접 gcd, lcm을 구할 수 있다.

.

#유클리드 호제법, GCD

유클리드 호제법: 두 정수 a와 b(a > b)가 있을 때, a = bq + r (0 <= r < b)라 하면,
(a와 b의 최대공약수) = (b와 a % b의 최대공약수)이다.
∴ gcd(a, b) = gcd(b, r)
만약 r이 0 이면, a, b의 최대공약수는 b이다.
∴ a % b = 0 이면 gcd(a, b) = b

.

#LCM - GCD를 이용해 구할 수 있다

a, b의 최소 공배수는 a * b를 a, b의 최대공약수로 나눈 몫이다.
∴ lcm(a, b) = a b // gcd(a, b)*

.
코드:

        def gcd(a, b):
        	if b == 0:
        		return a
        	else:
        		return gcd(b, a % b)
        
        def lcm(a, b):
          return a * b // gcd(a, b)

.
.
.

itertools 라이브러리의 permutations(순열), combination(조합) 클래스

• 순열 vs 조합
  고등학교때 순열과 조합을 배웠던 기억을 되살려보자면, 순열은 순서를 고려하고 조합은 순서를 고려하지 않는 것이다. 순열, 조합, 중복순열, 중복조합 각각의 활용 방법은 아래 블로그를 참고하자
  (Python) 순열, 조합, 중복순열, 중복조합 쉽게 구현하기 이 문제에서는 각 테스트케이스마다 주어진 숫자들로 만들어지는 모든 쌍의 gcd를 구해야 했기에 순서를 고려하지 않는 조합 클래스를 사용했다!
  .
• for문 + combination(조합) 최적화: 2차원 리스트/튜플에서 안쪽 원소에 접근

  • 2차원 리스트에서 안쪽 리스트의 원소에 접근할 때 a[0][0] 이런식으로 접근하곤 한다..

  • 2차원 리스트에서 안쪽 리스트의 크기가 모두 같고, 그 크기가 작을 때 for문을 아래처럼 작성하여 안쪽 리스트의 원소에 바로 접근할 수 있다!

  • for과 in 사이에 쓰는 변수는 안쪽 리스트의 크기가 n이면 n개 써준다.

  • 2차원 튜플, 리스트 안에 튜플이나 튜플 안에 리스트가 있는 경우도 똑같다!

  • 예제)

    >>> a = [[10, 20], [30, 40], [50, 60]]
    >>> for x, y in a:    # 리스트의 가로 한 줄(안쪽 리스트)에서 요소 두 개를 꺼냄
    ...     print(x, y)
    ...
    10 20
    30 40
    50 60

  • 이 문제에서 활용한 모습
    사실 combinations, permutations의 결과는 2차원 리스트가 아니라 클래스이기 때문에 리스트로 변환해서 사용해야하는데 변환하지 않아도 이렇게 활용할 수 있는 정확한 원리는 잘 모르겠다..

    for i in range(t):
      sum = 0
      numbers = list(map(int, input().split()))
      del numbers[0]
      
      for x, y in combinations(numbers, 2):
        gcd = math.gcd(x, y)
        sum += gcd
          
      result.append(sum)

    • 리팩토링 전 코드

      for i in range(t):
        sum = 0
        numbers = list(map(int, input().split()))
        del numbers[0] 
      
        combs = list(combinations(numbers, 2))
        for j in range(len(combs)):
          gcd = math.gcd(combs[j][0], combs[j][1])
          sum += gcd
      
        result.append(sum)

  • 참고: 아래 코드처럼 for과 in 사이에 변수를 하나만 쓰면 쌍 자체에 접근한다!

  • 안쪽 리스트의 원소 하나하나에 접근할 필요가 없다면 이렇게..

    from itertools import combinations
    
    for i in combinations([1,2,3,4], 2):
        print(i, end=" ")
    
    >> 결과: (1, 2) (1, 3) (1, 4) (2, 3) (2, 4) (3, 4)