[Java] 거듭제곱 계산

문제

두 수를 입력받아 거듭제곱을 리턴해야 합니다.

입력

인자 1: base

• int 타입의 자연수 (base >= 2)

인자 2: exponent

• int 타입의 정수 (exponent >= 0)

출력

• long 타입으로 리턴
• 실제 계산 결과를 94,906,249로 나눈 나머지를 리턴

주의

• Math.pow 사용 불가
• 시간복잡도 O(logN) 만족

문제부터 이해하기가 정말 오래 걸렸다.
애초에 수포자였기도 해서 더 오래걸렸던것같은데 그 중 가장 많이 잡아 먹은게 왜 94,906,249의 나머지를 리턴하는 것인지에 대해 전혀 감도 잡히지 않아 큰 문제였다.

정말 감사하게도 동기분의 도움을 받아 알아본 결과 '모듈러 곱셈 역원' 과 관계있다고 한다.

모듈러 곱셈 역원까지 이해하기에는 수학이 많이 요구되는 터라 수포자인 나는 도저히 이해할수 없었고 내가 조금이나마 이해할 수 있던 부분은

왜 94,906,249로 나눈 나머지를 요구하는 것일까?

까지였다.

이 부분에는 여러 이유가 존재했다.

이유?

1. 프로그래밍 언어에서 자료형의 범위에는 제한이 있고 큰 수끼리의 연산이 느리다.

   • 범위에 제한이 있기에 범위는 넘어설수밖에 없고 오버플로우가 발생한다.
   • 이는 결국 결과가 정확하지 않게된다.

2. 알고리즘 사이트에서는 보통 1,000,000,007 로 나눈 나머지를 구하라는 문제가 많은데, 1,000,000,007과 94,906,249의 공통점은 소수라는 것이다.

   • 소수에는 다양한 장점이 있다.
     • 풀이의 정확도 요구
     • 모듈러 곱셈 역을 구하는 방법이 간단
   • 소수가 아닌 약수는 모듈러 연산 결과가 겹칠 확률이 높다.

내가 이해한 이유는 여기까지이고 이해한것에 따라 식을 구성해보았다.

public long power(int base, int exponent) {
	// 1. 94906249 의 수를 매번 반복해서 쓰기 힘들기에 변수에 할당해주었다.
    int dec = 94906249;
    
    // 2. 시간복잡도 O(logN)을 만족해야하니 2로 나눠야한다
    int half = exponent / 2;
    
    // 3. 재귀를 통해 반복해준다
    long rec = power(base, half);
    
    // 4. 2로 나눴으니 곱해준다.(연산마다 94906249의 나머지를 리턴하라했다)
    long pow = (rec * rec) % dec;
    
    // 5. 밑 설명 참조
    if (exponent % 2 == 1) return (base * pow) % dec;
    else return pow;

5. exponent를 2로 나눴을때 나머지가 1이라면 홀수라는 의미.
   그 의미는 예를 들어 base = 3, exponent = 7이라고 했을때
   구해야하는 수 : 3⁷
   시간복잡도 적용한 수 : 3ⁿ∕² = 3³ 이므로
   3³ × 3³ = 3⁶ 이 된다.
   3이 모자르기 때문에 한번을 더 곱해줘야 한다.
   그렇기때문에 한번의 연산이 더 필요로 한 것이며 연산이 주어졌으니 추가로 94,906,249의 나머지를 구해주면 된다.

---

이 문제는 내가 어려워하는 것들의 총합이었다.
시간복잡도, 수학, 재귀.. 그래도 어떻게든 이해를 한것같다.
이 문제를 푸는데 정말 큰 도움을 주신 동기분께 매우 큰 감사를 드린다🙇🏻‍♀️