[알고리즘 일기] 30. 최대 공약수 구하기
최대공약수 구하기 두 정수 $a$, $b$를 입력받아서, $a$, $b$의 최대공약수를 출력하시오. codeup.kr 2623(Codeup). 최대 공약수 구하기 카드 두 정수 a, b를 입력받아서, a, b의 최대공약수를 출력하시오. 입력 정수 a, b가 공백으로 구분되어 입력된다.(1 0: gcd = C A, B = B, C C = A % B print(gcd) 1️⃣ 유클리드 호제법 사용 2️⃣ 소수를 구하는 방법 사용 시, 시간 복잡도 : O(n) 3️⃣ 유클리드 호제법 사용 시, 시간 복잡도 : O(logn) 유클리드 호제법 [ 1. 교과서 속 주개념] [ 1) 유클리드 호제법] 두 정수 a, b의 최대공약수를 G(a, b)라고 하자. 정수 a, b, q r (b ≠ 0)에 대하여 a = bq ..
2021.05.30