코테 (1) 썸네일형 리스트형 GCD 알고리즘 GCD(Greatest Common Divisor), 즉 최대 공약수를 구하는 방법에 대해 한 번 알아보고자 한다. 최대 공약수를 구하는 방법은 우리가 이미 초등학교, 중학교 때 배우기는 하였다. 두 수에 대해서 소수(Primary Number)를 나누어 주어 서로소로 만든 후, 나누어주었던 소수 집합을 모두 모아 곱해주면 그게 바로 최대 공약수였다. 그러나 이 방식을 컴퓨터에서 구현하기에는 아름답지 못한 방법이다. 우선 나누어주는 수가 소수인지 판단하는 데 시간을 소모하고, 두 수가 모두 해당 소수로 나누어지는 지 판단해야 한다. 이런 방식은 잠시 뒤로 밀어두고 우리는 유클리드 호제법을 이용하여 GCD를 구하고자 한다. 유클리드 호제법의 가장 기본적이고 핵심적인 부분을 꼽자면 A, B라는 두 수에 대해.. 이전 1 다음
