'GCD' 태그의 글 목록

[알고리즘] 최대공약수 구하기 - 유클리드 호제법 Euclidean Algorithm

일반적으로 A와 B의 최대공약수를 구하는 가장 쉬운 방법은 A와 B를 2부터 A와 B중 더 작은 수 까지 모든 자연수로 나누는 것이다. 이 방법은 수가 커질수록 시간이 오래걸려 비효율적이며, 모든 수로 나눠야 하므로 시간복잡도는 O(n)이 된다. 이때 유클리드 호제법을 사용한다. 유클리드 호제법 (Euclidean Algorithm) : 두 정수의 최대공약수(Greatest Common Divisor)를 구하는 알고리즘 A > B 일 때1. A % B = C2. B % C = D3. 위 과정을 계속 반복4. X % Y = 0, Y가 A와 B의 최대공약수 그림으로 표현해 보자 두 정수 A, B를 직사각형의 두 변의 길이라고 생각하면 직사각형을 정사각형으로 완전히 채우려고 할 때 정사각형의 가장 긴 변의 길..

프로그래밍/Algorithm 2021.01.23

일	월	화	수	목	금	토
			1	2	3	4
5	6	7	8	9	10	11
12	13	14	15	16	17	18
19	20	21	22	23	24	25
26	27	28	29	30	31

Nanarin🙃

GCD 1

티스토리툴바