이 글에서는 배열의 모든 요소를 곱한 결과를 n으로 나눈 나머지를 구하는 방법을 알아보겠습니다. 배열과 n 값은 사용자가 입력한다고 가정합니다. 예를 들어 배열이 {12, 35, 69, 74, 165, 54}라면 전체 곱은 (12 × 35 × 69 × 74 × 165 × 54) = 19107673200이 되고, 이 값을 47로 나눈 나머지는 14입니다.
언뜻 보면 이 문제는 아주 간단해 보입니다. 배열의 모든 요소를 곱한 뒤 나머지 연산자(%)만 적용하면 되기 때문입니다. 하지만 여기에는 중요한 함정이 숨어 있습니다. 곱셈 결과가 int나 long 자료형의 표현 범위를 초과하면 오버플로우가 발생하여 잘못된 값이 반환될 수 있습니다.
핵심 아이디어: 단계별 모듈로 연산
이 문제는 모듈로 연산의 수학적 성질을 이용해 해결할 수 있습니다.
(a × b) mod n = ((a mod n) × (b mod n)) mod n
즉, 요소를 하나씩 곱할 때마다 즉시 n으로 나눈 나머지를 구하면, 중간 곱셈 값이 항상 n보다 작게 유지됩니다. 따라서 어떤 큰 수가 입력되더라도 자료형의 범위를 초과하지 않아 오버플로우를 완전히 피할 수 있습니다.
알고리즘
multiplyRemainder(arr, size, n)
begin
mul := 1
i를 0부터 size-1까지 반복:
mul := (mul * (arr[i] mod n)) mod n
return mul mod n
end
C++ 구현 예제
#include<iostream>
using namespace std;
int multiplyRemainder(int arr[], int size, int n){
int mul = 1;
for(int i = 0; i<size; i++){
mul = (mul * (arr[i] % n)) % n;
}
return mul % n;
}
int main(){
int arr[6] = {12, 35, 69, 74, 165, 54};
int size = 6;
int n = 47;
cout << "나머지: " << multiplyRemainder(arr, size, n);
}
동작 과정 상세 분석
예제 입력에 대해 코드가 어떻게 진행되는지 단계별로 살펴보겠습니다.
- 초기값: mul = 1
- i=0: mul = (1 × (12 % 47)) % 47 = 12
- i=1: mul = (12 × (35 % 47)) % 47 = 420 % 47 = 44
- i=2: mul = (44 × (69 % 47)) % 47 = (44 × 22) % 47 = 968 % 47 = 28
- i=3: mul = (28 × (74 % 47)) % 47 = (28 × 27) % 47 = 756 % 47 = 4
- i=4: mul = (4 × (165 % 47)) % 47 = (4 × 24) % 47 = 96 % 47 = 2
- i=5: mul = (2 × (54 % 47)) % 47 = (2 × 7) % 47 = 14
모든 단계에서 mul은 47보다 작은 값을 유지하므로, 최종 곱인 19107673200처럼 큰 숫자를 직접 계산하지 않고도 정확한 나머지를 얻을 수 있습니다.
실행 결과
나머지: 14
이 프로그램의 시간 복잡도는 배열을 한 번만 순회하므로 O(n)입니다. 공간 복잡도 역시 추가 메모리가 거의 필요 없는 O(1)로 매우 효율적입니다. 이 기법은 배열뿐 아니라 팩토리얼, 거듭제곱 등 곱셈 결과가 기하급수적으로 커지는 다양한 문제에서도 널리 활용됩니다.