1. 계산 결과를 1,000,000,007로 나눈 나머지를 출력하세요.
알고리즘 문제를 풀다보면 가끔 이런 문장을 만나곤 합니다. 주로 큰 수를 결과로 출력하기 위한 문제들에서 보입니다. 그 이유는 컴퓨터가 표현할 수 있는 숫자형에는 한계가 있기 때문입니다. 참고로 32비트 정수형의 최대값은 2,147,483,647입니다. 따라서 큰 수를 표현해야하는 알고리즘 문제에서는 특정 수의 나머지를 출력하라는 조건이 달려있곤 합니다.
2. 계산을 다하고 나누면 한 번만 나누면 될까?
정답은 '아니오.'입니다. 계산을 하다보면 컴퓨터가 인식할 수 있는 범위를 넘어선 수가 만들어지기도 합니다. 그게 아니더라도 큰 수를 너무 많이 계산하다보면 시간이 너무 오래 걸리거나, 메모리를 초과할 수도 있습니다. 따라서 계산 중간 필요한 순간마다 해당 값으로 나누는 과정이 필요합니다.
3. 계산 도중에 나누었다가 결과가 달라지면 어떡하지?
이런 궁금증이 생겼습니다. 계산 중인 값을 도중에 나머지로 바꿔서 계산을 하다가 결과값이 달라지진 않을까? 조금만 생각해보면 그렇게 해도 괜찮은 상황이 있다는 것을 알 수 있습니다.
A와 B를 계산할 때, 계산하기 '전'에 나누는 것과 계산 '후'에 나누는 것이 나머지에 어떤 영향을 줄까요? A를 m으로 나눈 나머지를 c라고 하고, B를 m으로 나눈 나머지를 d라고 합시다. 아래와 같이 덧셈, 뺄셈, 곱셈을 해보면 결과값을 m으로 나누었을 때, 나머지도 '같은 연산'을 한 값이라는 것을 알 수 있습니다. (다만, 결과값의 나머지가 0보다 작거나, m보다 크다면 한 번 더 m으로 나누면 됩니다.) 결과적으로 사칙연산 중에 나눗셈만 빼면 계산 중에 나누어도 괜찮다는 것을 알 수 있었습니다.
4. 그럼 나눗셈도 할 수 있을까?
이러한 계산의 나눗셈은 분배법칙이 적용되지 않습니다. 대신 역수를 곱하는 방법으로 변경하여 곱셈의 역원을 구하여 해결할 수 있습니다. 이를 위해 모듈러 역수, 확장 유클리드 호제법, 페르마의 소정리 등으로 검색해보면 도움이 될 것입니다. 이 글에서 자세히 설명하지 않는 이유는... 사실 저도 아직 정확히 모르기 때문입니다...ㅠㅠ 하지만 더 공부할 것이 있다는 건 즐거운 일이겠죠? :)
5. 왜 하필 1,000,000,007로 나눌까?
앞서 살펴본 이유들로 인해 1,000,000,0007이 사용하기 적합한 수이기 때문입니다.
먼저, 32비트 정수의 최대값이 2,147,483,647이기 때문에 1,000,000,007로 나눈 나머지는 덧셈에 대해서 32비트 정수의 최대값을 넘지 않음을 보장할 수 있습니다. 그리고 1,000,000,007로 나눈 나머지는 서로 곱해도 64비트 정수의 최대값(9,223,372,036,854,775,807)보다 작다는 장점도 있습니다.
다음으로, 모듈러 역수를 구하기 쉽습니다. 모듈러 역수를 구하는 쉬운 방법은 페르마의 소정리를 이용하는 것입니다. 페르마의 소정리를 이용하기 위해서는 나누는 수가 소수여야 합니다. 마침 1,000,000,007은 소수입니다. 다시 말해 페르마의 소정리를 이용하여 모듈러 역수를 쉽게 찾을 수 있다는 장점이 있습니다.
큰 수의 계산을 여러 차례 반복하다보면 값이 너무 커져서 오버플로우가 발생하게 됩니다.
이 오버플로우를 막기 위해 1,000,000,007로 나누어 가면서 계산하는 것처럼,
우리의 인생에서 마주하게 되는 큰 문제들도
소중한 사람들과 함께 나누어 간다면 오버플로우가 발생하지 않고 잘 해결할 수 있지 않을까요?
