[삼성SDS] 24년 하반기 대학생 알고리즘 특강(Day5) : 정수론(유클리드 호제법, 확장 유클리드 호제법, 소수), 조합론

유클리드 호제법

• 빠른 시간에 두수의 최대공약수를 구할 수 있는 방법이다.
• 2개의 자연수의 최대공약수를 구하는 알고리즘의 하나이다.
• 2개의 자연수 a, b에 대해서 a를 b로 나눈 나머지를 r이라 하면(단, a > b), a와 b의 최대공약수는 b와 r의 최대공약수와 같다는 성질을 이용한다.
• gcd(a, b) = gcd(b, r)

 

공식 대입해보기

a = 36, b = 24

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

gcd(36, 24)

= gcd(24, 12)

= gcd(12, 0)

r == 0 일 때, b가 최대공약수가 된다.

 

예제문제

백준 14476번 : 최대공약수 하나빼기 

https://www.acmicpc.net/problem/14476

 

최대공약수 구하는 메소드

// gcd(a, b) == gcd(b, r) : r = a % b
static int gcd(int a, int b) {
    while (b != 0) {
        int r = a % b;
        a = b;
        b = r;
    }
    return a;
}

 

자세한 코드 풀이법은 아래 참고해주세요.

[코테] 백준 14476번 : 최대공약수 하나 빼기 (java)

 

 

 

---

확장 유클리드 호제법

• 유클리드 호제법을 확장하여, 두 정수 a와 b의 최대 공약수(GCD)를 구하는 것뿐만 아니라, 베주 항등식(Bézout's identity)을 만족하는 정수 쌍 x와 y를 찾는 알고리즘이다.

 

확장 유클리드 호제법 관련 정식

1. 부정 방정식

• 해가 무수히 많은 방정식
• 미지항의 개수보다 방정식의 개수가 작을 경우도 부정방정식에 포함된다.

 

2. 디오판토스 방정식

• 해가 정수인 경우의 부정 방정식 (3x + 2y = 5)

 

3. 베주 항등식

• 정수 a, b의 최대공약수 gcd(a, b)로 나타낼 때, 확장 유클리드 호제법을 이용하여, ax + by = gcd(a, b)의 해가 되는 정수 x, y 짝을 찾아낼 수 있다.(x, y 중 한개는 보통 음수가 된다.)
• ax+by=gcd(a,b)

 

 

예제 문제

백준 3955번 : 캔디 분배

https://www.acmicpc.net/problem/3955

 

확장 유클리드 호제법을 통해 s, t, r를 구하는 메서드

public static EGResult egcd(long a, long b) {
    long s0 = 1, t0 = 0, r0 = a; // 마지막 s,t,r이 될 것임
    long s1 = 0, t1 = 1, r1 = b;

    long temp;
    // b기준이었으나 현재 b는 r1
    while (r1 != 0) {
        long q = r0 / r1;

        temp = r0 - r1 * q; // 새로운 나머지
        r0 = r1;
        r1 = temp;

        temp = s0 - s1 * q;
        s0 = s1;
        s1 = temp;

        temp = t0 - t1 * q;
        t0 = t1;
        t1 = temp;
    }

    return new EGResult(s0, t0, r0);
}

 

 

자세한 코드 풀이법은 아래 참고해주세요.

[코테] 백준 3955번 : 캔디 분배 (java)

 

 

 

---

소수 (Prime Number)

• 소수는 1과 자기 자신 외에는 나누어떨어지지 않는 자연수이다.
• 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, ...

 

에라토스테네스의 체

• 주어진 범위 내의 모든 소수를 찾는 매우 효율적인 방법이다.
• 2부터 시작하여 특정 수의 배수를 모두 지우는 과정을 반복하여 소수를 찾는다.
• 위키피디아 설명 : https://ko.wikipedia.org/wiki/%EC%97%90%EB%9D%BC%ED%86%A0%EC%8A%A4%ED%85%8C%EB%84%A4%EC%8A%A4%EC%9D%98_%EC%B2%B4

에라토스테네스의 체 - 위키백과, 우리 모두의 백과사전

 

 

순서

1. 초기화: 2부터 n까지의 모든 수를 나열한다.
2. 첫 번째 소수 선택: 현재 남아있는 가장 작은 수를 소수로 선택합니다. 초기에는 2를 소수로 선택한다.
3. 배수 지우기: 선택된 소수의 배수를 모두 지운다.
4. 반복: 남아있는 가장 작은 수를 소수로 선택하고, 그 배수를 모두 지운다. 이 과정을 반복하여 원하는 범위 내의 모든 소수를 찾는다.
5. 종료: 선택된 수의 제곱이 n보다 큰 경우, 반복문을 탈출한다.

 

예제 문제

백준 1837번 : 암호제작

https://www.acmicpc.net/problem/1837

 

문제의 조건중 K까지의 소수 배열을 생성하는 코드는 아래와 같다.

//에라토스테네스의 체 생성
for (int i = 2; i < K; i++) {
    if (!checked[i]) {
        primes.add(i);
        for (int j = i; j < K; j += i) {	//i의 배수 탐색
            checked[j] = true;
        }
    }
}

 

자세한 코드 풀이법은 아래 참고해주세요.

[코테] 백준 1837번 : 암호제작 (java)

 

---

조합 (Combination)

• N가지의 물건 중 K개의 물건을 순서 구분없이 고르는 경우의 수
• 예를 들어, {A, B, C}라는 집합에서 2개의 원소를 선택하는 조합은 {A, B}, {A, C}, {B, C}가 있으며, {A, B}와 {B, A}는 같은 조합으로 취급된다.

조합 생성 메소드

public static int combination(int n, int k) {
    if (n == k || k == 0) {
   		return 1;
    } else if (dp[n][k] != 0) {
    	return dp[n][k];
    } else {
    	return dp[n][k] = Math.min((int) 1e9, combination(n - 1, k - 1) + combination(n - 1, k));
    }
}

 

선택사항)

Math.min((int) 1e9, ...): 

계산된 조합 값이 10^9 (즉, 1,000,000,000)보다 큰 경우, 상한을 적용하여 최대값을 10^9로 제한한다.
조합의 수가 매우 커질 수 있기 때문에, 특정 문제에서 오버플로우를 방지하기 위해 위 같은 제한을 둔다.

 

 

예제 문제

백준 1256번 : 사전

https://www.acmicpc.net/problem/1256

 

조합 표

 

조합 문제를 풀 때는 조합 배열을 만들어야(메모리제이션) 불필요한 연산을 막을 수 있다.

위 조합 생성 메소드를 참고하여 생성한다.

 

자세한 코드 풀이법은 아래 참고해주세요.

[코테] 백준 1256번 : 사전 (java)