📙[Algo] 24.01.10 정수론 / 알고리즘

정수론 정리

소수 판정

완전 탐색으로 접근

1️⃣ 1부터 n까지 나누어 떨어지는 경우가 2개면 소수(1과 자기자신), 그렇지 않으면 소수가 아님을 판단

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();

        int cnt = 0;
        for (int i = 1; i < n+1; i++) {
            if (n % i == 0) {
                cnt++;
            }
        }

        if(cnt == 2) System.out.println("소수");
        else System.out.println("소수 아님");
    }
}

 

2️⃣ 1부터 n/2까지로 범위를 줄여 탐색해도 된다. 그 이유는 n/2보다 큰 수는 뭘 곱해도 n이 될 수 없기 때문이다.

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();

        int cnt = 0;
        for (int i = 1; i < n/2+1; i++) {
            if (n % i == 0) {
                cnt++;
            }
        }

        if(cnt == 2) System.out.println("소수");
        else System.out.println("소수 아님");
    }
}

 

최적화

소수 판정은 약수가 한 쌍만 있는 지 찾는 것이다.

예시) 12 의 약수
1 12

2  6

3  4

⇒ 약수를 왼쪽에 작은 것, 오른쪽은 큰 것으로 배치해서 봤을 때, 왼쪽에 올 수 있는 수들 중 가장 큰 것은 \(\sqrt{n}\) 이다.

❓1부터 \( \sqrt{n} \) 까지 봤을 때 약수가 3개라면? 6개라고 판단 가능.

❓2부터 \( \sqrt{n} \) 까지 보니 약수가 하나도 없다면? \( \sqrt{n+1} \) 부터 n-1까지 약수가 없다! (왼쪽 쌍이 없는데, 오른쪽 쌍이 존재할 수가 없음)

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();

        if(n == 1){
            System.out.println("소수 아님");
            System.exit(0);
        }

        int cnt = 0;
        for (int i = 2; i * i <= n; i++) {
            if (n % i == 0) {
                cnt++;
            }
        }

        if(cnt == 0) System.out.println("소수");
        else System.out.println("소수 아님");
    }
}

주의할 점 : 1은 따로 처리할 것.

 

시간 복잡도

 O(  \( \sqrt{n} \) ) 

약수 구하기

완전 탐색으로 접근

1부터 n까지 나누었을 때 나머지가 0인 경우 출력

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();

        for (int i = 1; i < n+1; i++) {
            if (n % i == 0) {
                System.out.println(i);
            }
        }
    }
}

 

최적화

1부터 \(\sqrt{n}\) 까지 나누었을 때 나머지가 0인 경우, 나누는 수와 나누어지는 수를 나누는 수로 나눈 몫을 같이 출력해준다.

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();
        for (int i = 1; i * i <= n; i++) {
            if (n % i == 0) {
                System.out.println(i);
                if (i * i != n)  System.out.println(n / i);
            }
        }
    }
}

주의할 점 : n이 제곱수일 경우 약수가 중복 출력될 수 있으니 조건문으로 따로 처리할 것.

 

참고로 약수의 개수는 기본적으로 짝수개이지만, 제곱수인 경우 약수의 개수는 홀수이다.

 

시간 복잡도

 O(  \( \sqrt{n} \) ) 

 

소인수분해

완전 탐색 방식

2부터 더 이상 나눌 수 없을 때까지 나눈다. 그러나 n이 엄청 큰 소수라면 너무 느림.

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();
        for (int i = 2; i < n+1; i++) {
            while (n % i == 0) {
                System.out.println(i);
                n /= i;
            }
        }

    }
}

 

최적화

n의 소인수는 n = a * b * c * d * e 형태로 나타낼 수 있다. 즉, n의 소인수를 모두 곱하면 n이 된다.

 \( \sqrt{n} \)  *  \( \sqrt{n} \) 은 n이 된다. 즉,  \( \sqrt{n} \) 보다 큰 값 *  \( \sqrt{n} \) 보다 큰 값은 n보다 클 수밖에 없다.

💡 결론 :  \( \sqrt{n} \) 보다 큰 소인수는 2개 이상 존재할 수 없다.
⇒ 즉,  \( \sqrt{n} \) 보다 큰 소인수는 없거나 하나 존재한다.

그렇기 때문에, 케이스는 총 2가지로 나뉠 수 있다.

 

1️⃣  \( \sqrt{n} \) 보다 큰 소인수가 없는 경우

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int tmp = n;
        for (int i = 2; i * i < n + 1; i++) {
            while (tmp % i == 0) {
                System.out.println(i);
                tmp /= i;
            }
        }
    }
}

 

2️⃣ \( \sqrt{n} \)  보다 큰 소인수가 정확히 하나 있는 경우

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int tmp = n;
        for (int i = 2; i * i < n + 1; i++) {
            while (tmp % i == 0) {
                System.out.println(i);
                tmp /= i;
            }
        }

        if (tmp != 1) {
            System.out.println(n);
        }
    }
}

\( \sqrt{n} \)보다 큰 수는 n에 혼자 남아 있으므로, n이 1이 아닐 경우 따로 출력해준다.

 

시간 복잡도

 O(  \( \sqrt{n} \) ) 

 

유클리드 호제법

약수라는 것은 같은 간격으로 이동했을 때 도달할 수 있을 때, 그 간격을 약수로 볼 수 있다.

즉, 위 그림에서는 2씩 건너 뛰어서 8로 도달 했으므로, 2는 8의 약수가 될 수 있다.

만약, 8과 12의 공약수를 구하고 싶다면 같은 간격으로 이동 했을 때 두 수 모두 도달할 경우를 공약수로 볼 수 있다.

여기서는 2씩 건너 뛰어서 8과 12에 도달했으므로, 2는 8과 12의 공약수이다.

또한, 8과 12의 공약수는 12 - 8의 약수이기도 하다.

8을 다시 원점으로 본다면 12는 12 - 8의 값이 되기 때문이다.

💡 결론 : a와 b의 공약수는(a > b) a - b의 약수이기도 하다.

⇒ a, b, a - b는 공약수를 공유한다.

gcd(a, b) == gcd(a, a - b) == gcd(b, a - b)

gcd(510, 20) == gcd(490, 20) == gcd(470, 20) == gcd(450, 20) == gcd(430, 20) == gcd(410, 20) == gcd(30, 20) == gcd(20, 10) ⇒ 10

❓gcd(510, 20)에서 한번에 gcd(20, 10)으로 가는 법?

⇒ 모듈러 연산으로 구할 수 있다.

gcd(a, b) == gcd(b, a % b)

import java.util.Scanner;

public class Main {

    static int getDcd(int a, int b){
        int tmp = 0;
        while (a % b != 0) {
            tmp = a % b;
            a = b;
            b = tmp;
        }

        return b;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int a = sc.nextInt();
        int b = sc.nextInt();

        System.out.println(getDcd(a, b));
    }
}

💡최소 공배수(LCM)의 경우  LCM(A, B) == A * B / GCD(A, B) 로 구할 수 있다. JAVA나 C++의 경우 오버플로우 뜰 수 있으니까 LCM(A, B) == A / GCD(A, B) * B

 

시간 복잡도

 O(  \( \log{n} \) ) 

 

에라토스테네스의 체

❓1부터 n까지의 소수를 모두 구해보자!

1️⃣ 1외에는 모두 소수라고 가정

2️⃣ i가 2부터 반복한다.

• 만약 i가 소수라면 i의 배수 모두 지우기
• 만약 i가 소수가 아니라면 스킵

예시 ) 1부터 30까지 소수 구하기

1️⃣ 2를 제외한 2의 배수들을 모두 지운다.

2️⃣ 3을 제외한 3의 배수들도 모두 지운다. (이미 칠해진 애들은 2의 배수에서 걸러졌으므로 건너 뜀)

3️⃣ 5을 제외한 5의 배수들도 모두 지운다.

계속 진행하다보면 결국 방문하지 않은 숫자들이 2부터 30까지의 소수가 된다. (1은 미리 처리)

import java.util.Arrays;
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();

        boolean[] isPrime = new boolean[n+1];
        Arrays.fill(isPrime, true);

        isPrime[1] = false;

        for (int i = 2; i < n + 1; i++) {
            if(!isPrime[i]) continue;

            for (int j = 2 * i; j < n + 1; j += i) {
                isPrime[j] = false;
            }
        }
    }
}

소수인 경우 true, 아닌 경우 false

그러나 이미 앞에서 처리한 배수들의 경우 또 반복해서 처리할 필요가 없으므로, 아래와 같이 최적화할 수 있다.

import java.util.Arrays;
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();

        boolean[] isPrime = new boolean[n+1];
        Arrays.fill(isPrime, true);

        isPrime[1] = false;

        for (int i = 2; i < n + 1; i++) {
            if(!isPrime[i]) continue;

            for (int j = i * i; j < n + 1; j += i) {
                isPrime[j] = false;
            }
        }

        for (int i = 1; i <= 30; i++) {

            System.out.print(isPrime[i] + " ");
            if(i%10==0 ) System.out.println();
        }
    }
}

 

시간 복잡도

 O(  \(n \log{n} \) ) 

 

1부터 n까지 k의 배수의 개수

n / k개

 

시간 복잡도

 O(1) 

 

n!에 곱해져 있는 소수 k의 개수

완전 탐색으로 접근

❓10!에 2가 몇 개 있는가?

 

import java.util.Arrays;
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();

        int cnt = 0, tmp = 0;
        for (int i = 1; i < n + 1; i++) {
            tmp = i;
            while (tmp % 2 == 0) {
                cnt ++;
                tmp /= 2;
            }
        }

        System.out.println(cnt);
    }
}

그러나 n의 범위가 커지면 느려지므로 최적화 할 필요가 있다. ⇒ 1부터 n까지 모두 볼 필요가 없다!

 

최적화

즉, 방향을 세로로 생각하지 말고 가로로 생각해서 계산해보자!

나누는 수가 나뉘어지는 수보다 크지 않을 때까지 계산

 

시간 복잡도

O(  \(n \log{n} \) )  => O(  \(\log{n} \) ) 

 

모듈러의 성질

나눗셈을 제외한 모든 사칙연산( +, -, * )에 모듈러 연산을 적용할 수 있다.

(나눗셈의 경우 우리가 사용하는 정수 나눗셈이 일반적이지 않은 방식이기 때문에, 페르마소 정리를 알고 처리해야 한다.)

순환을 표현할 때도 모듈러를 많이 쓴다.

 

알고리즘 문제) BOJ14620. 꽃길 

14620번: 꽃길

문제 요약
꽃 → 1년 후에 꽃핌 → 다음해 식목일 부터 꽃길을 걸을 수 있음
씨앗은 총 3개

다른 꽃과 닿으면 두 꽃 모두 죽음,
화단 밖에 나가도 죽음

가장 싸게 대여해서 세 꽃을 모두 피우려함
이때 가장 최소 비용 구하기

시간 제한
2초

입력
화단 한 변의 길이 N(6≤N≤10)
N개의 줄에 지점당 가격(0≤G≤200)

출력
최소 비용

 

접근법

• 100C3
• 전체 칸중 칸 3개를 고르고
  • 각각 꽃을 다 피울 수 있는지 체크
  • 만약 다 피울 수 있다면 ⇒ 비용 구하기
  • 계속 반복하면서 최솟값 갱신

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
    static int N; // 화단 한 변의 길이
    static int[][] prices; // 가격 정보 담을 배열
    static int[][] coords; // 좌표 정보 담을 배열
    static int[] peek;
    static int[] delR = {-1, 1, 0, 0};
    static int[] delC = {0, 0, -1, 1};
    static boolean[][] visited;
    static int row, col, mrow, mcol, price, total, answer = Integer.MAX_VALUE;

    static void plantFlower(int depth, int start){

        if(depth == 3){

            total = 0;

            for (int i = 0; i < N; i++) {
                Arrays.fill(visited[i], false);
            }

            for(int i=0; i<3; i++){
                row = coords[peek[i]][0];
                col = coords[peek[i]][1];
                price = prices[row][col];
                total += price;
                visited[row][col] = true;

                for (int dir = 0; dir < 4; dir++) {
                    mrow = row + delR[dir];
                    mcol = col + delC[dir];

                    if (mrow < 0 || mcol < 0 || N <= mrow || N <= mcol
                            || visited[mrow][mcol]) return;

                    visited[mrow][mcol] = true;
                    total += prices[mrow][mcol];
                }
            }

            answer = Math.min(answer, total);

            return;
        }

        for (int i = start; i < N*N; i++) {
            peek[depth] = i;
            plantFlower(depth + 1, i + 1);
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;


        N = Integer.parseInt(br.readLine());

        coords = new int[N*N][2];
        prices = new int[N][N];
        for (int i = 0, idx = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            for (int j = 0; j < N; j++) {
                prices[i][j] = Integer.parseInt(st.nextToken());
                coords[idx][0] = i;
                coords[idx++][1] = j;
            }
        }

        peek = new int[3];
        visited = new boolean[N][N];

        plantFlower(0,0);
        System.out.println(answer);
    }
}