배열 곱셈을 n으로 나눈 나머지를 구하는 파이썬 프로그램

이 글에서는 아래 문제 상황에 대한 해결 방법을 알아봅니다.

문제 정의

여러 개의 숫자로 이루어진 배열과 하나의 수 n이 주어졌을 때, 배열의 모든 원소를 곱한 결과를 n으로 나눈 나머지를 출력해야 합니다.

접근 방법

• 먼저 각 원소에 대해 arr[i] % n과 같이 나머지를 구한 뒤, 그 나머지를 현재까지의 결과값에 곱합니다.

• 곱셈을 마친 후에는 다시 한 번 n으로 나눈 나머지를 취해 중간 계산값이 너무 커지는 것(오버플로우)을 방지합니다. 이는 모듈러 산술의 분배 법칙에 근거한 것입니다.

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

예제 코드

def findremainder(arr, lens, n):
    mul = 1
    # 각 원소의 나머지를 구해 누적으로 곱함
    for i in range(lens):
        mul = (mul * (arr[i] % n)) % n
    return mul % n

# 실행 코드
arr = [100, 1, 2, 3, 4, 5, 6, 6, 7]
lens = len(arr)
n = 11
print(findremainder(arr, lens, n))

출력 결과

1

동작 원리

위 예제에서 100을 11로 나눈 나머지는 1입니다. 이후 나머지 원소들(1, 2, 3, 4, 5, 6, 6, 7)의 나머지를 차례대로 곱하면서 매번 11로 나눈 나머지만 남기면 최종 결과는 1이 됩니다. 중간 계산값이 항상 n보다 작게 유지되므로, 큰 수를 한 번에 곱할 때 발생할 수 있는 오버플로우를 효과적으로 피할 수 있습니다.

참고로 파이썬은 임의 정밀도 정수를 지원하기 때문에 오버플로우가 발생하지 않지만, C나 C++처럼 고정 크기 정수형을 사용하는 언어에서는 이 기법이 특히 유용하게 활용됩니다.

결론

이 글에서는 모듈러 산술의 분배 법칙을 활용하여 배열 전체 곱셈 결과를 n으로 나눈 나머지를 효율적으로 구하는 방법을 살펴보았습니다. 매 단계마다 나머지 연산을 적용하면 중간값이 커지지 않아 안전하고 빠르게 답을 얻을 수 있습니다.