C++에서 long long int에도 담기지 않는 수가 있다. 9,223,372,036,854,775,807이 가장 큰 수라고 하는데, 그것보다 더 큰 수를 계산해야 하는 경우는 어떻게 해야 할까? 2^1239 을 계산하고 싶을 땐 어떻게 해야 할까? 그 방법 중 하나가 문자열로 곱셈과 덧셈을 구현하는 것이다.
원리는 아주 간단하다. 손으로 두자릿수의 곱셈과 덧셈을 해보자. 한 자리씩 더하거나 곱할 때 carry가 발생하면 다음 자리수로 넘겨서 더해준다. 따라서 손으로 하는 필산을 프로그램으로 구현한 것이 되겠다.
1. sum
두 수를 문자열로 받고, 뒷 자리수부터 시작해서 carry 가 발생할 경우 자리수 올림까지 고려한다. 두 수의 덧셈을 문자열로 반환한다.
이때 a[Sizea]에서 0을 빼는 건 뭐냐! 라고 생각할 수 있는데, 그렇게 하면 숫자를 ASCII코드의 값이 된다. 참고로 0, 1, 2, 3..은 연달아 있으니까 0의 값을 빼면 해당하는 숫자가 num1 혹은 num2에 할당되는 구조다.
string sum(string& a, string& b) {
int Sizea = a.length();
int Sizeb = b.length();
int cr =0;
string ssum = "";
while (Sizea > 0 || Sizeb > 0) {
int num1 = 0;
if(Sizea>0){
Sizea--;
num1 = a[Sizea]-'0';
}
int num2 = 0;
if (Sizeb > 0) {
Sizeb--;
num2 = b[Sizeb]-'0';
}
int rem = num1 + num2 + cr;
cr = rem / 10;
rem = rem%10;
char cur = rem +'0';
ssum += cur;
}
if (cr > 0) {
ssum += cr +'0';
}
string tot = "";
int i =0;
for (i = (int)ssum.length()-1; i >= 0; --i) {
tot += ssum[i];
}
return tot;
}
2. times
임의의 양수와 한 자리 수의 곱을 나타냈다. 두 수를 모두 문자열로 받는다. 두 수의 곱셈을 문자열로 반환한다.
이때 임의의 수 * 한 자리 라는 점을 명심하자.
string times(string& a, string& b){
int Size1=a.length();
string time = "";
int carry = 0;
while(Size1>0){
int num = 0;
if(Size1>0){
Size1--;
num=a[Size1]-'0'; //아스키 코드를 활용해서 num에 숫자 할당
}
int s = num*(b[0]-'0')+carry;
int remain = s%10;
carry =s/10;
char rem = remain + '0';
time += rem;
}
if (carry > 0) {
time += carry +'0';
}
int i =0;
string tot = "";
for (i = (int)time.length()-1; i >= 0; --i) {
tot += time[i];
}
return tot;
}
3. times2
임의의 양수와 임의의 정수의 곱을 나타낸다. 두 수를 모두 문자열로 받는다. 두 번쨰로 받은 수를 각 자리수별로 쪼갠 다음, times를 통해 첫 번째 수를 곱한다. 곱한 수를 sum을 이용해 더한다. 모든 자리수에 대해 곱을 구해서 더한 다음, 그 값을 문자열로 반환한다.
times가 임의의 양수 * 한자리니까 이번에는 임의의 양수 * 임의의 양수인 경우다. 나중에 곱해지는 수를 자리수마다 하나씩 분해해서 times()를 통해 처리한다. 그리고 str1 += '0';을 보면 알 수 있듯이, 연산값에 자리수만큼 0을 하나씩 더 붙여준 다음에 기존의 값과 sum()을 통해 합쳐서 다시 str에 저장했다.
string times2(string& a, string&b){
int k = b.length();
int i=0;
string str="0";
while(k>0){
if(k>0){
k--;
string box = "";
box += b[k];
string str1 = times(a,box);
int j;
for(j=i;j>0;j--){
str1 += '0';
}
i++;
str=sum(str,str1);
}
}
return str;
}
4.power
제곱을 계산한다. n와 k를 받는다. while 문을 이용해서 n을 k번 곱한다. times2를 이용해서 n * n의 값을 구하고, 그 값을 저장한다. 또 그 값을 다시 times2에 넣어서 n을 곱한다.
string power(string& a, string& b){
std::stringstream ss(b);
int n;
ss >> n;
if(n==0){
return "1";
}
if(n==1){
return a;
}
string str = times2(a,a);
while(n-2>0){
n--;
str=times2(str,a);
}
return str;
}
2^260와 같은 큰 수! 이 방법으로 계산하면 오버플로도 안 나고 빠르게 계산할 수 있다.
개인적으로 필산 구현하기는 기본적으로 꼭 한번은 구현해봐야 하는 로직인 것 같다.
'Algorithm' 카테고리의 다른 글
[BOJ][Python3]12933. 오리 (0) | 2024.03.05 |
---|---|
[BOJ][Python3]2504.괄호의 값 (2) | 2022.11.27 |
[BOJ][Python3]15686.치킨 배달 (2) | 2022.11.24 |
[BOJ][Python3]14501.퇴사 (0) | 2022.10.26 |
[Leetcode][Python3] 135. Candy (0) | 2022.04.26 |
댓글