코딩테스트를 위한 GCD 알고리즘 정리

About this offer

코딩테스트를 공부하다 보면 분수의 약분, 최소공배수, 배열의 공통 주기처럼 최대공약수(GCD, Greatest Common Divisor) 를 구해야 하는 문제를 자주 만나게 된다. GCD를 구하는 방법은 여러 가지가 있지만, 코딩테스트에서는 모든 알고리즘을 깊게 공부할 필요는 없다. 가장 중요한 것은 유클리드 호제법(Euclidean Algorithm) 이다. 이번 글에서는 GCD를 구하는 여러 방법을 살펴보고, 코딩테스트에서 어느 정도까지 알고 있으면 좋은지 정리해본다. 1. 최대공약수란? 두 정수 a , b 가 있을 때 두 수를 모두 나누어떨어지게 하는 수를 공약수 라고 한다. 예를 들어 12와 18의 공약수를 구해보면, 12의 약수: 1, 2, 3, 4, 6, 12 18의 약수: 1, 2, 3, 6, 9, 18 공약수는 1, 2, 3, 6 이고, 그중 가장 큰 값인 6 이 최대공약수이다. 따라서 gcd(12, 18) = 6 이다. 2. 모든 약수를 탐색하는 방법 가장 쉽게 생각할 수 있는 방법은 1 부터 두 수 중 작은 값까지 모두 확인하는 것이다. public int gcdBruteForce(int a, int b) { int gcd = 1; for (int i = 1; i <= Math.min(a, b); i++) { if (a % i == 0 && b % i == 0) { gcd = i; } } return gcd; } 두 수를 모두 나눌 수 있는 값을 발견할 때마다 gcd 를 갱신하고, 마지막에 발견한 가장 큰 공약수를 반환한다. 시간 복잡도 두 수 중 작은 값을 N 이라고 하면, O(N) 의 시간이 필요하다. 구현은 간단하지만 입력값이 커지면 비효율적이다. 따라서 이 방법은 GCD의 개념을 이해하기 위한 방법 으로는 좋지만, 실제 코딩테스트에서는 유클리드 호제법을 사용하는 것이 일반적이다. 3. 유클리드 호제법 GCD를 구할 때 가장 중요한 알고리즘은 유클리드 호제법 이다. 다음 성질을 이용한다. gcd(a, b) = gcd(b, a % b) 두 수의 최대공약수는 작은 수 b a 를 b 로 나눈 나머지 의 최대공약수와 동일하다. 이를 나머지가 0 이 될 때까지 반복한다. 예제 gcd(48, 18) 을 계산해보자. gcd(48, 18) | 48 % 18 = 12 gcd(18, 12) | 18 % 12 = 6 gcd(12, 6) | 12 % 6 = 0 따라서 최대공약수는 6 이다. 4. 반복문으로 구현한 유클리드 호제법 코딩테스트에서 가장 사용하기 좋은 형태이다. public int gcd(int a, int b) { while (b != 0) { int remainder = a % b; a = b; b = remainder; } return a; } 처음에는 a = 48 b = 18 이라고 해보자. 반복 과정은 다음과 같다. 48, 18 18, 12 12, 6 6, 0 b 가 0 이 되면 현재 a 가 최대공약수이다. 시간 복잡도 유클리드 호제법은 대략 O(log(min(a, b))) 의 시간 복잡도를 가진다. 단순하게 모든 약수를 확인하는 방법보다 훨씬 빠르다. 5. 재귀로 구현하기 유클리드 호제법은 재귀 호출로도 자연스럽게 표현할 수 있다. public int gcd(int a, int b) { if (b == 0) { return a; } return gcd(b, a % b); } 더 줄이면 다음처럼 작성할 수도 있다. public int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); } 알고리즘의 정의 자체와 코드가 거의 동일하다는 장점이 있다. gcd(a, b) → gcd(b, a % b) → ... → gcd(gcd, 0) 코딩테스트 풀이에서도 자주 볼 수 있는 형태이다. 다만 처음 공부할 때는 값이 어떻게 변하는지 확인하기 쉬운 반복문 버전도 함께 이해하는 것이 좋다. 6. 여러 수의 GCD 구하기 유클리드 호제법은 두 수뿐만 아니라 여러 수에도 사용할 수 있다. 다음 성질을 이용한다. gcd(a, b, c) = gcd(gcd(a, b), c) 예를 들어 24, 36, 60 의 최대공약수를 구한다고 해보자. 먼저 gcd(24, 36) = 12 이고, 다음으로 gcd(12, 60) = 12 이므로 최종 최대공약수는 12 이다. 배열에 적용하면 다음과 같이 작성할 수 있다. public int gcd(int a, int b) { while (b != 0) { int remainder = a % b; a = b; b = remainder; } return a; } public int gcd(int[] numbers) { int result = numbers[0]; for (int i = 1; i < numbers.length; i++) { result = gcd(result, numbers[i]); } return result; } 이러한 형태는 배열 전체의 공통 간격이나 비율을 구하는 문제에서 활용할 수 있다. 7. GCD와 LCM GCD를 공부할 때는 최소공배수(LCM, Least Common Multiple) 도 함께 알아두는 것이 좋다. 두 수 a , b 에 대해서 다음 관계가 성립한다. a × b = gcd(a, b) × lcm(a, b) 따라서 최소공배수는 lcm(a, b) = a × b / gcd(a, b) 로 구할 수 있다. Java에서는 다음과 같이 작성할 수 있다. public long lcm(int a, int b) { return (long) a / gcd(a, b) * b; } 여기에서 a * b / gcd(a, b) 가 아니라 a / gcd(a, b) * b 순서로 계산하는 이유는 곱셈 과정에서 발생할 수 있는 overflow 위험을 줄이기 위해서 이다. 또한 계산 결과가 int 의 범위를 넘어갈 수 있으므로 long 을 사용하는 것이 안전하다. 8. Binary GCD GCD를 구하는 또 다른 알고리즘으로 Binary GCD , 또는 Stein's Algorithm 이 있다. 이 알고리즘은 % 연산 대신 주로 다음 연산을 이용한다. 비트 연산 2로 나누기 뺄셈 다음 성질들을 이용한다. gcd(2a, 2b) = 2 × gcd(a, b) // 둘 다 짝수라면 공통으로 2를 꺼냄 gcd(2a, b) = gcd(a, b) // b가 홀수이면 2를 제거 gcd(a, b) = gcd(|a - b|, min(a, b)) // 두 수가 홀수라면 두 수의 차이를 이용 과거에는 나눗셈 연산이 상대적으로 비싼 환경에서 의미가 있었지만, 일반적인 코딩테스트에서는 직접 구현할 일이 많지 않다. 따라서 Binary GCD라는 알고리즘도 존재한다. 정도만 알고 있어도 충분하다. 9. 확장 유클리드 알고리즘 유클리드 호제법을 확장하면 단순히 GCD만 구하는 것이 아니라 다음 식을 만족하는 x , y 까지 구할 수 있다. ax + by = gcd(a, b) 이를 확장 유클리드 알고리즘(Extended Euclidean Algorithm) 이라고 한다. 예를 들어, gcd(30, 18) = 6 이고 30 × (-1) + 18 × 2 = 6 이므로 x = -1 y = 2 가 하나의 해가 된다. 확장 유클리드 알고리즘은 다음과 같은 정수론 문제에서 사용된다. 모듈러 역원 선형 디오판토스 방정식 중국인의 나머지 정리 모듈러 연산 기본적인 코딩테스트에서는 자주 등장하지 않지만, 정수론 문제를 공부하기 시작하면 중요해진다. 10. 코딩테스트에서는 어디까지 공부해야 할까? GCD 관련 알고리즘을 모두 같은 수준으로 외울 필요는 없다. 알고리즘 중요도 학습 목적 모든 약수 탐색 ★ GCD 개념 이해 유클리드 호제법 ★★★★★ 반드시 숙지 재귀 유클리드 호제법 ★★★★★ 간결한 구현 여러 수의 GCD ★★★★ 배열 문제 응용 Binary GCD ★ 존재 정도 알아두기 확장 유클리드 ★★★ 정수론 심화 일반적인 코딩테스트를 준비한다면 다음 코드는 바로 작성할 수 있을 정도로 익혀두는 것이 좋다. public int gcd(int a, int b) { while (b != 0) { int remainder = a % b; a = b; b = remainder; } return a; } 그리고 함께 기억할 공식은 다음과 같다. gcd(a, b) = gcd(b, a % b) lcm(a, b) = a / gcd(a, b) × b 이 두 가지를 알고 있으면 상당수의 GCD/LCM 문제를 해결할 수 있다. 정리 GCD를 구하는 가장 단순한 방법은 모든 약수를 검사하는 것이지만 시간 복잡도가 O(N) 이기 때문에 큰 입력에는 적합하지 않다. 코딩테스트에서는 대부분 유클리드 호제법 을 사용한다. 유클리드 호제법의 핵심은 다음 한 줄이다. gcd(a, b) = gcd(b, a % b) 이를 나머지가 0 이 될 때까지 반복하면 최대공약수를 빠르게 구할 수 있다. GCD를 이해하면 자연스럽게 최소공배수, 분수의 약분, 배열의 공통 주기와 같은 문제에도 적용할 수 있다. 따라서 코딩테스트를 준비한다면 여러 GCD 알고리즘을 모두 외우기보다는 유클리드 호제법의 원리를 이해하고 직접 구현할 수 있는 수준까지 익히는 것 이 가장 중요하다.