쌍문동 척척박사
Spring / ReactJS / PS

유클리드 호제법 (최대 공약수)

유클리드 호제법 (최대 공약수)

BOJ 2485 가로수를 풀어보자.

우선 몇몇 포인트부터 살펴보면

  • 입력 값의 범위가 int형을 넘어섰으니 (최대 20억) long 형을 써야한다.
  • 가로수 간격은 단순히 최소값이 아니라, 최대 공약수로 설정해야 간격이 어긋나지 않게 된다.

가장 기초적인 최대 공약수를 구하는 함수를 작성해보면 다음과 같다.

1
2
3
4
5
6
7
public long gcd(long a, long b){
  long gcd = 0, min = Math.min(a, b);
  for(long mod = 1; mod <= min; mod++){
    gcd = (a%mod == 0 && b%mod == 0) ? mod : gcd;
  }
  return gcd;
}

시간 제한 안에 통과가 되는가? 시간 복잡도가 O(N)이므로 바로 아니라는 것을 알 수 있다. 따라서 우리는 다른 기법이 필요하다.

기본 개념

유클리드 호제법은 실제 수학 시험에서도 자주 출제되는 유명한 최대 공약수 찾기 테크닉이다. 증명은 다음 링크를 확인하자. 유클리드 호제법 구현은 다음과 같으며, 두 수 N, M에 대해 시간 복잡도는 O(lg(N+M))이다.

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
32
import java.io.*;
import java.util.*;

class Solution{
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    final int MAXN = 100000 + 2;

    int N;
    long min;
    long[] tree = new long[MAXN];

    public long gcd(long a, long b){
        long mod;
        while((mod = a%b) > 0){
            a = b;
            b = mod;
        }
        return b;
    }
    public Solution() throws IOException {
        N = Integer.parseInt(br.readLine());
        for(int i = 0; i < N; i++){
            tree[i] = Long.parseLong(br.readLine());
        }
        min = tree[1]-tree[0];
        for(int i = 1; i < N-1; i++){
            min = gcd(min, tree[i+1]-tree[i]);
        }
        long cnt = -N+1 + (tree[N-1]-tree[0])/min;
        System.out.println(cnt);
    }
}

공약수 문제가 과연 많이 출제될까? 하는 생각이 들 수도 있는데, 실제로 공약수는 그 자체가 문제의 핵심으로 나오는 경우 외에도 부분적 문제로 등장하는 경우도 많다. 다른 수학 개념들도 마찬가지다. 전체 문제의 틀은 Divide and Conquer이거나 BFS/DFS일 수 있지만 그 내부 로직에 공약수 테크닉이 포함될 수 있다는 말이다. 그렇기에 꼭 알아두고 넘어가자.

추가 문제

comments powered by Disqus