『Do it! 알고리즘 코딩 테스트 with JAVA 강의』를 듣고 정리한 글입니다.

소수 구하기

• 소수(Prime number)는 자신보다 작은 2개의 자연수를 곱해 만들 수 없는 1보다 큰 자연수를 말한다.
  • 1과 자기 자신 외의 약수가 존재하지 않는 수
• 코딩 테스트에서는 이러한 소수를 판별하는 방식을 묻는 소수 구하기 문제가 종종 출제된다.

에라토스테네스의 체 원리

• 소수를 구하는 대표적인 판별법으로는 에라토스테네스의 체 원리가 있다.

  1. 구하고자 하는 소수의 범위만큼 1차원 배열을 생성한다.

  2. 2부터 시작하고 현재 숫자가 지워지지 않을 때는 현재 선택된 숫자의 배수에 해당하는 수를 배열에서 끝까지 탐색하면서 지운다.

     이때, 처음으로 선택된 숫자는 소수이기 때문에 지우지 않는다.

  3. 배열의 끝까지 2번 과정을 반복한 후 배열에서 남아 있는 모든 수를 출력한다.

• 에라토스테네스의 체는 이중 for문을 사용하지만, 시간복잡도는 일반적으로 $O(Nlog(logN))$이다.
  • 배수를 삭제하는 연산으로 실제 구현에서 바깥쪽 for문을 생략하는 경우가 빈번하게 발생하기 때문이다.

구현 코드

• N이상 M이하의 범위에서 소수 찾기
  1. 크기가 N+1인 배열을 선언한 후 값은 각각의 인덱스 값으로 채운다.
  2. 1은 소수가 아니므로 삭제한다.
  3. 2부터 N의 제곱근까지 값을 탐색한다. 값이 인덱스 값이면 그대로 두고, 그 값의 배수를 탐색해 0으로 변경한다.
  4. 배열에 남아 있는 수 중 M 이상 N 이하의 수를 모두 출력한다.

💡 N의 제곱근까지만 탐색하는 이유

N이 a*b라고 가정했을 때, a와 b 모두 N의 제곱근보다 클 수 없다. 따라서 N의 제곱근까지만 확인해도 전체 범위의 소수를 판별할 수 있다.

만약 16의 범위까지 소수를 구할 때 16 = 4*4로 이뤄지면 16보다 작은 숫자는 항상 4보다 작은 약수를 갖게 된다는 뜻이다.

따라서 4까지만 확인하고 소수 판별을 진행하면 된다.

int[] A = new int[N+1];

for (int i = 2; i <= N; i++) {
    A[i] = i;
}

for (int i = 2; i <= Math.sqrt(N); i++) {
    if (A[i] == 0) continue;
    for (int j = i+i; j <= N; j=j+i) {
        A[j] = 0;
    }
}

for (int i = M; i <= N; i++) {
    if (A[i] != 0) {
        System.out.println(A[i]);
    }
}

오일러 피

• 오일러 피 함수(Euler's phi function) P[N]의 정의는 1부터 N까지 범위에서 N과 서로소인 자연수의 개수를 뜻한다.
  • 서로소는 공약수가 1 이외에 없는 수를 말한다.
  • 예를 들어, 2와 3이 서로소이다.
• 오일러 피 함수는 증명 과정을 공부해야 완벽하게 알 수 있지만, 여기에선 코딩 테스트에 사용하기 위한 구현 부분만 알아보도록 한다.
• 코딩 테스트에 자주 나오지는 않는다.

핵심 이론

1. 구하고자 하는 오일러 피의 범위만큼 배열을 자기 자신의 인덱스 값으로 초기화한다.
2. 2부터 시작해 현재 배열의 값과 인덱스가 같으면(=소수일 때) 현재 선택된 숫자(K)의 배수에 해당하는 수를 배열에 끝까지 탐색하며 P[i]=P[i]-P[i]/K 연산을 수행한다. (i는 K의 배수)
3. 배열의 끝까지 2번 과정을 반복하여 오일러 피 함수를 완성한다.

구현 코드

private static long Euler(Long N) {
    
    long res = N;

    // 2부터 N의 제곱근까지 반복
    for(long i=2; i <= Math.sqrt(N); i++){
        if(N%i == 0){
            res = res - res/i;
            while(N%i == 0) {
                N /= i;
            }
        }
    }

    if(N>1) {
        res = res - res/N;
    }
    
    return res;
}

유클리드 호제법

• 유클리드 호제법(euclidean-algorithm)은 두 수의 최대 공약수를 구하는 알고리즘이다.
• 일반적으로 최대 공약수를 구하는 방법은 소인수 분해를 이용한 공통된 소수들의 곱으로 표현할 수 있지만, 유클리드 호제법은 좀 더 간단한 방법을 제시한다.

핵심 이론

• 먼저 MOD 연산이 최대 공약수를 구하는 데 사용하는 핵심 연산이기 때문에, 이 연산을 이해하고 있어야 한다.
  • MOD 연산: 두 값을 나눈 나머지를 구하는 연산
  • ex) 10 MOD 4 = 2 → 10 % 4 = 2
• MOD 연산으로 다음과 같이 유클리드 호제법을 구현할 수 있다.
  1. 큰 수를 작은 수로 나누는 MOD 연산을 수행한다.
  2. 앞 단계에서의 작은 수와 MOD 연산 결괏값(나머지)으로 MOD 연산을 수행한다.
  3. 2번 과정을 반복하다가 나머지가 0이 되는 순간의 작은 수를 최대 공약수로 선택한다.
• 최대 공약수를 구하는 연산은 일반적으로 gcd로 정의한다.

구현

• 코딩 테스트에서는 보통 재귀함수로 구현한다.

public static void main(String[] args) throws Exception {

    BufferedReader br = 
        new BufferedReader(new InputStreamReader(System.in));

    StringTokenizer st = new StringTokenizer(br.readLine());

    int N = Integer.parseInt(st.nextToken());
    int M = Integer.parseInt(st.nextToken());

    int result = gcd(N, M);
    System.out.println(result);
}

private static int gcd(int N, int M) throws IOException {
		int res = N % M;
    if (res == 0) return M;
    return gcd(M, res);
}

최소 공배수 구하기

• 최대 공약수의 함수를 기반으로 최소 공배수(LCM)를 구할 수 있다.
• 최소 공배수 = 두 수의 곱 / 최대 공약수

private static int lcm(int N, int M) throws IOException {
    return (N*M) / gcd(N, M);
}

Reference

[지금 무료] Do it! 알고리즘 코딩테스트 with JAVA 강의 - 인프런