Boj 13171
Boj 1629

Modular 정리

명제 : (A * B)%N = ((A%N) * (B%N)) % N

증명:

1. 정리의 의미:

• A * B를 N으로 나눈 나머지는,
  A와 B를 각각 N으로 나눈 나머지를 곱한 후에 다시 N으로 나눈 나머지와 같다.

2. 수학적 표현:

• A = q1 * N + r1 => r1 = A % N
• 여기서 q1은 A를 N으로 나눈 몫이고, r1은 나머지
• B = q2 * N + r2 => r2 = B % N
• 여기서 q2는 B를 N으로 나눈 몫이고, r2는 나머지

3. 좌변 전개:
   (A * B) % N

(A * B) % N = ((q1 * N + r1) * (q2 * N + r2)) % N

4. 식 전개:

= (q1 * N * q2 * N + q1 * N * r2 + q2 * N * r1 + r1 * r2) % N

여기서 중요한 점은, N의 배수는 %N을 취하면 항상 0이 된다는 것입니다:

• q1 * N * q2 * N % N = 0
• q1 * N * r2 % N = 0
• q2 * N * r1 % N = 0

따라서, 위의 식은 다음과 같이 단순화됩니다:

(A * B) % N = (r1 * r2) % N

5. 우변 전개:

((A % N) * (B % N)) % N

• 이는 r1 = A % N이고 r2 = B % N이므로:

((A % N) * (B % N)) % N = (r1 * r2) % N

6. 결론:

(A \times B) \% N = ((A \% N) \times (B \% N)) \% N

분할 정복

분할 정복(Divide and Conquer)은 문제를 작은 부분 문제로 나누어 해결하고, 부분 문제의 해를 결합하여 원래 문제의 해를 구하는 전략입니다. 이 알고리즘은 문제를 재귀적으로 해결하는 데 자주 사용됩니다.

분할 정복의 3단계

1. 분할(Divide):

• 문제를 더 작은 하위 문제들로 분할합니다.
• 보통 문제의 크기를 반으로 줄이는 식으로 나누는 경우가 많습니다.

2. 정복(Conquer):

• 분할된 하위 문제들을 각각 해결합니다.
• 하위 문제가 충분히 작으면 직접 해결하고, 그렇지 않으면 다시 분할 정복을 적용합니다.

3. 결합(Combine):

• 하위 문제의 해를 합쳐서 원래 문제의 해를 구합니다.

분할 정복 알고리즘은 큰 문제를 작은 문제로 나누어 해결하는 효율적인 접근법입니다. 다양한 알고리즘에 적용되며, 재귀를 통한 문제 해결에서 자주 사용됩니다.

Boj 1629 문제를 통한 알고리즘 해설

package BOJ;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

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

        String[] input = br.readLine().split(" ");

        int a = Integer.parseInt(input[0]);
        int b = Integer.parseInt(input[1]);
        int c = Integer.parseInt(input[2]);

        long answer = modularExponentiation(a, b, c);
        System.out.println(answer);
    }


    // 분할 정복을 이용한 거듭제곱
    private static long modularExponentiation(long base, long exp, long mod) {
        if (exp == 0) {
            return 1; // A^0 = 1
        }

        // A^(B/2) // 분할 단계
        long half = modularExponentiation(base, exp / 2,  mod);
        half = (half * half) % mod; // 정복 및 결합

        // B가 홀수일 경우 추가로 base를 곱해준다.
        if (exp % 2 != 0) {
            half = (half * base) % mod; // 홀 수 처리 
        }

        return half;
    }
}

분할 정복을 이용한 거듭제곱:

1. 분할(Divide):

• 지수 B를 반으로 나누어 문제를 작게 나눕니다.
• 예를 들어, A^8 을 계산할 때, A^4 * A^4 로 나눌 수 있습니다.
• 일반적으로 A^B 는 A^(B/2) * A^(B/2) 로 표현할 수 있습니다.

2. 정복(Conquer):

• 작은 문제들을 재귀적으로 계산합니다.
• 만약 B/2 까지의 결과를 이미 계산했다면, 이를 제곱하여 B 에 대한 결과를 구합니다.
• 이를 통해 큰 연산을 여러 개의 작은 연산으로 나누어 수행합니다.

3. 결합(Combine):

• 재귀적으로 계산한 A^(B/2) * A^(B/2) 를 합쳐서 A^B 를 구합니다.
• 만약 B가 홀수라면, 결과에 A 를 한 번 더 곱합니다.

시간 복잡도

• O(log B): 지수 B 를 매번 반으로 나누기 때문에, 재귀 호출의 깊이가 약 log B 가 됩니다. 따라서 시간 복잡도는 O(log B)입니다.

결론

이 알고리즘이 분할 정복인 이유는, 문제를 절반으로 분할하여 재귀적으로 해결하고, 부분 문제를 결합하여 원래 문제를 해결하기 때문입니다. 이를 통해 효율적으로 큰 지수를 다룰 수 있게 됩니다.