이 튜토리얼에서는 문자열 형태로 표현된 매우 큰 숫자를 나누는 방법을 알아봅니다.
C++의 기본 정수 자료형은 대략 19자리 숫자까지만 저장할 수 있기 때문에, 그 이상의 큰 숫자는 문자열로 표현해야 합니다. 이번 예제에서는 문자열로 주어진 큰 숫자와 나누는 수(제수)가 주어졌을 때, 나눗셈의 결과인 몫을 구하는 프로그램을 작성해 보겠습니다.
핵심 아이디어는 간단합니다. 먼저 주어진 숫자에서 제수보다 크거나 같은 부분을 찾아 나눗셈을 수행하고, 그다음 남은 자릿수를 하나씩 붙여가며 나눗셈을 반복하는 것입니다. 이는 우리가 손으로 세로 나눗셈을 계산하는 과정과 정확히 동일한 원리입니다.
문제 해결 단계
- 큰 숫자(문자열)와 제수를 초기화합니다.
- 주어진 숫자를 처음부터 탐색하면서 제수보다 커지는 부분을 추출합니다.
- 추출한 부분을 제수로 나누고, 그 결과를 몫에 추가합니다.
- 나눗셈 후 남은 나머지에 다음 자릿수를 이어 붙여 새로운 피제수를 만듭니다.
- 모든 자릿수를 처리할 때까지 위 과정을 반복합니다.
- 결과가 비어 있으면 "0"을 반환하고, 그렇지 않으면 최종 결과를 출력합니다.
예제 코드
전체 코드를 살펴보겠습니다.
#include <bits/stdc++.h>
using namespace std;
string divideLargeNumber(string number, int divisor) {
// 결과를 저장할 문자열
string result;
int index = 0;
// 제수보다 큰 피제수 부분을 추출
int dividend = number[index] - '0';
while (dividend < divisor) {
dividend = dividend * 10 + (number[++index] - '0');
}
// 모든 자릿수가 나눗셈에 참여할 때까지 반복
while (number.size() > index) {
result += (dividend / divisor) + '0';
// 다음 자릿수를 피제수에 추가
dividend = (dividend % divisor) * 10 + number[++index] - '0';
}
if (result.length() == 0) {
return "0";
}
return result;
}
int main() {
string large_number = "12345678901234567890";
int divisor = 75;
cout << divideLargeNumber(large_number, divisor) << endl;
return 0;
}실행 결과
위 프로그램을 실행하면 다음과 같은 결과가 출력됩니다.
164609052016460905
코드 설명
divideLargeNumber 함수는 문자열로 된 숫자와 정수형 제수를 입력받습니다. 첫 번째 while 루프는 제수보다 작은 동안 자릿수를 하나씩 추가하여 유효한 피제수를 만듭니다. 두 번째 while 루프에서는 각 단계마다 (dividend / divisor)를 결과 문자열에 추가하고, (dividend % divisor) * 10 + 다음 자릿수로 피제수를 갱신합니다.
이 알고리즘은 문자열의 길이를 N이라 할 때 O(N)의 시간 복잡도를 가지므로, 수백 자리에 달하는 매우 큰 숫자도 빠르게 처리할 수 있습니다.
마무리
이 방식을 활용하면 long long 범위를 훌쩍 넘는 거대한 숫자도 문제없이 나눗셈할 수 있습니다. 튜토리얼에 대해 궁금한 점이 있다면 댓글로 남겨주세요.