[백준] 1629번 : 곱셈 | C++

0. 문제

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

 

세 개의 정수 a, b, c가 주어졌을 때, a^b % c의 값을 0.5초 안에 구해내는 문제입니다. 

---

1. 문제풀이 핵심

간단히 핵심만 짚고 넘어가겠습니다. 

 

 

1. 모듈러 연산의 규칙을 알고 활용해야 한다
큰 수의 연산을 피해야하기 때문에 모듈러 연산 규칙이 필요합니다. 아래가 모듈러 연산 규칙입니다. 아래서 자세히 설명하겠습니다. 

//모듈러 연산의 규칙
(a * b) % c = (a % c * b % c) % c

큰 수의 연산이란
- a와 b의 최대 범위가 모두 21억이므로 long long으로 선언해도 그 둘을 곱한 값은 long long의 범위를 벗어날 수 있습니다.

그러므로 a와 b를 곱하기 전에, 모듈러 연산 규칙을 사용해서 "a를 c로 나눈 나머지값과 b를 c로 나눈 나머지값을 곱하도록" 하여 곱셈 결과가 자료형의 범위를 넘지않도록하는게 중요합니다. 

 

2. 재귀 함수를 통한 시간복잡도 O(log n)의 로직 구현
단순히 a를 b번 곱하는 방법은 O(b)의 시간복잡도를 가지며 이는 문제의 시간제한이 0.5초이므로 시간초과에 걸리게 됩니다. 대신 재귀적으로 계산하여 연산 횟수를 반토막씩 줄여 O(log n)의 시간 복잡도를 가지도록 해야 합니다.

 

이에 대한 자세한 설명은 2. 문제 풀이에 사용된 개념 에서...

---

2. 문제풀이에 사용된 개념

2-1. 모듈러 연산 규칙 _ 합, 차, 곱 분해의 법칙(임의의 명칭)

2-2. n의 크기와 시간제한을 통해 문제가 요구하는 시간복잡도를 찾아내기

 

2-1 . 합 ,차,곱 분해 법칙 (임의의 명칭)

모듈러 연산의 특징 중 합하는 요소 각각에 모듈러 연산을 수행한 값과 같습니다.

(a + b) % c = (a % c + b % c) % c 
(a - b) % c = (a % c - b % c) % c 
(a * b) % c = (a % c * b % c) % c

 

각 단계마다 모듈러 연산을 적용하지 않으면 숫자가 매우 커질 수 있어 long long 자료형의 범위를 벗어나게 될 수 있습니다.

 

2-2. 주어진 시간 제한에 따라 요구되는 시간복잡도 로직 찾아내기

알고리즘 문제를 풀 때에는 시간제한과 n의 범위(최댓값)를 통해 이 문제가 나에게 요구하는 시간복잡도, 그에 해당하는 알고리즘을 추정해서 문제를 풀게됩니다.

 

이 문제의 경우 b의 범위가 최대 21억으로, 브루트포스하면 시간 복잡도가 O(21억)이 됩니다.

      ** 브루트포스 방식: for문으로 a를 하나하나 곱하는 걸 b번 수행한 후, 그 결과를 c로 나눈 나머지를 구하는 것

-> 이는 시간 제한(0.5초) 내에 계산이 불가능합니다. 

 

보통 코딩 테스트에서 시간 제한이 1초인 경우, 반복 횟수(n)가 10,000,000 이하이면 O(n)인 브루트 포스 방법을 사용할 수 있습니다.  즉 단순 탐색이나 for문으로 처음부터 끝까지 훑는 방식을 사용해도 됩니다.

하지만 이 문제에서는 n이 10,000,000 이상이므로, O(log n)의 시간복잡도를 가진 알고리즘을 사용해야 합니다.

 

 

a^b % c를 구하기 위한 브루트포스 방법 VS 분할하여 계산(=분할 정복)하는 방법의 시간 복잡도 비교

a. 브루트포스 (a를 b번 곱하고 % c)
'a'를 'b'번 곱해야 하기 때문에 매우 비효율적입니다.

시간 복잡도 : O(b)

 

b. 지수에 대해 분할 정복
b를 반으로 나누며 재귀함수를 호출합니다. 이 방법은 "거듭제곱을 분할하여 계산하는 방법 (Exponentiation by Squaring)"이라고 불립니다. 지수를 매번 반으로 나누기 때문에 재귀 호출의 깊이는 log₂(b)가 되며, 각 단계에서는 상수 시간의 연산이 이루어집니다.

시간 복잡도 : O(log b)

 

따라서, 지수를 단순 반복으로 계산하는 것보다 분할 정복을 사용하면 시간 복잡도가 훨씬 줄어듭니다. 특히, 'b'가 매우 큰 경우, 큰 시간차이를 가져옵니다.

ex. b = 1,000,000일 때 단순 반복은 백만 번의 연산이 필요하지만, 분할 정복은 약 20번의 연산으로 결과를 얻을 수 있다

 

---

 

3. 문제풀이 코드

#include<bits/stdc++.h>

using namespace std;
#define ll long long

ll a,b,c,res;

int go(int a, int b){ //밑과 지수를 입력받는다 //a의 b승
    if(b==1){ //종료 조건 
        return a%c; 
    }
    ll res = go(a,b/2); //일단 가장 작은 단위까지 들어가야되서 쭉쭉 들어가야됨
    res = (res*res)%c;
    
    if(b%2) res = (res*a)%c;
    return res; //다시 되돌아오며 본인의 결과값을 자기를 호출한 함수에게 던져주기 위함
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin>>a>>b>>c;
    res = go(a,b);
    
    cout << res;
}

 

 

3-1. 코드 로직 설명

 

1. 지수를 절반씩 분할

• a^b = a^(b/2) * a^(b/2)를 이용하여 b를 절반으로 줄여 계산합니다.
• a^(b/2) 값을 저장하여 같은 연산을 두번하지 않도록 합니다.

2. 재귀 호출

• b == 1일 때, 종료 조건으로 a % c를 반환합니다.
• 재귀적으로 b를 반으로 줄여가며 최종적으로 a를 한 번 곱한 값까지 내려갑니다.
• 그 후, 되돌아오며 이전에 계산한 값을 이용해 현재 단계의 값을 계산합니다.
• 이를 통해 불필요한 중복 계산을 줄입니다.

---

4. 요약 정리

 

• 문제 핵심: 큰 수를 다루기 위해 모듈러 연산의 규칙을 활용해야합니다.
• 접근 방법: 단순히 a를 b번 곱하는 방식은 0.5초와 21억이라는 큰 숫자에 의해 불가능함을 깨닫고, b를 반으로 나누어 재귀적으로 계산하는 분할 정복 방식을 사용합니다.
• 시간 복잡도: 단순 반복을 통한 계산의 시간 복잡도는 O(b)이지만, 분할 정복 방식을 사용하면 O(log b)가 됩니다.
• 코드 구현: 재귀 함수를 통해 b를 반으로 줄여가며 계산하고, 되돌아오면서 최종 결과를 도출합니다.